Ponder This Challenge - February 2006 - Random [0,1] poker game

Ponder This Challenge:

Puzzle for February 2006.

This month's puzzle is about a simple 2 player poker like gambling game. The two players each ante 1 unit to a pot. Then each player receives a random number uniformly distributed between 0 and 1. Each player knows the value of his number but not the value of his opponent's number. The first player is then given an opportunity to bet one additional unit. If the first player doesn't bet there is a showdown and the player with the highest number collects the antes. If the first player bets the second player may call by matching the bet or drop out (giving the antes to the first player). If the second player calls there is again a showdown and the player with the highest number collects the pot (consisting of 4 units, the bets and the antes). If both players follow their optimal strategy what is the value of the game? In other words if they play (optimally) a large number of games how much is the first player expected to win (or lose if the value is negative) per game?

The first 100 people who answer correctly will be listed. The answer will be posted a week after the 100th is received, or at the end of the month.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  I came up with this problem and solution myself. However a reader points out that this model of poker has been solved before. It is usually attributed to Von Neumann (see Theory of Games and Economic Behavior by Von Neumann and Morgenstern, sections 19.14.1-19.16.2).

  Answer:

  We show below that the value of the game is .1.

  Let the first player's number be x, the second player's be y. Suppose the second player follows a strategy of calling when y>p and folding otherwise (for some parameter p between 0 and 1). Suppose the first player knows p, then what should he do.

  Suppose first x<p.

  If the first player does not bet he will win 1 unit a fraction x of the time and lose 1 unit a fraction (1-x) of the time.So his expectation is x-(1-x) or 2*x-1.

  If the first player bets he will win 1 unit if not called but lose 2 units if called. So his expectation is p-2*(1-p)=3*p-2.

  So the first player should bet if (3*p-2) > (2*x-1) (or x <(1.5*p-.5) ) and not bet otherwise.

  Suppose next x>p.

  As above if the first player does not bet his expectation is 2*x-1.

  If the first player bets he will win 1 unit if not called, 2 units if called with p<y<x but lose 2 units if called with x<y<1. so his expectation is p+2*(x-p)-2*(1-x) or 4*x-p-2.

  So the first player should bet if (4*x-p-2) > (2*x-1) (or x >(.5*p+.5) ) and not bet otherwise.

  So putting the cases together the first player should bet when x < (1.5*p-.5) or x > (.5*p+.5) and not bet otherwise. Next we compute the first player's expectation.

  Suppose first p < 1/3. Then for 0 < x < (.5*p+.5) the first player doesn't bet. His expectation is 2*x-1 which averaged over the interval is .5*p-.5. The interval has length .5*p+.5 so the total expectation for the no bet case is .25*p*p-.25. For .5*p+.5 < x < 1 the first player bets with expectation 4*x-p-2 which averaged over the interval is 1. The interval has length -.5*p+.5 so the total expectation for the bet case is -.5*p+.5. Combining the bet and no bet cases the total expectation is .25*p*p-.5*p+.25.

  Suppose next p > 1/3. Here we have 3 intervals. For 0 < x <(1.5*p-.5) the first player bets with expectation 3*p-2. This interval has length 1.5*p-.5 so the total expectation for this interval is4.5*p*p-4.5*p+1. For 1.5*p-.5 < x < .5*p+.5 the first player does not bet with expectation 2*x-1 which has average value 2*p-1 on the interval. This interval has length 1-p so the total expectation for this interval is -2*p*p+3*p-1. Finally for .5*p+.5 < x < 1 the first player bets. As above the total expectation for this interval is-.5*p+.5. Combining the three intervals the total expectation is 2.5*p*p-2*p+.5.

  Hence the expectation of the first player is .25*p*p-.5*p+.25(p < 1/3), 2.5*p*p-2*p+.5 (p > 1/3). This expectation is minimized when p=.4 where it has value .1. Hence the value of the game is at most .1 since the second player can limit the value to at most .1 by calling when y>.4 and folding otherwise. The first player's strategy in this case is to not bet for .1<x<.7 and bet otherwise. Suppose the second player knows the first player is following this strategy. The nit is easy to see that if the first player bets the second player should fold if y<.1, is in different between calling and folding for.1<y<.7 and should call when y>.7. So the second player can not do better than calling whenever y>.4 which leaves the first player an expectation of .1. Hence the value of the game is at least .1. This means the value of the game is exactly .1.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• Eugene Vasilchenko (02.02.2006 @12:06:30 PM EDT)
• Joe BGI SF Fendel (02.02.2006 @01:14:05 PM EDT)
• Claudio Bartolini (02.03.2006 @07:38:45 PM EDT)
• Joseph DeVincentis (02.03.2006 @08:16:12 PM EDT)
• Daniel Bitin (02.04.2006 @06:13:41 PM EDT)
• Patrick J. LoPresti (02.05.2006 @03:28:10 PM EDT)
• Joe Schauder (02.06.2006 @07:23:52 AM EDT)
• Giorgio Antonelli (02.06.2006 @03:12:12 PM EDT)
• Adrian Groves (02.06.2006 @07:04:44 PM EDT)
• Yizhou Liu (02.07.2006 @12:49:47 AM EDT)
• James Dow Allen (02.07.2006 @01:09:58 AM EDT)
• Don Coppersmith (02.08.2006 @08:55:56 AM EDT)
• Frank Yang (02.08.2006 @11:23:19 AM EDT)
• Deron Stewart (02.08.2006 @01:46:07 PM EDT)
• David McQuillan (02.08.2006 @03:08:50 PM EDT)
• John Hart (02.09.2006 @03:29:16 AM EDT)
• Dave Parashar (02.09.2006 @04:39:22 AM EDT)
• Mark Pilloff (02.10.2006 @09:14:08 PM EDT)
• Phil Muhm (02.12.2006 @08:08:47 PM EDT)
• Dmitry Litvinenko (02.13.2006 @03:49:29 AM EDT)
• James Boyce (02.13.2006 @05:19:42 PM EDT)
• Adel El-Atawy (02.14.2006 @01:06:48 PM EDT)
• Dave Biggar (02.14.2006 @01:41:44 PM EDT)
• Malcolm J. Powell (02.16.2006 @12:43:32 PM EDT)
• Immanuel Litzroth (02.16.2006 @05:38:33 AM EDT)
• Chris Messer (02.18.2006 @05:40:07 PM EDT)
• Wolf Mosle (02.22.2006 @08:42:00 PM EDT)
• Ed Sheppard (02.23.2006 @04:45:01 PM EDT)
• Christopher Quayle (02.24.2006 @08:59:59 AM EDT)
• Frank Mullin (02.24.2006 @11:19:59 AM EDT)
• Kerry M. Soileau (02.24.2006 @05:44:32 PM EDT)
• Dharmadeep Muppalla (02.25.2006 @09:05:37 AM EDT)
• Mike Szydlo (02.26.2006 @01:28:31 AM EDT)
• Wei Wu (02.26.2006 @08:33:55 PM EDT)
• John G. Fletcher (02.26.2006 @11:08:09 PM EDT)
• Du Yang (02.27.2006 @05:12:54 AM EDT)
• Forest C Deal (02.27.2006 @12:41:34 PM EDT)
• Shmuel Menachem Spiegel (02.27.2006 @11:34:46 PM EDT)