View Single Post
  #4  
Old 05-25-2005, 09:19 PM
Siegmund Siegmund is offline
Senior Member
 
Join Date: Feb 2005
Posts: 415
Default Re: Coin Flipping Tournament… A Fun Game Theory Problem

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.
Reply With Quote