August 17 – 22 , 2014, Dagstuhl Seminar 14342
Nimrod Megiddo (IBM Almaden Center, US)
Kurt Mehlhorn (MPI für Informatik – Saarbrücken, DE)
Vijay V. Vazirani (Georgia Institute of Technology, US)
Mihalis Yannakakis (Columbia University – New York, US)
Rahul Savani (University of Liverpool, GB)
1 / 2 >
For support, please contact
(Use seminar number and access code to log in)
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
Dagstuhl Seminar Series
- Data Structures / Algorithms / Complexity
- Computational Complexity
- Equilibrium Computation
- Game Theory
- Market Equilibrium
- Nash Equilibrium