6
$\begingroup$

Alice, Bob and Carole are playing a betting game. At the beginning, they have 20 chips in the common pot. They move alternatively in the order of Alice, Bob and Carole. In their move, a player announces a number $M$ and toss a fair coin: if head, $M$ more chips are added to the pot; if tail, $M$ chips are removed from the pot, where $1\leq M\leq$ the current # of chips in the pot.

The game continues until either

  1. The pot is empty. In which case the one who empties the pot is the loser, and the other two are the winners.
  2. The pot contains 100 or more chips. In which case everyone wins.

No communication is allowed before or during the game. Everyone wants to maximize their own winning probability.

Question: What strategies should Alice, Bob and Carole adopt? What're their winning probabilities?


Hint:

If you think you have found a neat and simple strategy for everyone, think again.

$\endgroup$
4
  • 6
    $\begingroup$ This kind of games among three or more players always have an ambiguity: what is the behavior of a player, if he/she is facing multiple choices which all lead to the same maximal winning probability for him/herself, but have different winning probabilities for the other two players? Sometimes it can be proved that this situation does not occur, but a priori this ambiguity always exists. Which case do we have here? $\endgroup$
    – WhatsUp
    Jul 5 at 20:16
  • 2
    $\begingroup$ Since we cannot lose if it's not our turn, seems like betting N-1 or N-2 might be the best. Trying to make others end the game. $\endgroup$
    – justhalf
    Jul 6 at 4:43
  • 2
    $\begingroup$ @justhalf But don't forget that if there are enough coins, maybe betting to win with 100 coins is better. For example, if we have 99 coins, and I bet one, then even if I lose, the next player has a chance to win by betting 2. Even if they lose, the next has a chance to win by betting 4. And even if they lose, I have another chance to win by betting 8, and so on. Conversely, if I bet 98 originally, I win 50% of the time on the next person's turn. But otherwise, there is a chance that I end up being faced with a single coin much sooner than the alternative. $\endgroup$
    – Trenin
    Jul 6 at 13:30
  • $\begingroup$ Thought I was getting somewhere, but I feel this might need a simulation instead. $\endgroup$
    – Trenin
    Jul 7 at 18:35
2
$\begingroup$

Edit: I started out trying to get a formal proof of optimality, but abandonded that. I leave the work here for someone else to continue if they see any merit. I did run some simulations if anyone wants to come up with a strategy they will have to do better than this.

There are two ways to win as stated in the puzzle;

  1. Everyone wins if you get 100 coins
  2. If one person loses by running out of coins on their turn, then the other two win.

Win By Knockout

This happens when one person bets all the remaining coins and loses. Obviously, if there is more than 1 coin, it would be silly to bet it all because you'd have a 50% chance of losing outright.

Betting all but one seems like a good choice. It maximises the chances of a quick win because if you lose, the next person losing means the game is over. If you win, and the next two people lose, then you also win. The only time you lose is if there is a Win-Loss right before your turn, and you throw a tails. In fact, we can easily enumerate the possibilities of the next three tosses.

For the following, $P_X(N)$ is the probability of $X$ winning on Alice's turn with $N$ coins in the pot.

A  B  C  P_A  P_B  P_C 
T  T  T  Win  Lose Win
T  T  H  Win  Lose Win
T  H  T       P(1) 
T  H  T       P(N) 
H  T  T  Win  Win  Lose
H  T  H       P(N)
H  H  T       P(1)
H  H  H       P(N)
  • 3/8 times Alice wins, 1/8 Bob wins, and 2/8 Carole wins
  • 3/8 times it is Alice's turn again with multiple coins
  • 2/8 times Alice is faced with a potentially losing toss because she has only 1 coin left in the pot

This gives:

$$P_A(N)= \frac{3}{8} + \frac{3}{8}P_A(N) + \frac{2}{8}P_A(1)$$ $$8P_A(N) = 3 + 3P_A(N) + 2P_A(1)$$

We can also get Bob and Carole's chances too.

$$P_B(N) = \frac{1}{8} + \frac{3}{8}P_B(N) + \frac{2}{8}P_B(1)$$ $$5P_B(N) = 1 + 2P_B(1)$$ $$P_C(N) = \frac{2}{8} + \frac{3}{8}P_C(N) + \frac{2}{8}P_C(1)$$ $$5P_C(N) = 2 + 2P_C(1)$$

Lets explore $P_A(1)$. If she throws tails, then she loses. If not, then the game continues. Lets do the next three throws;

A  B  C  P_A  P_B  P_C 
T  T  T  Lose Win  Win
T  T  H  Lose Win  Win
T  H  T  Lose Win  Win 
T  H  H  Lose Win  Win 
H  T  T  Win  Win  Lose
H  T  H       P(N)
H  H  T       P(1)
H  H  H       P(N)

Thus:

$$P_A(1)= \frac{1}{8} + \frac{1}{8}P_A(1) + \frac{2}{8}P_A(N)$$ $$7P_A(1) = 1 + 2P_A(N)$$ $$P_B(1)= \frac{5}{8} + \frac{1}{8}P_B(1) + \frac{2}{8}P_B(N)$$ $$7P_B(1) = 5 + 2P_B(N)$$ $$P_C(1)= \frac{4}{8} + \frac{1}{8}P_C(1) + \frac{2}{8}P_C(N)$$ $$7P_C(1) = 4+2P_C(N)$$

Substituting back in, we can solve for both $P_A(1)$ and $P_A(N)$.

$$P_A(1) = \frac{11}{31}, P_A(N) = \frac{23}{31}$$

Thus, Alice will have a 71% chance of winning using this strategy from the start.

We can work out the chances for Bob and Carole as well.

$$P_B(N) = \frac{17}{31}, P_B(1) = \frac{27}{31}$$ $$P_C(N) = \frac{22}{31}, P_C(1) = \frac{24}{31}$$

So when it is Alice's turn with a single coin, she has the lowest chance of winning ($\frac{11}{31}$) while the other two have greater chances. Bob, in fact, has only a $\frac{4}{31}$ chance of losing at this point! It makes sense because there is a 50-50 chance of Bob winning right away, and even if Alice stays alive with heads, Bob still gets a chance to force Carole into a bad spot. It takes 4 turns before there is even a possibility of Bob losing.

However, when it is Alice's turn with multiple coins, you can see she has the best chance of winning. Bob has the worst because he may be forced to bet everything on his turn. Carole is only marginally worse, likely because there is a chance she could lose before Alice gets a second turn.

CAVEAT This does not take into account the pot doubling on each heads toss and exceeding 100, which also counts as a win.

Other strategies

There is some merit to say leaving 2 coins for the next player. If the others follow the same strategy, you are guaranteed to not lose on your next turn, but you may be left with only 2 coins, and potentially forcing the next player into the tough spot. It is easy to see that this strategy makes the game last longer, and the longer it is, the more random chance is involved. Perfectly random length games will favour each player the same, so your chances should tend towards $\frac{2}{3}$. However, here is the analysis to show this strategy isn't as good as the other.

We need three tables, one for $P(N)$, $P(2)$, and $P(1)$.

Lets start with $P(N)$.

A  B  C  P_A  P_B  P_C 
T  T  T  Win  Win  Lose 
T  T  H       P(2)
T  H  T       P(2) 
T  H  H       P(N) 
H  T  T       P(1)
H  T  H       P(N)
H  H  T       P(2)
H  H  H       P(N)

So we get the following three equations:

$$5P_A(N) = 1 + P_A(1) + 3P_A(2)$$ $$5P_B(N) = 1 + P_B(1) + 3P_B(2)$$ $$5P_C(N) = P_C(1) + 3P_C(2)$$

Now lets look at $P(2)$.

A  B  C  P_A  P_B  P_C 
T  T  T  Win  Lose Win 
T  T  H  Win  Lose Win
T  H  T       P(1) 
T  H  H       P(N) 
H  T  T       P(1)
H  T  H       P(N)
H  H  T       P(2)
H  H  H       P(N)

Yielding: $$7P_A(2) = 2 + 2P_A(1) + 3P_A(N)$$ $$7P_B(2) = 2P_B(1) + 3P_B(N)$$ $$7P_C(2) = 2 + 2P_C(1) + 3P_C(N)$$

Lastly, $P(1)$.

A  B  C  P_A  P_B  P_C 
T  T  T  Lose Win  Win 
T  T  H  Lose Win  Win
T  H  T  Lose Win  Win
T  H  H  Lose Win  Win
H  T  T  Win  Win  Lose
H  T  H       P(2)
H  H  T       P(2)
H  H  H       P(N)

Which gives:

$$8P_A(1) = 1 + 2P_A(2) + P_A(N)$$ $$8P_B(1) = 5 + 2P_B(2) + P_B(N)$$ $$8P_C(1) = 4 + 2P_C(2) + P_C(N)$$

Solving, we get the following: $$P_A(1)=\frac{5}{13}, P_A(2)=\frac{9}{13}, P_A(N)=\frac{9}{13}$$ $$P_B(1)=\frac{11}{13}, P_B(2)=\frac{9}{13}, P_B(N)=\frac{7}{13}$$ $$P_C(1)=\frac{10}{13}, P_C(2)=\frac{8}{13}, P_C(N)=\frac{10}{13}$$

Since $\frac{9}{13} \lt \frac{23}{31}$, this strategy is inferior for Alice to use on her turn when she has more than 2 coins.

Winning Co-operatively

There is another way to win. If there are sufficient coins, then they can work together to bet the minimum each time. For example, if there are 95 coins, Alice can bet 5, and everyone wins on heads. If not, then Bob can bet 10 and everyone wins. There would need to be 4 failures in a row before there wouldn't be a chance to win again. In fact, if there was a strategy to guarantee this method, then everyone would use it because there is no way anyone can lose with it.

So the question becomes, at what point does this strategy win out over the previous?

Well, lets say that if Alice loses her current toss, then Bob player cannot win co-operatively. Bob would revert to the other strategy and bet all but 1 coin. If Bob loses, Alice has a decent shot at winning because Carole will be betting the last coin. If Bob wins, then he would put the pot higher than the original amount, and thus Carole would be playing the co-operative strategy again. So there isn't much downside to playing co-operatively.

This yields the following strategy:

  • If the pot has 51 coins or more, then bet $100-pot$.
  • Otherwise, bet $pot-1$

Results

Simulations show that the competitive strategy of always betting all but 1 coin gives Alice a 77.6% chance of winning. Of all the games, only 13.2% of them result in everyone winning.

However, the composite strategy of playing cooperatively and only betting enough to win when there are lots of coins yeilds a much better result for Alice at 84%. The number of games where everyone wins also increases to 20%.

Python Code

import sys
import random
import math

WINS=[0,0,0]
POT = 20
TRIALS = int(sys.argv[1])
losses = 0

for trial in range(TRIALS):
    # We will run a simulation of the game.
    pot = POT
    turn = 2
    while pot > 0 and pot < 100:
        # Advance to the next turn.
        turn = (turn + 1) % 3
        # The bet will be just enough to win, otherwise all but 1.
        bet = max(min(100-pot, pot-1),1)
        if random.getrandbits(1):
            # The bet was a win!
            pot += bet
        else:
            # The bet was a loss.
            pot -= bet
    # Everyone gets a win...
    WINS[:]=[wins+1 for wins in WINS]
    if pot == 0:
        losses += 1
        # ...except whoever just lost
        WINS[turn] -= 1

# Display the wins
print(f"The wins are: {WINS} and losses are {losses}.")
$\endgroup$
10
  • $\begingroup$ Shouldn't the threshold be higher than 51? If Alice has 51 coins and loses, Carole won't be able to play cooperatively even if Bob wins. $\endgroup$
    – Eric
    Jul 8 at 0:51
  • 2
    $\begingroup$ @Eric I am feeling dense right now. If Alice has 51 coins and loses, then she will have bet 100-51=49 coins. It will be Bob's turn with 2 coins. So yes, at this point the strategy switches. Cooperative play is only valid if the number of coins in the pot is greater than 50, allowing for a quick win. At least in my "solution". It could be there is a better strategy, but I don't see it right now. $\endgroup$
    – Trenin
    Jul 8 at 12:13
  • 1
    $\begingroup$ @Trenin 51 coins is an interesting case since you could simultaneously operate with both competitive and cooperative strategies by betting 50. $\endgroup$
    – Gilbert
    Jul 9 at 20:43
  • $\begingroup$ @Trenin according to your simulations, how often does the 51 state occur? $\endgroup$
    – Gilbert
    Jul 10 at 1:42
  • 1
    $\begingroup$ @Gilbert In a co-op bet, the bet is $100-N$ where $N$ is the size of the pot. A win means game over. A loss and the pot loses this amount. The new pot is $N-(100-N) = 2N-100$. This number is always even. On a competitive bet, the bet is $N-1$. A loss leaves a single coin. A win and the pot is $N+N-1=2N-1$. This number is always odd. Working backwards, we can determine the bets necessary to get there. 1>2>3>5>9>17>33>65>30>59>18>35>69>38>75>50>99>98>96>92>84>68>36>71>42>83>66>32>63>26>51 So, it takes $2^{30}$ bets going exactly right to get there after getting to a single coin. $\endgroup$
    – Trenin
    Jul 20 at 19:59
0
$\begingroup$

Let's say there're $K\gt 50$ chips in the pot and it's your move. The drama of the game is this: should you adopt the selfish strategy of betting $K-1$, or the cooperative strategy of betting $100-K$? I claim there exists an Nash equilibrium for this game, and in that equilibrium the threshold number of chips for cooperation to happen is

67

To see why, suppose the other two players are both observing the 67-rule mentioned above, and you have 67 chips. If you also adopt the 67-rule, the game would be played out like this for you:enter image description here so your losing probability would be $\frac{1}{8}P(2)+\frac{1}{8}P(34)$, where $P(x)$ is your losing probability when you have $x$ chips in pot.

But if you adopt the selfish strategy, the game would be like this:enter image description here so your losing probability would be $\frac{1}{8}P(3)+\frac{1}{8}P(1)$. Notice that $P(3)$ is only slightly smaller than $P(2)$, while $P(34)$ is much smaller than $P(1)$. This means you have a lower losing probability by observing the 67-rule.

In a similar fashion, the reader can verify that if $K\geq 76$, at equilibrium everyone will adopt the cooperative strategy. If $67\leq K\lt 76$, there're 2 equilibria: all be selfish or all be cooperative. If $K\lt 67$, at equilibrium everyone will be selfish.

$\endgroup$
1
  • $\begingroup$ Where does 67 come from? You've stated it is the threshold, but what makes it different from 66? Or 68? $\endgroup$
    – Trenin
    Jul 26 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.