Title:  Exponentiality of the exchange algorithm for finding another room partitioning

One of the most fundamental problem in game theory is finding a Nash equilibrium for two-players games. Edmonds (2009) provides an abstract generalization of the Nash equilibrium theorem for two-players games and the Lemke-Howson algorithm (1964) for finding such equilibria, building upon the concept of “oik”.

Using this concept, several results on the existence of a second object of a certain type can be derived. As an example, it can be shown that, for any triangulated surface, and any subset of its triangles (called “rooms”) partitioning its vertices, there exists another different subset of triangles partitioning the vertices. Given one partition, a second one can be found using an “exchange algorithm” which walks from room to room. In this talk, we discuss the running time of this algorithm, and review some results in this area.