During the last fifteen years, I am active on two exciting research agendas that lie at the interface of Computer Science and Economics; these interdisciplinary fields enjoy some overlap and are today known as Algorithmic Game Theory and Computational Social Choice. Below, I highlight representative contributions and give the flavour of my research taste, as well as pointers to recent projects.
Algorithmic game theory (AGT) studies the interplay between incentives and computation. In my related involvement, I am motivated by new possibilities for large-scale computing opened by the recent explosive growth of the Internet. Today, the Internet provides knowledge sources about almost everything, a rich menu of services including web search, social media, and cloud computing platforms, an enormous aggregate computing power, and seemingly unlimited storage space. Novel applications that arise every day on the Internet make use of these resources, attract new users, and further contribute to its expansion. However, these applications have to face new challenges. Internet services, knowledge, computing, and storage resources are controlled by different organizations, corporations, and individuals. Access to them may depend on the (economic) incentives of their owners and their users, which may act strategically and, in general, behave in a different way compared to the predictions at the application design phase. Such issues are thoroughly taken into account in the design of applications that directly aim to create revenue. Typical examples include websites that use auctions to sell products; such applications can exploit the significant progress in Economic Theory during the last decades. However, (not necessarily economic) incentives are pervasive on the Internet today and they should be considered in the design of any new software application.
My research focuses on strategic games and studies them from many different angles. Recent studies include: quantifications of the deterioration of system performance due to selfish behaviour (e.g., by studying the price of anarchy of sponsored search auctions [J32] and of resource allocation mechanisms [J47]), techniques for performance improvement through external incentives (e.g., by regulating price competition through subsidies [J42]), algorithm design principles that motivate the players to act truthfully (like in the very recent working paper [W1]on mechanism design with and without money), the computational complexity of equilibria (in particular, for approximate pure Nash equilibria; see [J33, C54]), and many more.
My work in Computational Social Choice (COMSOC) has covered voting, fair division, and matching problems. Voting theory originates from the seminal work of Marquis de Condorcet at the end of the 18th century, soon after the French Revolution. Traditionally, it aimed to study different electoral systems (voting rules) with respect to their amenability to reach socially-good collective decisions (e.g., in government elections, for decision making in committees, etc.). During the last decade, there are efforts to modernize the way we use democracy in the Internet era; these have resulted in the new ideas that fall under an umbrella that is usually called interactive democracy. My intention for the near future is to assess the suitability of the current designs for making good collective decisions. In the recent paper [C100], we present a complexity-theoretic critique of liquid democracy, a novel voting practice according to which a voter can choose between voting directly on a given issue or delegating her vote to another better-informed voter.
A voting rule can be thought of as a well-defined way to select a winning alternative based on the preferences of a set of agents (voters) on a set of available alternatives (candidates). Today, voting provides a compelling method for decision making in multi-agent systems and this is another application that has motivated my related research. For example, my work on the distortion [J35, J41] and the sample complexity of voting rules [J37] aims to assess the strengths and limitations of voting rules for decision making. Applications of voting to specific (combinatorial optimization questions that model) real-world problems such as peer grading in MOOCs or business rating are considered in [J48] and [J46], respectively.
Fair division is the ancient problem of dividing a good (or a set of goods) among individuals in such a way that everybody feels that gets a fair share. In today’s networked world, fair division finds important applications in resource allocation. Essentially, the resources of a system (e.g., the computational resources of a cloud system) correspond to the goods and the users of the system are the individuals that have different requirements for resource usage. Fair division is a minimum requirement for the success of such systems. Recent contributions include the study of novel approximate notions of fairness [J45, C95] as well as the proposal new fairness settings that take knowledge and social constraints into account [C91, C93].
In addition to the AGT- and COMSOC-related contributions mentioned above, several of my recent research projects can be thought of as touching both areas. A representative example is my ongoing activity on kidney exchange, which is part of my involvement in the COST Action CA15210 ECNKEP on “European Network for Collaboration on Kidney Exchange Programmes”. In kidney exchange programmes (KEPs), pairs consisting of a patient suffering from end-stage renal disease and a willing but incompatible donor enroll into a central database and the objective of the KEP is to compute a matching of possible mutual transplantations between the donor of a pair and the patient of another pair and vice versa. In many cases, “chains” that include altruistic donors or longer “cycles” are part of the matching. Several such national programmes run in Europe and the intention of ENCKEP is to study the possibility of merging them into a single KEP. Even though this may look like an obvious win-win situation at first glance, there are many strategic issues that constitute a transnational KEP a very challenging goal. One of them is related to the required property of individual rationality from the matching algorithm: each country should benefit from its participation in the European programme compared to running its own KEP. In a similar abstract problem that we study in [C83], we show how this can be achieved under assumptions on the underlying compatibility graph and the size of each participating country.
In another cross-cutting direction, our paper [C78] on mean estimation is among the few first attempts to study strategic aspects in machine learning. We consider a simple setting which assumes that n single-dimensional data points are drawn from an unknown common distribution and the objective is to learn the mean of this distribution. Our findings suggest that drastically different approaches from the ones currently used in the ML practice should be used, such as, for example, selecting the generalized median after introducing additional equidistant points.
My future research plans are highly influenced by the belief shared by the EconCS research community (which tackles questions at the interface of Computer Science and Economics) that the traditional algorithmic thought has to be revised and extended. First, there is a need for simplicity in algorithm design and the structure of voting rules can be used as a recipe for simplicity. Keeping the structure simple would allow us to determine the best possible algorithm when statistical information for the input data is available; this approach that is highly influenced by machine learning research.
Furthermore, strategic issues also call for a paradigm shift in algorithm design. In large-scale environments composed by self-interested parties, the algorithm designer is actually a game designer. An algorithm running in such an environment defines a strategic game among self-interested parties that act as players. Then, the outcome of the algorithm is essentially what is computed by the actions of the parties themselves, according to their incentives. Whether an algorithm will be successful mainly depends on the properties of the game it defines. So, the design of efficient algorithms is tightly coupled with an in-depth understanding of the strengths and limitations of strategic games as computing machines. A large part of my research plan for the next years is to contribute with concrete intermediate steps towards the visionary technological goal for efficient algorithm design in large-scale environments that might involve self-interested parties, a vision that can significantly improve the applications running on the Internet and have a tremendous impact.