Game Theory

At that level of generality, I can state the problem, but I can't solve it. From what I've read of Theory of Games and Economic Behavior, which I believe is the original work on game theory, it looks like there's a definite method of solution. However, according to the later book The Compleat Strategyst, from which I first learned game theory, that method turned out to be unsatisfactory in some way. I don't know if a satisfactory method was ever found—I will have to investigate and report back.

In the meantime, there's one particular case that is very well understood, namely, zero-sum two-player games. (A general game is zero-sum if for each outcome, the sum of all the players' utilities is zero.) What kinds of games are zero-sum? Well, for one thing, any two-player game in which the outcome is a simple win or loss (or tie) can be regarded as zero-sum by assigning the utilities 1 and −1 to winning and losing. Any game involving money is also typically zero-sum, because money is neither created nor destroyed, only transferred. By the way, being zero-sum is not at all the same thing as being fair. The game with only one outcome, that I win, isn't fair, but is still zero-sum.

Much to my surprise, I had a hard time finding an interesting example of a zero-sum two-player game. All I wanted was a game that didn't seem contrived and yet had an interesting game-theoretic solution. The game Rock, Scissors, Paper, for example, isn't contrived, but the best strategy is, unsurprisingly, to choose randomly among the three options, with equal weights.

This is a good time to point out that the best strategy, from a game-theoretic point of view, may not be much fun. The fun of playing games like Rock, Scissors, Paper comes from trying to guess and exploit the other player's choices; what game theory tells you is that if you choose randomly, and give up trying to exploit the other player, then you also can't be exploited. (Of course, choosing randomly may not be as easy as it sounds—humans are not very good at generating randomness internally.)

Anyway, the example I finally settled on is the game Undercut, which is both defined and analyzed in the eponymous chapter of Metamagical Themas. Here's how it works. Each player chooses a number between 1 and 5 (inclusive) and gets that many points … unless the other player chooses the number one smaller, in which case the other player gets all the points from both numbers.

As it stands, the game isn't zero-sum. If Undercut were being played for money instead of points, with, say, some grant providing the funding, it might be best for the players to cooperate and exploit the funding source by always choosing 5. Or it might not—since a player can productively defect by choosing 4, it might turn into a version of the prisoner's dilemma.

Here, though, we want to make it a zero-sum game, and to do that, we make the reasonable assumption that the players don't care about points per se, but rather about having more points than the other player. The utility to each player, then, is the difference between the points earned, and that makes the game zero-sum. Here's the payoff matrix that results.

	1	2	3	4	5
1	0	3	−2	−3	−4
2	−3	0	5	−2	−3
3	2	−5	0	7	−2
4	3	2	−7	0	9
5	4	3	2	−9	0

The best strategy for this game, it turns out, is to choose randomly among the five options, but with weights 10:26:13:16:1. For example, one should choose 2 most often, exactly 26/66 of the time. This, I hope, is an interesting result, not what you would have expected!

By the way, it's easy to check the result: just observe that the weights are a zero eigenvector of the payoff matrix. In other words, faced with this probabilistic strategy, any choice one makes has an average payoff of exactly zero, so no random combination of choices will be able to do any better.