Abstract: A game in strategic form is a basic model of game theory. The main solution concept is Nash equilibrium, which recommends to each player a strategy that is optimal for that player if the other players follow their recommendations. A Nash equilibrium in mixed (randomized) strategies is known to exist, but the computational challenge is to find one. A classic "homotopy" method is to follow a path from an easily computed equilibrium of a distorted game while reducing the distortion until one reaches and thereby solves the original game. For two-player games, this can be implemented with a simplex-like algorithm. This talk presents recent progress on this topic. We present a polynomial-time algorithm for rank-1 games. These are games that allow, via a rank-1 matrix, win-win interactions beyond zero-sum payoffs, which should be of economic interest.
The second talk gives a general discussion of future challenges in computational game theory. There seems to be a large gap between theory (often focused on hardness results) and practice (with models chosen ad hoc for computational tractability). To improve our algorithms, we need benchmark cases of "difficult" games that arise in practice.