Dagstuhl Seminar 13161
Interface of Computation, Game Theory, and Economics
( Apr 14 – Apr 19, 2013 )
- Sergiu Hart (The Hebrew Univ. of Jerusalem, IL)
- Éva Tardos (Cornell University, US)
- Bernhard von Stengel (London School of Economics, GB)
- Andreas Dolzmann (for scientific matters)
- Annette Beyer (for administrative matters)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
The aim of this seminar is to study research issues at the interface of computing, game theory and economics. It will facilitate discussions among people working in different disciplines, with different perspectives that can be usefully synthesized in approaching problems of shared interest. The seminar topics include models of learning by computational agents in economic settings; research on the role of complex networks in economic systems; the welfare properties and stability of equilibria; the computational tractability of basic economic problems, and the design of computationally feasible mechanisms; and the role of information, trust, and reputation in markets.
The last decade has seen an explosive growth of research at the interface of computing and game theory, and more generally economics. In large part, this growth has been fueled by the emergence of large communication networks. The success of such large systems requires them to support a very diverse set of users, and to ensure that network participants cooperate despite their diverse goals and interests. There is a significant opportunity for multiple research communities to contribute together to the understanding of these phenomena, the formulation of possible interventions, and the broader policy discussions aimed at increasing the robustness of the systems involved.
The seminar is aimed at bringing together the leading researchers from computer science and from game theory and economics to discuss these issues. The following are some topics of interest:
- Economic theory often neglects the computational bottlenecks due to exponential computation and communication in a mechanism. As economic systems grow in complexity, the computational difficulty in determining their equilibria translates into conceptual intractability and unpredictability in reasoning about them. Computational ideas can potentially identify types of market conditions that trigger such intractability, and suggest approaches to make them more tractable.
- Understanding the interconnectedness of complex economic systems requires models and theories for the underlying network structures and their dynamics. Models of networks and interacting computational agents can offer techniques for reasoning about cascading effects and social-contagion phenomena, and can provide guidance in how to control and shape them.
- Quantifying the welfare properties of economic interactions. The aim is to quantify the welfare properties of equilibria, and of outcomes under various models of the participants' behavior. Complex economic systems generally have more than one equilibrium, and natural models of agent behaviors may not guarantee convergence to such an equilibrium. Different equilibria, and different models of agent behaviour, can lead to outcomes where the participants' welfare can be very different. Quantifying the welfare properties of the outcomes follows in a long line of research quantifying the performance of algorithms under sub-optimal conditions, ranging from conditions with limited computational resources (approximation algorithms) to limited information about the future (on-line algorithms). For large classes of interesting games these measures of equilibrium quality have turned out to be encouragingly favorable both for equilibria, and more recently, for outcomes of learning behavior of the agents.
- Computational approaches to mechanism design can provide ways of constructing robust and tractable market institutions, by controlling sources of complexity and promoting specific patterns of participant behavior. Mechanism design considers the problem of designing incentives to guide the behavior of self-interested agents toward a collective goal. Recent work by computer scientists has added computational considerations to the classic mechanism design problems that have a long tradition in economists. There has been significant recent progress on computationally feasible mechanism design, both in designing techniques that can be efficiently implemented, and in understanding the limits of such designs.
The aim of this seminar was to study research issues at the interface of computing, game theory and economics. It facilitated discussions among people working in different disciplines. The majority of participants were academics from computer science departments, and the others (about one third) from other disciplines such as economics or corporate research departments of Google or Microsoft. All have strong cross-disciplinary interests.
Economic transactions on the internet are of ever-increasing importance. In order to execute and support them algorithmically, it is important to understand the agents' incentives on one hand and computational constraints on the other hand. This is studied in approaches to mechanism design and auctions, which formed a large part of the topics of this workshop.
Theoretical and practical issues of mechanism design were topics of the following presentations: epistemic implementations with belief levels (Jing Chen), translating agent-provided inputs to optimization (Constantinos Daskalakis), reward schemes (Shahar Dobzinski), the difficulties of allocating more than one good (Sergiu Hart), advertisement exchanges (Vahab Mirrokni), mechanisms for the private supply of a public good (Rudolf Müller), truthfulness versus privacy (Aaron Roth), composing mechanisms (Vasilis Syrgkanis), and allocating indivisible objects (Rakesh V. Vohra).
Aspects of auctions concerned "expressiveness" about preferences (Paul Dütting), the approximate optimality of marginal revenue maximization (Jason D. Hartline), improving the design of online advertising auctions (Kevin Leyton-Brown), commitment (Katrina Ligett), inefficiency of multi-unit auctions (Vangelis Markakis), symmetric auctions (Mallesh Pai), interdependent values (Tim Roughgarden), and spectrum auctions (Ilya Segal).
Understanding the interconnectedness of complex economic systems requires models and theories for the underlying network structures and their dynamics. Networks were studied with respect to social segregation (Nicole Immorlica), practical market applications (Ramesh Johari), online creation (Thomas Kesselheim), competition (Brendan Lucier), and social contagion (Sigal Oren).
Social models, with bridges to mechanism design, were studied in presentations on division protocols (Simina Branzei), randomized social choice (Markus Brill), ranking methods (Gabrielle Demange), power changes in voting games (Edith Elkind), and incentives beyond selfishness (Guido Schäfer).
Achieving and computing an equilibrium in dynamic models of large interactions such as games and market models was studied for large aggregative games (Yakov Babichenko), new price updating in markets (Nikhil R. Devanur), payoff queries for games (Paul W. Goldberg), limit processes for evolutionary games (Bill Sandholm), and tournament competitions (Bernhard von Stengel).
The topics were chosen by the presenters, not by the organizers. The rather strong emphasis on mechanism design and auctions (which may have caused one single critical feedback comment on "too much groupthink") reflects the strong current interest in this area, in line with its economic importance, for example as the source of the riches of Google and other internet search engines.
- Yakov Babichenko (California Institute of Technology - Pasadena, US) [dblp]
- Simina Branzei (Aarhus University, DK) [dblp]
- Markus Brill (TU München, DE) [dblp]
- Jing Chen (Institute of Advanced Study - Princeton, US) [dblp]
- Giorgos Christodoulou (University of Liverpool, GB) [dblp]
- Constantinos Daskalakis (MIT - Cambridge, US) [dblp]
- Gabrielle Demange (Paris School of Economics, FR) [dblp]
- Nikhil Devanur Rangarajan (Microsoft Corporation - Redmond, US) [dblp]
- Shahar Dobzinski (Weizmann Institute - Rehovot, IL) [dblp]
- Paul Dütting (EPFL - Lausanne, CH) [dblp]
- Edith Elkind (Nanyang TU - Singapore, SG) [dblp]
- Michal Feldman (The Hebrew Univ. of Jerusalem, IL) [dblp]
- Felix Fischer (University of Cambridge, GB) [dblp]
- Paul W. Goldberg (University of Liverpool, GB) [dblp]
- Yannai A. Gonczarowski (The Hebrew Univ. of Jerusalem, IL) [dblp]
- Sergiu Hart (The Hebrew Univ. of Jerusalem, IL) [dblp]
- Jason D. Hartline (Northwestern University - Evanston, US) [dblp]
- Penelope Hernandez Rojas (University of Valencia, ES) [dblp]
- Martin Hoefer (MPI für Informatik - Saarbrücken, DE) [dblp]
- Nicole Immorlica (Northwestern University - Evanston, US) [dblp]
- Ramesh Johari (Stanford University, US) [dblp]
- Thomas Kesselheim (Cornell University, US) [dblp]
- Max Klimm (TU Berlin, DE) [dblp]
- Elias Koutsoupias (University of Oxford, GB) [dblp]
- Kevin Leyton-Brown (University of British Columbia - Vancouver, CA) [dblp]
- Katrina Ligett (CalTech - Pasadena, US) [dblp]
- Brendan Lucier (Microsoft New England R&D Center - Cambridge, US) [dblp]
- Jeffrey MacKie-Mason (University of Michigan - Ann Arbor, US) [dblp]
- Vangelis Markakis (Athens University of Economics and Business, GR) [dblp]
- Vahab Mirrokni (Google - New York, US) [dblp]
- Hervé J. Moulin (Rice University - Houston, US) [dblp]
- Rudolf Müller (Maastricht University, NL) [dblp]
- Sigal Oren (Cornell University, US) [dblp]
- Mallesh Pai (University of Pennsylvania, US) [dblp]
- Dmitrii V. Pasechnik (Nanyang TU - Singapore, SG) [dblp]
- Aaron Roth (University of Pennsylvania - Philadelphia, US) [dblp]
- Tim Roughgarden (Stanford University, US) [dblp]
- William H. Sandholm (University of Wisconsin - Madison, US) [dblp]
- Rahul Savani (University of Liverpool, GB) [dblp]
- Guido Schäfer (CWI - Amsterdam, NL) [dblp]
- Michael Schapira (Hebrew University - Jerusalem, IL) [dblp]
- Ilya R. Segal (Stanford University, US) [dblp]
- Vasilis Syrgkanis (Cornell University, US) [dblp]
- Éva Tardos (Cornell University, US) [dblp]
- Berthold Vöcking (RWTH Aachen, DE) [dblp]
- Rakesh V. Vohra (Northwestern University - Evanston, US) [dblp]
- Bernhard von Stengel (London School of Economics, GB) [dblp]
- Jens Witkowski (Universität Freiburg, DE) [dblp]
- data structures / algorithms / complexity
- world wide web / internet
- Algorithmic Game Theory
- Nash Equilibria
- Mechanism Design