Abstract

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.)