|IFORS Distinguished Lecture|
Elise del Rosario (right) presents the IFORS award to ITL Christos Papadimitriou.
EURO XXIII, Bonn, Germany
Computing EquilibriaChristos Papadimitriou
IFORS Distinguished Lecturer
AbstractThe 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
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.