Communications of the ACM
Last byte
Roulette Angel
Credit: Getty Images
In the rules of roulette, all payouts are as if there are 36 possibilities. So if you bet a single chip on a single number and you win, you receive 36 chips in total (35 plus the one you put in). So, for example, if you put a chip on each of the 36 non-zero numbers and it hit one of those, then you would break even. However, there is also a 0 (and in some casinos a 00). It is possible to get 36 to 1 odds on those, but the point is that there are at least 37 or 38 possibilities. So you have a negative expected value at the game.
Two strangers Bob and Alice receive the following proposition from an eccentric, wealthy, and honest (nearly angelic) benefactor named, well, Angel.
Angel says: There is a fair roulette wheel with a 0 but no 00. I will give you each 36 chips each worth $1. First Alice will place her bets and then Bob will place his (so he can see Alice's). If at the end of the payout from the roll, the two of you have the same number of chips, I disappear and you will never see me again. If one of you has more, that person gets $10,000. The other gets nothing.
Warm-Up: Alice reasons that all bets have a negative expected value, so she bets nothing. What can Bob do to maximize his chance of winning the $10,000 and what are his odds?
Solution to Warm-Up: If Bob bets nothing, the result will be a tie, so Bob will receive nothing. Suppose that instead Bob bets on 35 numbers. That is he retains one chip and bets all the others. He has a 35/37 chance of winning on one of his numbers for which he will receive 36 chips. Because he kept one in reserve, he will have 37 chips in total and will win.
Figure. Sometimes, it is not important to beat the house, just to beat the stranger.
OK, now for some challenges for you.
Question: What if Alice had chosen Bob's strategy in the solution to the warm-up, viz. one chip on 35 of the 37 numbers. What could Bob do to maximize his chance of winning?
Solution: Bob should bet on 34 numbers of the 35 numbers on which Alice bets and keep two chips. If the ball falls on any of those 34, he will have 38 chips altogether whereas Alice will have only 37. If the ball falls on any of the numbers that neither he nor Alice picked, he would have two chips, while Alice would have only one. So he would have a 36/37 chance of winning.
It is clearly a big advantage to go second. So, what if Angel changes the rules a little. Alice still goes first. Bob still sees which numbers Alice chooses, but Bob must bet strictly more chips than Alice unless Alice bets all 36 in which case Bob also must bet 36.
Question: With these new rules, what is an optimal strategy for Alice? What is an optimal counter-strategy for Bob in that case? What are the odds for each?
Solution: If Alice bets on 35 numbers, then Bob must bet on 36. If the ball rolls on any of Alice's numbers, she wins. Bob can arrange to bet on the two numbers Alice did not bet on and 34 of those that Alice did bet on. So Bob will win 2/37 of the time and Alice 35/37 of the time. If Alice bets on fewer numbers, then her winning probability will go down.
Angel thinks about this and decides this is too favorable to Alice if she can bet more than 18 and too favorable to Bob if he sees what she bets. So, Angel limits Alice to bet 18 or fewer.
Bob is told how many chips she has placed but does not know where. He must bet at least one more than she does.
Question: What is the best strategy for each player?
Solution: Alice should still place 18 on randomly chosen 18 out of 37. If Bob places 19, then roughly half will be on the same numbers that Alice used. If the ball rolls to any of those numbers, Alice will win as well. If the ball rolls to any of the numbers neither chooses, Alice will win. Bob will win only if the ball rolls to a number that only Bob has chosen. So a better strategy, no matter how many chips Alice bets is for Bob to bet all his chips.
Alice will win with probability k/37 if she places k chips and Bob will win with likelihood at least (36- k)/37.
If you figured these all out, congratulations. But the fun is just beginning.
Upstart 1: What if Angel makes the game symmetric? That is, each of Bob and Alice writes his or her bets on paper in secret and then an impartial judge places them. What is the best strategy for each player?
Upstart 2: What if the game of Upstart 1 is played in k rounds and the winner is determined by the player with the most chips at the end? If k is very large, then it is best to bet nothing. But we know that's not the best when k = 1. Of course, feedback may play a role. Each player may change behavior depending on his or her relative wealth compared to the opponent.
I do not know how to solve either of these problems, so I asked my friend Tim Roughgarden what he thought about the first one. Tim suggested: "You could model the 'no communication' version as a simultaneous-move two-player game and examine the Nash equilibria (presumably there are many, though, and might not be easy to characterize)."
Might not be easy…
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2021 ACM, Inc.
No entries found