Homotopy methods for Nash equilibrium computation

In computational game theory, we prefer fast algorithms to slow ones, but we also prefer algorithms that seem "natural", capable of being carried out in the real world. This is perhaps a special feature of computational game theory (in comparison with most other areas of algorithmics) - we do not just want a solution, but the solution should represent something that happens "out there". (This recent blog post by Vohra makes the stronger claim that if a game-theory problem is polynomially solvable, there is usually a natural algorithm for it.)

Homotopy methods are based on a simple and appealing idea - given some game of interest, you start by constructing a version of that game where the numbers involved (that is, the payoffs associated with the various strategy combinations) have been changed so that there is a single "obvious" solution. (And let us assume that it is Nash equilibrium that we are interested in.) Then you gradually move all the numbers towards the ones that represent the game of interest, keeping track of this Nash equilibrium, which should change continuously.

The "starting" game (i.e. the one with the obvious, easy-to-find Nash equilibrium) can perhaps be assumed to represent some kind of prior belief by the players about what each other are doing, or what is the best action in the absence of knowledge about the other players. In that case, the above process seems to represent some kind of natural learning process that you can believe might actually happen. What we get in addition is a criterion for equilibrium selection --- we would like to believe that there really is a single correct answer to the question of "what is the outcome of this game?" and where there are multiple Nash equilibria, this kind of procedure usually identifies just one of them.

Browder's Fixpoint Theorem

Browder's fixpoint theorem -- not to be confused with Brouwer's fixpoint theorem -- can be used to show that such a path of Nash equilibria actually exists. The theorem says the following. Suppose you have a compact domain X, so that Brouwer's (not Browder's) fixpoint theorem promises that any continuous function from X to X has a fixpoint. Suppose that for each t in [0,1], f_t is a continuous function from X to X. Furthermore, the functions f_t are actually a continuum of continuous functions; if u converges to w then f_u converges to f_w. Then there is a path connecting some fixpoint of f₀ with a fixpoint of f₁. But, it should be noted that the path need not be monotonic as a function of t. In the context of games, it is easy to construct 2-player 2-action games where you have to backtrack in moving from one to the other.

Some literature

I recently read the following 2 papers in some detail, so far have probably just scratched the surface. The first paper (in Economic Theory, 2009) listed below gives a survey of different methods and how they work. It includes a nice explanation of how the Lemke-Howson algorithm can be seen to be a homotopy method.

The second paper (in GEB, 2002) addresses computation of approximate Nash equilibria for multiplayer games. It uses the notion of ε-Nash equilibria that some of us in the CS community worked with more recently. Recall that for multiplayer games, one needs to give up on exact NE in general, since they may require irrational numbers to specify them. (For 3+ players, a NE may need to be the solutions of a high-order polynomial.) Given a homotopy between multiplayer games, they first partition the space into simplices, then approximate the payoffs within each simplex by linearly interpolating between its vertices (i.e you evaluate the true payoffs at the vertices, but inside a simplex the approximate payoffs are allowed to differ from the correct ones). Having discretised the space in this way, the algorithm implicitly constructs a graph on simplices and sub-simplices, of degree at most 2, whose degree-1 vertices are approximate equilibria of the games at the extremes of the homotopy. So, to get from the NE of the "starting game" to the game of interest, you follow this path. I haven't understood the details yet; not even sure if the graph is directed like in PPAD problems.

The paper does not apply Browder's theorem, but Browder's theorem essentially follows from the construction of the graph, at least in the context of approximations to multiplayer games.

Homotopy methods to compute equilibria in game theory by Herings and Peeters

Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games by Herings and van den Elzen