Ridere, ludere, hoc est vivere.

Thursday, September 19, 2013

Game Theory: A simple multi-player case

Earlier this week I was listening to Episode 36 of the Flip the Table podcast, which discussed the obscure 1979 Bruce Jenner Decathlon Game (publisher Parker Brothers).  The game consists of ten mini-games using an eclectic variety of mechanics.  One of them caught my attention as an elegant bluffing and second-guessing procedure used to resolve the "foot races" in the decathlon.

Each player has three cards numbered '2,' '3,' and '4.'  Players secretly each select one of the three cards, then all reveal their choices simultaneously.  Players whose selection matched that of any other player(s) advance their track figure only one space along the track, whereas players who selected a unique number (one that no other player selected) advance a number of spaces along the track equal to the number on the card they selected.  The process repeats until one player's track figure crosses the finish line to win the race.

This mechanic caught my attention because I had just been brainstorming about ideas in which players might secretly and simultaneously select from among a number of options whose benefit would be greater if fewer other players made the same selection; i.e. the less popular the selection, the more beneficial it would be to those who chose it.  So here was a perfect example, better than anything I'd thought of so far.

Now, it occurred to me that whereas this "mini-game" wouldn't work for only two players, it makes a nice game theory problem for a multi-player case.  In two-player game theory, a game is represented as a matrix of pay-offs in which the axes represent the discrete decision spaces of the two players.  We can examine the two-player game as a matrix and see why this game is meaningless as a two-player game.

 Figure 1: Two-player game theory matrix
Figure 1 shows what the payoff matrix looks like.  Player A and Player B each secretly and simultaneously choose 2, 3, or 4.  They reveal and cross-reference the result on the payoff matrix.  Positive results indicate Player A's net progress against Player B; negative result indicates that Player B gains ground relative to Player A.  Each is motivated to choose '4' every time; unilaterally switching to '2' or '3' only yields a worse result for the player deviating from '4.'  So there's no game in the two-player case.  This game is said to have a Nash Equilibrium (after the mathematician John Nash).

 Figure 2: Three-player game theory matrix
Now let's look at the three-player case.  A single matrix isn't going to work in this case.  Instead, we'll have three matrices, one for each of Player C's three choices '2,' '3,' or '4.'  I've color-coded the players' payoffs to help keep them straight.  Without loss of generality, I assume Player A to be in the lead or tied for the lead, Player B to be tied for either first or second or alone in second, and Player C to be tied for second or alone in third.  Now we no longer have a zero-sum game but instead show progress for each result in the form "A/B/C" where A = Player A's payoff, B = Player B's payoff, and C = Player C's payoff.  Player A's payoff is his change in position relative to B.  Player B's payoff is his change in position relative to A, the leader.  Player C's payoff is also his change in position relative to A, the leader.

If all three players choose simultaneously to minimize their potential loss, all three will choose '4.'  But there appears to be a new Nash Equilibrium here - and not the one you might think.  If A anticipates that B and C will choose 4, then A will choose 3 so as to extend his lead over B, who will have made the same choice as C.  But now if B anticipates that A will choose 3 and C will choose 4, then B will choose 3 so as not to lose ground against A.  If C anticipates that A and B will choose 3, then C will stick with 4.  Coming back to A, if A anticipates that B will choose 3, A will stick with 3 so as not to lose ground against B.  So, theoretically, the first- and second-place racers will select '3' to keep pace with one another, and the third-place racer will select '4' and so gain ground on the others until he becomes the leader.

This analysis is flawed and incomplete; it doesn't take into account cases where two or all three racers are tied (which is likely).  I've read that in a zero-sum three-player game, Nash proved that there is always an equilibrium.  The way I've characterized it, this game is not zero-sum, so that theory, at least, doesn't apply.  It would be interesting to continue this analysis more thoroughly, and I find myself wishing I were formally trained in game theory to give the problem the analysis it warrants.

1. You have done very well with your game theory so far.

I want to let you know that there is no proof that a 3 player zero-sum game must have a Nash Equilibrium. Or, I should say, there do exist three player zero sum games with no Nash Equilibrium.

Part of what is making the 2nd game more complicated is that you are engaging in a game of repeated play.

Another thing that increases the complexity is that there is a 4th conditional statement that you are exploring--the condition over what is the difference in length between the players. Not only does this dramatically increase the number of permutations to solving the game, but it forces you to look at one of your assumptions about the players not in first place.

As a player am I indifferent about coming in 2nd or 3rd? The answer to that question alters the payouts in your payoff matrix.

(Also, let's say more than one player crosses the finish line, does that count as a tie or does the runner that goes further win?)

2. Excellent points, Aaron. As a player, my approach will change if I'm only one space behind the leader and two spaces from the finish line, as opposed to trailing by five spaces.

Exploring this topic has made me want to read up on game theory again. If you can recommend a good book on the topic, I'd be interested to know what it is.

3. Games of Strategy by Avinash Dixit and Susan Skeath.

There are many editions of the book so you will be able to get an older edition at a reasonable price.