Bernhard von Stengel
Abstract:
A bimatrix game is a basic model in non-cooperative game
theory. Its central solution concept is the Nash equilibrium.
For bimatrix games, Nash equilibria are best understood
geometrically. Recent results seem to make it unlikely that
a polynomial-time algorithm for finding one Nash equilibrium
exists. In this talk we consider the problem of finding
*all* Nash equilibria of a bimatrix game. First, we will
introduce the main concepts and geometric tools. Then, we
will describe the state-of-the-art algorithms, which are
based on linear programming and polyhedral computation, and
report the results of computational experiments.
Joint work with David Avis, Gabriel Rosenberg, and Rahul Savani.