A three-way bet

Question

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.

Answer 1

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}.")

Answer 2

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: 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: 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.