display | more...

Many of the more powerful results in game theory seem far removed from direct considerations of strategy. For instance, whilst the minimax theorem proves that any two player zero-sum game in strategic form will have a value, and hence any rational player will have to aim for that value, there is no indication of what strategy the player should employ to achieve this aim. By contrast, using linear programming techniques to find an optimal strategy sheds little light into why that strategy works.

Fortunately, there are many special classes of payoff matrix whose structure is vulnerable to a bit of ingenuity instead of some algorithmic heavy lifting, so there is still something for the avid puzzle solver to play with. A good example is given by the set of magic square games.

A two player n×n zero-sum game is described as a magic square game if the payoff matrix A is a magic square- that is, the sum of any row, column or diagonal is constant. What is the optimal strategy for such a game?

It is hopefully clear that given a strategy for Player 1 that returns x regardless of Player 2's strategy, the value of the game is at least x; and that given a strategy for Player 2 that returns y to Player 1 regardless of Player 1's strategy, the value of the game is at most y. From there, it follows that if x=y, then x ≤ V ≤ x so the value is precisely x. This gives a test for strategies that are claimed to be optimal.

Let our magic square be such that the sum of any row or column is s.

If Player 1 uses the strategy (1/n, 1/n, ... , 1/n) - that is, picks randomly from the rows with an equal chance of picking each - then they will receive the average of whichever column is picked by Player 2. But since the sum of any column is the fixed amount s, the return is therefore s/n regardless of Player 2's choice. So we have x=s/n.

But for the columns as for the rows- if Player 2 also uses the strategy (1/n, 1/n, ... , 1/n), then Player 1 ends up with the average of the row they chose. Again, this is s/n for any row, so we have y=s/n. Hence, there is a value of s/n and the optimal strategy is to pick at random, yet uniformly.

Note that no use was made of the diagonal condition on magic squares; thus this argument extends to payoff matrices that take the form of latin squares, and thus any that satisfy a sudoku grid structure too!

Log in or register to write something here or to contact authors.