http://www.dagstuhl.de/07471

### 18. – 23. November 2007, Dagstuhl Seminar 07471

# Equilibrium Computation

## Organisatoren

Jean-Jacques Herings (Maastricht University, NL)

Marcin Jurdzinski (University of Warwick – Coventry, GB)

Peter Bro Miltersen (Aarhus University, DK)

Éva Tardos (Cornell University, US)

Bernhard von Stengel (London School of Economics, GB)

## Auskunft zu diesem Dagstuhl Seminar erteilt

## Dokumente

Dagstuhl Seminar Proceedings

Teilnehmerliste

## Summary

The purpose of this Dagstuhl seminar was to bring together researchers from different disciplines working on algorithmic problems of finding equilibria.

The abstracts of 25 talks are listed below. In addition to his talk, Paul Goldberg gave an introduction to the complexity class PPAD which is central for defining the complexity of finding one equilibrium (for example, a Nash equilibrium in a game of $n$ players). This talk is accessible through the following URL: http://www.csc.liv.ac.uk/~pwg/PPADintro/PPADintro.html. This colorful talk was prepared by Paul Goldberg in Dagstuhl in immediate response to requests for such an introduction, and is described as such on the mentioned webpage.

Furthermore, Mike Paterson gave a popular evening talk on the entertaining topic of piling bricks so that they can "stick out" as far as possible, which can be considered as an "equilibrium problem" in physics but not in the computational sense studied in the seminar.

Overall, the seminar talks represented a good balance of the topics, and were not too numerous so as to make listening tiresome. A significant time was spent in discussions, drawing on the expertise of experienced scholars in the field (for example, Nimrod Megiddo). We encouraged, with success, to let junior researchers present their work as much as possible. The survey talks, often given by senior researchers, gave introductions and overviews.

Many of the topics of the seminar are in areas with very hard and long-standing open questions. In particular, solving parity games, or the related mean-payoff and simple stochastic games, in polynomial time is an intriguing open problem. It is a plausible conjecture that this can be done, given that the problem is in the intersection of the complexity classes NP and co-NP. The most famous problem with that property is linear programming (LP), which is equivalent to finding an equilibrium in a zero-sum game, and thus closely related to the problems discussed in the seminar. The polynomial-time algorithms for linear programming, such as the ellipsoid method, were hailed as breakthroughs at the time. To this day, the understanding even of the linear programming problem is limited; for example, we do not have a "combinatorial", simplex-type algorithm that would solve this problem in polynomial time.

In this context, the results by Nir Halman on an abstract view of LP-type problems and their connection to the parity games and their relatives, provided one example of a ``bridge'' across several fields, Mathematical Programming, Parity Games, and the Complexity of Finding Equilibria. Some discussions started in how this could be extended to the computation of Nash equilibria of bimatrix games.

The equilibrium problems discussed in this seminar are much harder than linear programming, which by itself is an important interesting case. None of the main problems were solved – this would have been close to sensational –, but we could observe some (necessarily partial and incremental) progress.

The hard problems mentioned above are concerned with computing Nash equilibria. Another focus of the seminar was the computation of other, more refined solution concepts. Here, the interaction between the participants from the computer science community and the participants from the economics community was extremely fruitful. In particular, a number of computational problems were jointly formulated which together form an interesting research program.

A representative example is the following: Given a three-player game in normal form {em and} a strategy profile of the game, can it be decided in polynomial time if the strategy profile is a (trembling hand) perfect equilibrium of the game? The corresponding computational problem for Nash equilibria is trivial. One can ask the same question for other refinement notions, and we believe it would be very interesting to classify refinement notions by hardness or easiness of their verification problem, for two reasons. First, an easiness result would be useful in practice for studying equilibria computationally. Secondly, a refinement notion where even the verification problem is computationally intractable may arguably be considered an inferior solution concept to one where it is tractable to determine if a given profile is in equilibrium.

The workshop demonstrated that the topic of "equilibrium computation" is of great current interest. The stimulating discussions showed that it was very well worth bringing researchers together who normally operate in different communities.

## Dagstuhl Seminar Series

- 14342: "Equilibrium Computation" (2014)
- 10171: "Equilibrium Computation" (2010)

## Classification

- Artificial Intelligence / Robotics
- Semantics / Specification / Formal Methods
- Verification / Logic

## Keywords

- Planning
- Multiagent systems
- Reasoning

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

Download Übersichtsflyer (PDF).

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von

Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet und im Erdgeschoss der Bibliothek präsentiert.

Seminar Homepage : Letzte Änderung 17.01.2017, 13:55 Uhr