Pathways to Equilibria, Pretty Pictures and Diagrams (PPAD)
- 16:00 19th February 2014 ( week 5, Hilary Term 2014 )Room 278, Oxford e-Research Centre, 7 Keble Road
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 labelled 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 labelled 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 studied by Edmonds (and, earlier, Todd), which generalizes the orientability of abstract simplicial manifolds. Our exposition uses colourful pictures and examples wherever possible.
(Joint work with L. Vegh)
Speaker bio
Bernhard von Stengel is Professor of Mathematics at the London School of Economics, where he has been since 1998. He graduated in Mathematics in 1984 at Aachen, received an MSc in Computer Sciences from the University of Texas in 1986 with an MSc thesis advised by Edsger W. Dijkstra, a PhD from Passau in 1990, and a Habilitation in 1994 from Munich. As a postdoc he worked at the International Computer Science Institute in Berkeley 1994-1995, and as a Heisenberg Fellow in Tilburg in 1995 and at ETH Zurich 1996-1998. His research interests are mathematical and computational problems in game theory, specifically the computation and geometry of equilibria, and discrete mathematics and operations research in general.Share this:
