Pathways to Equilibria, Pretty Pictures, and Diagrams (PPAD)

Pathways to Equilibria, Pretty Pictures, and Diagrams (PPAD)

Bernhard von Stengel
LSE Department of Mathematics

Thursday, Oct.23, 2014
4:00 - 5:00 PM
Y2E2 300

Abstract:

Existence of an equilibrium in various economic models can be shown to exist by following a certain combinatorially defined path, for example of edges of a labeled polytope similar to the simplex algorithm for linear programming. In addition, such a path has a direction that defines the "index" of an equilibrium. Examples include Sperner's lemma about completely labeled simplices and Nash equilibria in games. We present a general model of "pivoting systems" that shows the essence of the path-following and the directedness argument. We also present a connection of bimatrix games where the paths are exponentially long with signed perfect matchings in Euler graphs, and an algorithm that gives a polynomial-time "shortcut" for these paths. We also present a concept of orientation for the "Euler complexes" or oiks introduced by Edmonds, which generalizes the orientability of abstract simplicial manifolds. Our exposition uses colorful pictures and examples wherever possible. (Joint work with L. Vegh)

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html