Dagstuhl Seminar 14342
Equilibrium Computation
( Aug 17 – Aug 22, 2014 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/14342
Organizers
- Nimrod Megiddo (IBM Almaden Center, US)
- Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE)
- Vijay V. Vazirani (Georgia Institute of Technology - Atlanta, US)
- Mihalis Yannakakis (Columbia University - New York, US)
Coordinator
- Rahul Savani (University of Liverpool, GB)
Contact
- Annette Beyer (for administrative matters)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
Among the most novel and significant additions to the theory of algorithms and computational complexity over the last decade are deep insights into the computability of equilibrium problems, the two most important ones being market equilibrium and Nash equilibrium. This Dagstuhl seminar provides the unique opportunity of not only summarizing the important progress made since the last seminar on this topic, held in April 2010 (Seminar 10171), but also to explore ways of building on it with the help of top experts who, we expect, will attend this seminar.
We plan on concentrating on the following topics:
- Key algorithmic techniques for computing equilibria: The question of computability of market equiliria has been explored with a wide variety of tools ever since Walras proposed the mechanism of tatonnement process in 1874. For example, impressive approaches were proposed in the 1960s and 70s by top mathematicians, including Herb Scarf and Steve Smale. Around the same time, Lemke & Howson and Curtis Eaves used the powerful machinery of LCP (linear complementarity problem) formulations and complementary pivot algorithms to give practical algorithms for 2-Nash and the linear case of Arrow-Debreu markets, respectively. Interestingly enough, a new revival of these methods, over the last two years, has led to algorithms for fairly general classes of markets. Although not polynomial time, these are simple pivoting-based algorithms which do not suffer from instability issues of other approaches and perform well on randomly chosen instances. They also reveal deep structural properties of the problems. A tutorial on these techniques will be given by Bernhard von Stengel. Another exciting recent result, which will be discussed in detail, is the design of a polynomial time algorithm for rank-1 bimatrix games. To our knowledge, this is the first such result for a problem in which the set of solutions is disconnected.
- Complexity classes that capture computability of equilibria: Equilibrium computation problems cannot be characterized using the usual complexity classes - the new classes PLS, PPAD and FIXP have shed much light on such problems. The latter two have been particularly useful in this respect, with PPAD being applicable when equilibria are rational numbers and FIXP when they are algebraic. However, several problems dealing with both market and Nash equilibria remain open and the community, which seems largely unaware of the subtilities of these complexity classes, stands to benefit from a better understanding. Mihalis Yannakakis will deliver a tutorial on this topic.
- Game and market dynamics: An equilibrium predicts "stable" behavior of the players in a game. Can collective behavior move towards an equilibrium? This question has been studied for various dynamics, such as best response dynamics, fictitious play, or adaptive heuristics. Simulating dynamics with good convergence behavior may be a method of approximately computing an equilibrium. This has been a recent method of choice for computing equilibria in large games in communities which study multiagent systems. It is also important to understand how these methods compare to analytical approaches. Sergiu Hart will deliver a tutorial on this topic.
- Open problems and wider impact: Several of the ideas developed within equilibrium computation appear to transcend the area and to lead to techniques and notions that will benefit other fields, in particular, algorithm design and economics. A special emphasis of this seminar is to identify such ideas.
The aim of this seminar was to study research issues related to algorithms and complexity for computation of equilibria in games and markets. The majority of participants were academics from computer science departments; some were from other disciplines; and several participants were from the corporate research departments of eBay, IBM, and Microsoft. All participants have strong interdisciplinary interests that typically span Economics, Game Theory, and Theoretical Computer Science.
The seminar started with a session of lightening talks, in which participants had two minutes and one slide to introduce themselves. This session was extremely well received, and it was worth the effort to ensure that everyone submitted a slide in advance. It is an effective and efficient way for everyone to get to know a little bit about each other, and thus to have things to talk about outside of talks right from the start of the seminar.
Three tutorials were given on topics chosen by the organizers. Bernhard von Stengel gave a tutorial on complementary pivoting algorithms for the Linear Complementarity Problem (LCP). The tutorial focussed on geometric aspects of LCPs and complementary pivoting algorithms, and in particular Lemke's algorithm. The LCP captures many game and market problems, and it came up throughout the seminar, most directly in the final talk by Adler on reductions to bimatrix games from PPAD Lemke-verified LCPs.
Complementary pivoting algorithms inspired the complexity class PPAD, which, together with FIXP, capture the problems of finding fixed points and equilibria of games and markets. The second tutorial, given by Kousha Etessami, was about the complexity of equilibria and fixed points. It covered PPAD (= linear-FIXP), FIXP, and FIXPa, and discussed some associated open problems. Related contributed talks included the following. Etessami, in a separate talk, showed that the complexity of computing a (perfect) equilibrium for an n-player extensive form game of perfect recall is hard for FIXPa. Gairing showed that the problem of finding an equilibrium of a weighted congestion game is FIXP-hard. Garg presented several results on market equilibria, including the result that it is FIXP-hard to compute an equilibrium of an Arrow-Debreu exchange market with Leontief utility functions. Chen presented a PPAD-hardness result for the problem of finding an approximate equilibrium in an anonymous game with seven actions per player. Mehta showed that it is PPAD-hard to find an equilibrium of a rank-3 bimatrix game. Paparas presented PPAD-hardness results for several market settings with non-monotone utilities. The number of talks related to these complexity classes shows their ongoing importance for the field of equilibrium computation.
The third tutorial was on game dynamics and was given by Sergiu Hart. He showed that "uncoupledness" severely limits the possibilities to converge to Nash equilibria, but on the other hand, there are simple adaptive heuristics, such as "regret matching", that lead to correlated equilibria. At the end of his tutorial, Hart also presented an exponential lower bound on the query complexity of correlated equilibria. In a closely related contributed talk, Goldberg gave bounds for the query complexity of approximate equilibria of various types, including for the relatively new concept of epsilon-well-supported correlated equilibrium.
A large number of contributed talks presented algorithms for computing equilibria of games and markets. On market equilibria we had the following algorithmic talks: Cole presented an asynchronous gradient descent method that implements asynchronous tâtonnement; Mehlhorn presented a combinatorial polynomial-time algorithm for the linear exchange model; Vazirani introduced Leontief-Free Utility Functions and presented a complementary pivoting algorithm for computing an equilibrium in markets with these utilities; and Vegh presented new convex programmes for linear Arrow-Debreu markets. On other game models, we had the following algorithmic talks: Cummings presented an efficient differentially private algorithm for computing an equilibrium in aggregative games; Savani presented a gradient descent algorithm for finding an approximate equilibrium of a polymatrix game; and Skopalik presented algorithms for finding approximate pure equilibria of congestion games.
There were other contributed talks on a range of topics: Harks talked about resource competition on integral polymatroids; Hoefer talked about decentralized secretary algorithms; Jain presented an analysis of several business models and pricing schemes; and Schäfer presented results about coordination games on graphs.
Apart from the topics of the tutorials, all other talk topics were chosen by the presenters, not by the organizers. Generally talks were informal, and were very interactive, often with lengthy discussions taking place during them. All talks were well received. Open problems were discussed in two sessions, the first during a normal seminar room session, and the second with cheese and wine in the evening. Below we give abstracts for the talks and brief summaries of the open problems that were discussed.
Creative Commons BY 3.0 Unported license
Nimrod Megiddo and Kurt Mehlhorn and Rahul Savani and Vijay V. Vazirani
- Ilan Adler (University of California - Berkeley, US) [dblp]
- Susanne Albers (TU München, DE) [dblp]
- Xi Chen (Columbia University - New York, US) [dblp]
- Richard Cole (New York University, US) [dblp]
- Rachel Cummings (Northwestern University - Evanston, US) [dblp]
- Kousha Etessami (University of Edinburgh, GB) [dblp]
- Martin Gairing (University of Liverpool, GB) [dblp]
- Jugal Garg (MPI für Informatik - Saarbrücken, DE) [dblp]
- Paul W. Goldberg (University of Oxford, GB) [dblp]
- Tobias Harks (Maastricht University, NL) [dblp]
- Sergiu Hart (The Hebrew Univ. of Jerusalem, IL) [dblp]
- Penny Haxell (University of Waterloo, CA) [dblp]
- Martin Hoefer (Universität des Saarlandes, DE) [dblp]
- Kamal Jain (eBay Research Labs, US) [dblp]
- Nimrod Megiddo (IBM Almaden Center, US) [dblp]
- Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
- Ruta Mehta (Georgia Institute of Technology - Atlanta, US) [dblp]
- Peter Bro Miltersen (Aarhus University, DK) [dblp]
- Dimitris Paparas (Columbia University - New York, US) [dblp]
- Britta Peis (RWTH Aachen, DE) [dblp]
- Yuval Rabani (The Hebrew University of Jerusalem, IL) [dblp]
- Rahul Savani (University of Liverpool, GB) [dblp]
- Guido Schäfer (CWI - Amsterdam, NL) [dblp]
- Leonard J. Schulman (CalTech - Pasadena, US) [dblp]
- Alexander Skopalik (Universität Paderborn, DE) [dblp]
- Madhu Sudan (Microsoft New England R&D Center - Cambridge, US) [dblp]
- László A. Végh (London School of Economics, GB) [dblp]
- Bernhard von Stengel (London School of Economics, GB) [dblp]
Related Seminars
Classification
- data structures / algorithms / complexity
Keywords
- Algorithms
- Computational Complexity
- Equilibrium Computation
- Game Theory
- Market Equilibrium
- Nash Equilibrium
