The games that we’ve looked at so far are the simplest case of
basic games. In these games, we’ve got a payoff matrix, and both players
can see the whole matrix – the players have equal information,
and nothing is secret. The players move simultaneously – so neither player can wait to see what his opponent does before making his own decision. Finally, the game is played exactly once – there are no repetitions.

The first complication we can add is to make it an iterative game – that is, instead of each player going once, they’ll repeat the game 10 times in sequence. Everything else stays the same: perfect, equal information, simultaneous moves, etc.

This creates an interesting added dimension. Now, we’ve got two layers
of strategy: each iteration, each player selects a strategy; and then there’s an over-arching strategy that they use to select their strategy each iteration. That over-arching strategy is called a grand strategy

In an iterated game, the optimal solution for players can be different than in the single iteration. The goal is to maximize your total utility at the end of a series of iterations. It’s OK if some iterations result in a loss of utility, so long as by the end of the series of iterations, the final
sum of the utility of the series is maximal.

For example, look at the following game. (This example is copied
from the textbook The Compleat Strategyst (Complete Strategist): Being A Primer On The Theory Of Games Of Strategy.)

Player 1 needs to choose either 1 or 2; player 2 needs to choose A or B. For simplicity, this is set up so that player 2 always pays player 1, so the utility values in the game grid are written as payoffs to player 1. (Originally, I didn’t include an explanation of the game grid payoffs. This confused a lot of readers. Sorry!)

There’s no saddle point here. The maximin for player 1 is 4 (at 2,B); the
minimax for player 2 is 3 (at 1,A). So the simple solution formula from before
doesn’t work. If we’re only playing the game once then there’s no way for
either player to create an idea outcome for themselves. Look at it from the
perspective of player 1. If player 2 picks strategy A, then the best thing for
player 2 to do is to pick strategy 2. But if player 2 picks B, then player 1
is better off picking A. Since the players move simultaneously, player
1 cannot pick the best strategy.

If the game is played once, then there’s no way to play optimally. It’s
basically random. But if you repeat the game multiple times – that
is, you play it as an iterated sequence of games – then you can find an
optimal strategy for selecting strategies. That’s called a grand
strategy: in a game where you make multiple moves, each move is a
strategy, and the process of selecting strategies for each move is a
grand strategy.

There is a successful grand strategy in this kind of iterated
zero-sum game. What’s interesting about it is that our idea of
strategy is not really what works as a successful grand strategy: the successful grand strategy is random.

After all: if player 1 can figure out player 2’s grand strategy,
then he can easily pick an optimal strategy. So the best grand strategy
is one that the other player can’t figure out. If you’re playing randomly, then there’s no way that the other player can predict
what strategy you choose.

So, let’s look at an example of a series of iterations, with player 1 selecting randomly, with a uniform probability distribution, and player
2 playing minimax:

• Iteration one: Player one selects 1, player two selects A. Player one takes 3.
• Iteration two: Player one selects 2, player two selects A. Player one
  wins 5.

It will continue like that. Player one will win 3 half the time, and 5
the other half – for an average of 4 – which is his maximin value. So
playing this way is at least as good for player 1 as maximin.

This is a pretty trivial game: for player 2, he’s guaranteed to
lose, and the only question is how quickly he’s going to lose. And
there’s not any strategy that’s going to really improve things much for player 2. There’s not much that 2 can do: playing strategy B is pretty much a lose for
him. So why would he ever do it?

If player 1 knows that player 2 is always going to play A, then he
could play strategy 2, and always win 5. So player two is motivated to
play B just often enough to make player one try 1 once in a while. The
key is, how often should he do that? What’s the best distribution for him,
to minimize his losses?

As you can see from the example, the key to finding the optimal strategy is
probability. You need to assign a probability distribution to the different
strategies. Each iteration, you pick a strategy randomly, according to the
distribution. If you can find the right probability distribution for your grand strategy, then you can optimize your winnings.

But is there always an optimal distribution? And how can you find it?

There is always an optimum. John vonNeumann (who managed to have his
fingers in an astonishing number of pies) proved that for every two player,
simultaneous move zero-sum iterated game, there is an optimal grand strategy based
on a probability distribution. And it’s computable. It took a while after
JvN to figure out the fast way of doing it – but it’s doable, and it’s doable
quickly, through a technique called linear programming.

Linear programming is a fascinating topic in itself. And it’s complicated
enough that it deserves a post of its own. (Or, more likely, several.)