Tutte seminar - Bernhard von Stengel

Constructing and computing equilibria for two-player games

Abstract:

A bimatrix game is a two-player game in strategic form, a basic model in game theory. A Nash equilibrium is a pair of (possibly randomized) strategies, one for each player, so that no player can do better by unilaterally changing their strategy. We give an introduction to the structure of Nash equilibria of bimatrix games based on best-reply regions derived from the payoff matrices. The corresponding mathematical objects are two polytopes for the two players and their combinatorial properties. With this geometric insight, one can construct games with certain properties, and understand algorithms for computing equilibria. We explain the classic Lemke-Howson algorithm, a pivoting method similar to the simplex algorithm for linear programming, that finds one Nash equilibrium. It also shows that a generic game has an odd number of equilibria.

We describe a class of square bimatrix games for which the shortest Lemke-Howson path grows exponentially in the dimension d of the game. We construct the games using pairs of dual cyclic polytopes with 2d facets in d-space and a suitable "labelling" of their facets.

The latter result is joint work with Rahul Savani, published in: R. Savani and B. von Stengel (2006), Hard-to-Solve Bimatrix Games. Econometrica 74, 397-429.