University of Cambridge > Talks.cam > Optimization and Incentives Seminar > Pathways to Equilibria, Pretty Pictures and Diagrams (PPAD)

Pathways to Equilibria, Pretty Pictures and Diagrams (PPAD)

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Felix Fischer.

Existence of an equilibrium in various economic models can be shown 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” recently introduced by Edmonds, which generalizes the orientability of abstract simplicial manifolds. Our exposition uses colorful pictures and examples wherever possible.

(Joint work with Marta Maria Casetti, Julian Merschen and Laszlo Vegh.)

This talk is part of the Optimization and Incentives Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity