Christos Papadimitriou

IFORS Distinguished Lecture

Elise del Rosario (right)  presents the IFORS award to ITL Christos Papadimitriou.

EURO XXIII, Bonn, Germany
Computing Equilibria

Christos Papadimitriou
IFORS Distinguished Lecturer
University of California at Berkeley

Abstract

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.