Suppose you and I are playing a two-player zero-sum game repeatedly. There is a payoff matrix $(A_{ij})$, and if I play action $i$ and you play action $j$ then I receive $A_{ij}$ and you receive $-A_{ij}$. I am not clever enough to compute my best strategy (my maximin strategy), but I can just manage to compute a best response to your mixed strategy, if you were to publicize it. Similarly you. We decide that at each turn (i.e., repetition of the game) we will just play a best response to our opponent's apparent strategy so far. To be more specific we each do the following:
- Turn $1$: Play something. Who cares. It's only one turn.
- Turn $n$: Play a best response assuming that the opponent will simply pick one of turns $1,\dots,n-1$ uniformly at random and replay that action.
This is an attractive rough and ready way to try to solve a two-player game when tackling the linear program head-on is difficult. But is it any good? That is, do our strategies converge to our respective maximin strategies? Williams's Compleat Strategyst says it works, but unfortunately it's not the sort of book that gives references.
For example, if we were playing rock-paper-scissors, the play might go as follows:
- rock, rock (we both start arbitrarily)
- paper, paper (paper is the best response to rock)
- paper, paper (paper is the best response to 1/2 rock, 1/2 paper)
- scissors, scissors (scissors is the best response to 1/3 rock, 2/3 paper)
- etc.
Clearly play is always symmetric here and we always draw, but that is not important (and wouldn't be true if we started with different actions). The only thing I care about is whether our distribution of actions converges to 1/3 rock, 1/3 paper, 1/3 scissors (the optimal strategy), and how fast.
