Friday, December 18, 2009

game theory anecdote

I've already mentioned the awesome sauciness of iTunes U: there's a lecture series of special interest to chess players (and business and science and poker folks): Ben Polak's Introduction to Game Theory.  You don't need iTunes to access this content. 

This gives me an excuse to recycle my chess-meets-Freakonomics story (an earlier version was told on the ICA message board last year).

Memorial Day Weekend 2008: I was walking around the lobby of the Westin Chicago North Shore in Wheeling, waiting for the round one pairings of the Chicago Open.  A grad student from the U of C School of Business waves a copy of Stephen Levitt's Freakonomics at me, explains that she's taking a course with Prof. Levitt, asks me if I was rated over 2000, and whether I wanted the chance to make some money in an experiment.  "Sure."

(Freakonomics is a very entertaining book on economics in nontraditional settings: it's a fun read, and you can get a taste of Levitt's approach to the world from his blog.)

Between rounds, I'm taken to a hotel room & seated at a computer terminal with a proctor there to read me instructions.  I was told that I would be playing against another ELO 2000+ guinea pig in another hotel room (that's what I was told: I don't know this for a fact).  My moves in all games were sent by computer, and my opponent's moves were communicated to me by the proctor.

Game 1: I am player 1 in a two-player game for $10.  On my turn, I am to name an integer between 1 and 9 inclusive.  Then Player 2 does the same.  We are to keep track of the running total of all integers.  (So if I say "9" & s/he says "8", the running total is 17.)  The first to get the running total to 100 wins.  (Do you see a winning strategy for either player?)

Game 2: Again, I am player 1 in a two-player game for $10.  The rules are the same as Game 1, except we're now allowed to name integers between 1 and 10 inclusive.  Again, the first to get the running total to 100 wins.

Here comes the spoiler....


Games 1 and 2 are variants of the game of Nim.  Game 1 is won by player 2 by force; Game 2 is won by player 1 by force (assuming correct play; and indeed we played correctly).

In game 1, player 2 simply picks a number that will bring the running total to 10, 20, etc. I immediately grumbled to the proctor that I was handed a lost position; she smiled & continued reading the instructions. Once I realized that player 2 understood the correct strategy in game 1, I tried to resign; the proctor asked me to play on. I kept choosing "1" to suggest to my unseen opponent that I knew s/he knew that s/he would win by force.

The winning move is Game 2 is for player 1 to choose "1" as the first move, then bring the running total to 12, 23, etc., with the subsequent moves (because 1 + [9 x 11] = 100). I suspect that these first two games were intended to be trivial, to make sure the chess players were capable of thinking in a certain mindset, and perhaps even to trick us into thinking in that mindset.

Which brings us to Game 3.

Game 3:  Again, I am player 1.  Each player can make a maximum of three alternating "moves" each: the moves are simply "Continue the game" OR "Stop the game."  Whatever Player 2's decision on Move 3, the game ends.

Here's the payoff matrix:

If stopped by player 1 on move 1
1 gets $4
2 gets $1

If stopped by player 2 on move 1
1 gets $2
2 gets $8

If stopped by player 1 on move 2
1 gets $16
2 gets $4

If stopped by player 2 on move 2
1 gets $8
2 gets $32

If stopped by player 1 on move 3
1 gets $64
2 gets $16

If stopped by player 2 on move 3
1 gets $32
2 gets $128

Else Game Ends and...
1 gets $256
2 gets $64

There is a certain logic to stopping the game immediately, taking the $4 for Game 3 (plus whatever earlier winnings one had), and saying goodbye.  In fact, I later found out that that's what NM Owechukwu Iwu did when he was Player 1 in this game.  (And he's beaten me in two consecutive Chicago Opens, so he knows a little bit about games.)

Here's the logic for stopping immediately.  Assume that the first five moves of the game are "continue."  Player 2 would have to be rather magnaminous to "tip" Player 1 by continuing the game at the end of Turn 3: the game must then end immediately anyway, and Player 2 would only get $64 instead of $128.  If Player 1 knows that Player 2 will end on Turn 3, then Player 1 will end on Turn 3, which means that Player 2 should end on Turn 3, which means that Player 1 should end on Turn 2...etc.  (Keep in mind that the experimenters have done their best to prevent collusion between the players: the "grandmaster draw" or thrown game is not an option.)

It is my strong personal opinion that (given this particular payoff matrix), this extremely logical analysis is sub-optimal because we're not playing a zero-sum game.  In fact, the University of Chicago Grad School is injecting cash into the game with every move.  (After a very long pause, I moved "continue".  The game concluded: Player 2: "continue," Me: "continue"; Player 2: "stop."  So I lost and received $8 for Game 3; while my opponent received $32.

What do you think the grad students were looking for?  And why were they testing chess players?

No comments: