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.