Coin Flipping Tournament… A Fun Game Theory Problem

[UprightCreature]

… or at least I find these things fun.

Imagine a heads up coin flipping tournament where each player starts with T100. There is some number of pre-determined rounds, in this case say 2. The players sit at the same table, but wager against the house not each other. At the beginning of each round each player secretly writes down an amount of their remaining stack to wager. This amount may be any real number >= 0 and <= the players T chips. Once all wagers are recorded they are revealed and each player flips a fair coin. If the player’s coin is tails they lose their wager. If the coin is heads they win 4 to 5 on their money. At the end of all rounds the person with the most T chips wins the tournament.

You’ll note that every wager a player makes is –EV, so to maximize ones T chip EV each round would be to always wager 0. This strategy however would result in losing the tournament 75% of the time against a halfway intelligent opponent that was aware of your strategy, and is clearly not the optimal strategy.

I think the problem is more interesting with more opponents and more rounds, but we can start with 2 people and 2 rounds.

What is the optimal strategy for this tournament?

[RocketManJames]

Just thinking out loud here... I don't really have an answer.

If you bet 0 for both rounds, then a thinking opponent wins 75% of the time, like you said. Because he can bet 10 in round 1, which gives him 108 or 90. And, he can then choose to wager 20 if he has 90 and 0 if he has 108. So, you've got the four outcomes: (100, 108), (100, 108), (100, 108), (100, 70).

What if you bet 0 and your opponent bets something greater than 0 in Round 1. Let's say he bets 10 in Round 1, and you bet 0. Then, after Round 1, you have 100 and opponent has 90 or 108.

He has 108. At this point, he will see you have bet nothing. If he chooses to stay at 108 by betting 0, then you will be 50% to win by betting more than 10 in this round. But, if he bets 100 at this point and have an outcome of 8 or 188. This would ensure that he'd be at 50% to win at worst or 75% to win at best (if you bet too much).

If he has 90, then you can bet 90 and be at worst 50% to win or best 75% to win (if he bets too much).

I guess I'm pretty stuck, so far in my line of thought, it's clearly not better than fifty-fifty against your opponent. I will keep thinking about this.

In Edit: I'm not sure how one player can get an edge over another player without knowing the other player's strategy or the probability the other player will employ a given strategy. The players make equivalent decisions and there's no postional advantage. Maybe I'm misunderstanding this a bit.

-RMJ

[d10]

Sounds like a simplified Black Jack tournament. I don't know much about BJ tourney strategy, but I imagine it would be similar.

[Siegmund]

Yes, this was a fun way to spend the afternoon instead of doing real work!


First, let's consider how the last round of such a tournament plays out, as a function of how many chips the two players have going into the last round.

take the size of underdog's stack as the unit of measurement.

Let R = (leader's stack) / (underdog's stack).

Let P be the house payoff rate on bets (in the OP's problem, P=0.8.)

Underdog will place a bet X, 0<=X<=1.
Leader places a bet Y, 0<=Y<=R.

There are four possible outcomes:

{W,L}: Leader wins his bet, underdog loses his bet: leader wins the tournament of course.

{W,W}: compare R+PY and 1+PX to see who wins the tournament.

{L,W}: compare R-Y and 1+PX to see who wins the tournament.

{L,L}: compare R-Y and 1-X to see who wins the tournament.

This divides the strategy space into up to four regions, as shown in the graph below, with leader's chance of winning the tournament ranging from 50% to 100%.



If R>1+P, the lower right region doesn't exist, and leader is guaranteed a win by betting 0 in the last round.

If (1+2P)/(1+P) < R < 1+P, leader will win 75% of the time. Leader places a bet slightly smaller than R-1 (between (1-R+P)/P and R-1 to be exact) and underdog places a bet large enough to make sure he doesn't fall in the 100% region - everything, for instance.

This is the situation illustrated in the graph, where choosing Y just under R-1 presents underdog with a "100% or 75%" choice.

If 1 < R < (1+2P)/(1+P), leader will win only 2/3rds of them time. In this case, R-1 on the left side of the graph is lower than (1-R+P)/P on the right side of the graph, so leader has no minimax force of 75% available.

In this case, underdog does best to bet everything 2/3 of the time and nothing 1/3 of the time, and leader does best to make a large bet (offering "50 or 75%") 2/3 of the time and a small bet (offering "100 or 50") 1/3 of the time.

---

Returning to the first round of the two-round tournament.

By symmetry, both players have a 50% chance to win the tournament if they play optimally.

If you bet 0 on the first round, you achieve that 50% equity. If your opponent bets 0 you are tied; if your opponent makes a small bet, you are equally likely to be a 2:1 underdog or 2:1 favorite in the final round. The same is true if both you and your opponent make small bets on the first round.

Making a large bet on the first round is an error. This can make bettor a 2:1 favourite if it wins but a 3:1 underdog if it loses, or a 3:1 favourite if it wins but a guaranteed loss if it loses. In the specific case in the original post, vs. a passing opponent, betting $37-44 risks being a 3:1 underdog, $45-69 risks a sure loss to no benefit, and $70+ risks a sure loss in exchange for a chance at being a 3:1 favorite.

So, my full strategy, if you ask me to play this game:

On round one, I pass. (Nothing bad can happen if you bet less than $18 on this round, but I choose to keep it simple.)

On round two, I still have $100.
If you have $55 or less, I win.
If you have $55 to $64, I bet nothing 1/3 of the time, and enough to beat you if you bet everything you have 2/3 of the time.
If you have $65 to $99, I bet (100-your stack)/(your stack), rounded down.
If you have $100, I pass.
If you have $101 to $155, I bet nothing 1/3 of the time, everything 2/3 of the time.
If you have $156 to $180, I bet everything.
If you have $181 or more, I win, and have you arrested for cheating.

[Jazza]

cool game, and well done seigmund for finding a Nash Equilibrium

[kyro]

Pretty easy if even I can get it...

Player 2 bets 1. If he wins, he bets 0 on the next flip. If he loses, he bets 2 on the next flip. The only way Player 1 beats him is if he loses both flips. Martingale system I believe it is called. Gonna make millions at Roulette!

[BettyBoopAA]

Pretty easy if even I can get it...

"Player 2 bets 1. If he wins, he bets 0 on the next flip. If he loses, he bets 2 on the next flip. The only way Player 1 beats him is if he loses both flips. Martingale system I believe it is called. Gonna make millions at Roulette!"

No player 1 adjusts to the result of player 2 results. Player 1 will always bet in round 2 under this scenario.

[kyro]

Figured it was too easy [img]/images/graemlins/tongue.gif[/img]. I assumed Player 1 bet 0 regardless of the circumstances...

[UprightCreature]

Nicely done.

The problem I haven't tried to tackle yet is the general case of n players and m rounds with a payout of p for each bet. Maybe I'll work on that this weekend.

[Skjonne]

[ QUOTE ]
...............On round one, I pass.

If you have $100, I pass............

[/ QUOTE ]

Nice work!

But it's not a fun game is it? Pass, pass, pass, pass, split pot [img]/images/graemlins/cool.gif[/img]