Christos Papadimitriou

Title of Presentation: Computing Equilibria


Bonn, Germany


The existence theorems establishing that certain equilibria, such as the mixed Nash equilibrium and price equilibria, are guaranteed to exist under very general conditions, are some of the most reassuring results in Economics.Developing efficient algorithms for computing these equilibria

– that is, rendering these existence theorems constructive

– has been over the past decades an important research front, which however has met with very limited success. In recent years, a new kind of complexity theory has been developed and applied to establish that certain of these computational problems are intractable, thus explaining the lack of progress in the development of efficient algorithms for them.

These complexity results raise important new questions related to efficient algorithm for computing approximate equilibria, not unlike the way in which the theory of NP-completeness for combinatorial optimization problems in the 1970s led researchers to the exploration of approximation algorithms. In this talk I shall survey these complexity results, as well as a few recent algorithmic advances.