August 17th – August 22nd 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)
For support, please contact
Annette Beyer for administrative matters
Roswitha Bardohl for scientific matters
(Use seminar number and access code to log in)
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.
Dagstuhl Seminar Series
- Data Structures / Algorithms / Complexity
- Computational Complexity
- Equilibrium Computation
- Game Theory
- Market Equilibrium
- Nash Equilibrium