Summary: the complexity of solving/playing normal-form zero-sum games
From Theory
Notes for CS 8803 - Game Theory and Computer Science. Spring 2008
Given a zero-sum two-person normal-form game, how can we compute its equilibria. From the first problem of GTCS Assignment 1, if the game is represented by a payoff table with rational entries, this can be done exactly in time polynomial in the size of game (in terms of number of bits used to represent it), because linear programming can be solved in polynomial time. However, we have some more intuitive alternatives.
So far, we have seen the Multi-armed bandits algorithm. This gives us an algorithm to play a (repeated) zero-sum game, in which we don't know the payoffs. All we need to know is the number of available strategies. The runtime per period (each update) is linear in the number of strategies. We can also use this or the more efficient weighted-majority algorithm to solve for the value (and optimal strategies) of a game. Simply simulate the algorithm playing for both players in any. This will give us an ε > 0 approximation to the value of the game, for any ε > 0 in time polynomial in 1 / ε. Such an approximation is called a fully polynomial-time approximation scheme. While it seems silly to use such a scheme given that we can exactly compute the value in polynomial time, the runtime is very good in terms of the size of the game matrix. And for many large linear programming problems, the weighted majority algorithm is now being considered for a variety of approximate optimization problems. See this survey:
Multiplicative weights method: a meta-algorithm and its applications. Sanjeev Arora, Elad Hazan, and Satyen Kale. pdf
It is worth knowing that there is something called Fictitious play. In analogy to the experts algorithms, this is a version in which each player simply uses a best-response to the empirical frequency of the opponents play. While we have seen that such a naive "follow-the-leader" approach can lead to poor average payoffs, if both players use it, the empirical distribution over plays will indeed eventually converge to optimal strategies for a two-person zero-sum game. Hence, the term fictitious play, because it's not a good strategy for really playing, but it is useful.
The production of this material was supported in part by NSF award SES-0734780.
