http://www.dagstuhl.de/10171

### April 25 – 30 , 2010, Dagstuhl Seminar 10171

# Equilibrium Computation

## Organizers

Edith Elkind (Nanyang TU – Singapore, SG)

Nimrod Megiddo (IBM Almaden Center, US)

Peter Bro Miltersen (Aarhus University, DK)

Vijay V. Vazirani (Georgia Institute of Technology – Atlanta, US)

Bernhard von Stengel (London School of Economics, GB)

## For support, please contact

## Documents

Dagstuhl Seminar Proceedings

List of Participants

Dagstuhl Seminar Wiki

Dagstuhl Seminar Schedule [pdf]

(Use seminar number and access code to log in)

## Summary

The focus of this seminar was the algorithmic problem of computing equilibria in games and market models, viewed from both the theoretical and practical perspective. The equilibrium computation problem is one of the central topics in the rapidly expanding field of algorithmic game theory.

The seminar was a
follow-up to Seminar 07471, on the same topic, but with
three new organizers, and with a focus on some of the aspects
of this problem that received relatively little attention
in Seminar 07471. One of the major themes of this
seminar was *dynamics*, i.e., exploring the agents' behavior (at both
individual and collective level) that leads to the discovery of
equilibria, and, more generally, adaptive changes in the collective
behavior. Discussed were the classic game-theoretic
approaches to this topic (organizer: von Stengel) as well
as more recent
computational and simulation-based techniques, as studied by the
multi-agent community (organizer: Elkind). Another key emphasis was on
algorithms and complexity results for * market equilibria* and their
applications to Nash Bargaining Games (organizer: Vazirani). We also
compared these approaches with computational and geometric aspects of
the central Linear Complementarity Problem (LCP) in mathematical
programming (organizer: Megiddo). Finally, since the last seminar
there was significant progress understanding the complexity
of important algorithms, such as strategy iteration, for solving
two-player zero-sum games of infinite duration.
Progress in this area has strong connections to mathematical
programming and was discussed and extended (organizer: Miltersen).

The following abstracts indicate the diversity of topics and their rich interconnections that were explored during a very successful seminar.

## Dagstuhl Seminar Series

- 14342: "Equilibrium Computation" (2014)
- 07471: "Equilibrium Computation " (2007)

## Classification

- Seminar
- Ds/alg/compl
- Www
- Interdisciplinary

## Keywords

- Algorithmic game theory
- Equilibrium
- Economic models