When I last wrote about game theory, we were working up to how to find

the general solution to an iterated two-player zero-sum game. Since it’s been

a while, I’ll take a moment and refresh your memory a bit.

A zero-sum game is described as a matrix. One player picks a row, and one player picks a column. Those selections are called *strategies*. The intersection

of the strategies in the game matrix describes what one player pays to the other. The

matrix is generally written from the point of view of one player. So if we call

our two players A and B, and the matrix is written from the viewpoint of A, then

an entry of $50 means that B has to pay $50 to A; an entry of $-50 means that A has to pay $50 to B.

In an iterated game, you’re not going to just play once – you’re going to play it repeatedly. To maximize your winnings, you may want to change strategies. It turns out that the optimal strategy is probabilistic – you’ll assign probabilities to your

strategy choices, and use that probability assignment to randomly select your

strategy each iteration. That probability assignment that dictates how you’ll

choose a strategy each iteration is called a *grand strategy*.

Jon Von Neumann proved that for any two-player zero-sum game, there is an optimal grand strategy based on probability. In a game where both players know exactly what the payoffs/penalties are, the best strategy is based on constrained randomness – because any deliberate system for choosing strategies can be cracked by your opponent, resulting in his countering you. The best outcome comes from assessing potential wins and losses, and developing a probabilistic scheme for optimizing the way that you play.

Once you make that fundamental leap, realizing that it’s a matter

of probability, it’s not particularly difficult to find the grand strategy: it’s just a simple optimization task, solveable via linear programming. The solution is very elegant: once you see it, once you see how to

formulate the game as a linear optimization process, it just seems completely obvious.

Continue reading →

### Like this:

Like Loading...