Which gun is Alice's best choice?

Question

Alice, Bob and Charles are involved in a deadly three way duel game.

Before the game starts, the referee prepares three guns for the players to choose from. She randomly picks three guns from a very large collection of guns whose hit probabilities are randomly distributed between $0$ and $1$. She then examines the hit probabilities of her picks, and honestly labels them "the best", "the mediocre" and "the worst" accordingly.

The players know how the referee picked and labeled the guns. But the guns' exact hit probabilities are only revealed to them AFTER they've made their choices. The game then begins with the following rules:

1. Each player takes turns to shoot. In your turn, you can either shoot at another player, or pass your turn.
2. To be fair, the player with the worst gun will go first, followed by the mediocre gun, and the best gun is the final one to shoot. This cycle is repeated until only one player survives.
3. Each player is intelligent, selfish and malicious. This means they calculate how to shoot to maximize their own surviving probabilities, but if shooting and passing give the same surviving probability, they would choose to shoot.

Given Alice is the only lady, she is allowed to choose her gun first.

Question: Which gun is her best choice? The best, the mediocre or the worst?

Hint：

It is never optimal for the mediocre or the best guns to pass turns.

---

Update: Without further constraints, the hint is not necessarily true. The "malicious" requirement in rule 3 seems insufficient. I didn't expect or intend that. I've provide a "bug version" (or lateral-thinking, depending on your perspective) solution in my answer. It seems the only way to avoid this is to change the rules and allow only the worst gun the right to pass.

Answer 1

Update: found the bug in my pass code that was skewing statistics. It didn't change my final answer, but the probabilities come in much, much closer. This also makes me think if I can work out an optimization for worst passing, it could catch that last percent difference and make it the best choice.

The answer is

The Mediocre!

I may or may not have written a simulation to test this several million times in different variations to help me...

If the worst passes every time, then mediocre still has a roughly 34% chance to win, compared to 32% and 33%.

Run 1:
The best's win count: 321451
The mediocre's win count: 344495
The worst's win count: 334054

Run 2:
The best's win count: 321761
The mediocre's win count: 343515
The worst's win count: 334724

Run 3:
The best's win count: 322009
The mediocre's win count: 343636
The worst's win count: 334355

and,

If the worst doesn't ever pass, mediocre has a roughly 48% chance to win, with the difference split between the other two options. This option should be eliminated as a possibility given the players ability to pick the optimal strategy (worst passing).

Run 1:
The best's win count: 260989
The mediocre's win count: 479366
The worst's win count: 259645

Run 2:
The best's win count: 261143
The mediocre's win count: 479403
The worst's win count: 259454

Run 3:
The best's win count: 260462
The mediocre's win count: 479958
The worst's win count: 259580

Code below for those who are curious/might have some input to improve.

<?php

    $o1_win_count = 0;
    $o2_win_count = 0;
    $o3_win_count = 0;
    $i=0;
    //$check1 = 0;
    //$check2 = 0;
    while($i < 1000000){
        $o1 = array('hc'=>0, 'status'=>"");
        $o2 = array('hc'=>0, 'status'=>"");
        $o3 = array('hc'=>0, 'status'=>"");
        $i++;
        $v1 = rand(0,10000)/10000;
        $v2 = rand(0,10000)/10000;
        $v3 = rand(0,10000)/10000;
        if($v1 > $v2 && $v1 > $v3 && $v2 != $v3){
            $o1['hc'] = $v1;
            if($v2 > $v3){
                $o2['hc'] = $v2;
                $o3['hc'] = $v3;
            }
            else{
                $o2['hc'] = $v3;
                $o3['hc'] = $v2;
            }
        }
        elseif($v2 > $v1 && $v2 > $v3 && $v1 != $v3){
            $o1['hc'] = $v2;
            if($v1 > $v3){
                $o2['hc'] = $v1;
                $o3['hc'] = $v3;
            }
            else{
                $o2['hc'] = $v3;
                $o3['hc'] = $v1;
            }
        }
        elseif($v3 > $v1 && $v3 > $v2 && $v1 != $v2){
            $o1['hc'] = $v3;
            if($v1 > $v2){
                $o2['hc'] = $v1;
                $o3['hc'] = $v2;
            }
            else{
                $o2['hc'] = $v2;
                $o3['hc'] = $v1;
            }
        }
        else{
            $i--;
            continue; //duplicate random values, restart this attempt
        }
        // o1 is "the best", o2 is "the mediocre", o3 is "the worst"
        while($o1['status'] == "" || $o2['status'] == "" || $o3['status'] == ""){
            $hit = rand(0,10000)/10000;
            //option 3 goes first, aims at option 1 if alive, 2 if 1 is dead, unless passing
            $pass = 0;
            //$diff1 = $o2['hc'] - $o3['hc'];
            //$diff2 = $o1['hc'] - $o2['hc'];
            /*if($o3['hc'] >= .32){ //change these out as desired, I was just doing guess and check to watch win count change for reference - could've missed possibilties in my guess and check
                $pass = 1;
            }*/
            $pass = 1;
            if($pass == 1){
                if($o2['status'] == "dead" || $o1['status'] == "dead"){ //skip as worst if all players in the game
                    if($o3['status'] != "dead" && $o3['hc'] >= $hit){
                        if($o1['status'] != "dead"){
                            $o1['status'] = "dead";
                            if($o2['status'] == "dead"){
                                $o3['status'] = "alive";
                                $o3_win_count++;
                            }
                        }
                        elseif($o2['status'] != "dead"){
                            $o2['status'] = "dead";
                            $o3['status'] = "alive";
                            $o3_win_count++;
                        }
                        else{
                            //shouldn't get here
                            $o3['status'] = "alive";
                            $o3_win_count++;
                        }
                    }
                }
            }
            else{
                if($o3['status'] != "dead" && $o3['hc'] >= $hit){
                    if($o1['status'] != "dead"){
                        $o1['status'] = "dead";
                        if($o2['status'] == "dead"){
                            $o3['status'] = "alive";
                            $o3_win_count++;
                        }
                    }
                    elseif($o2['status'] != "dead"){
                        $o2['status'] = "dead";
                        $o3['status'] = "alive";
                        $o3_win_count++;
                    }
                    else{
                        //shouldn't get here
                        $o3['status'] = "alive";
                        $o3_win_count++;
                    }
                }
            }
            $hit = rand(0,10000)/10000;
            //option 2 goes second, aims at 1 if alive, 3 if 1 is dead
            if($o2['status'] != "dead" && $o2['hc'] >= $hit){
                if($o1['status'] != "dead"){
                    $o1['status'] = "dead";
                    if($o3['status'] == "dead"){
                        $o2['status'] = "alive";
                        $o2_win_count++;
                    }
                }
                elseif($o3['status'] != "dead"){
                    $o3['status'] = "dead";
                    $o2['status'] = "alive";
                    $o2_win_count++;
                }
                else{
                    //shouldn't get here
                    $o2['status'] = "alive";
                    $o2_win_count++;
                }
            }
            $hit = rand(0,10000)/10000;
            //option 1 goes last, aims at 2 if alive, 3 if 2 is dead
            if($o1['status'] != "dead" && $o1['hc'] >= $hit){
                if($o2['status'] != "dead"){
                    $o2['status'] = "dead";
                    if($o3['status'] == "dead"){
                        $o1['status'] = "alive";
                        $o1_win_count++;
                    }
                }
                elseif($o3['status'] != "dead"){
                    $o3['status'] = "dead";
                    $o1['status'] = "alive";
                    $o1_win_count++;
                }
                else{
                    //shouldn't get here
                    $o1['status'] = "alive";
                    $o1_win_count++;
                }
            }

        }
    }

    echo "The best's win count: ".$o1_win_count."<br>";
    echo "The mediocre's win count: ".$o2_win_count."<br>";
    echo "The worst's win count: ".$o3_win_count."<br>";
?>

Answer 2

The answer is:

The Worst

Because:

Each player is intelligent and so they are likely to play tactically. This means that the worst and mediocre are likely to attack the best first, giving Alice (not knowing the hit probability) a 50% possibility of killing the mediocre. This does not guarantee Alice's survival but does decrease her chance of death by about 17.6%

Answer 3

I found a "bug" in this problem, not what I intended though. It seems with a very weak assumption, this problem (and by extension all similar three way duel problems), will admit a surprising solution. The assumption is

The players can see and remember who shot who.

Then the answer is

Alice can pick any gun and have a surviving probability of 100%!

Why? Because

Alice simply adopts a tit for tat strategy. She announces her strategy at the beginning of the game: Gentlemen, I'm vindictively dovish. I'll always pass my turns if nobody shoots me. But I'll keep shooting at whoever first shoot me until he or I am dead.

Why does this work?

When there're 2 players alive, {Alice, Bob} or {Alice, Charles}, if Bob and Charles have not shot Alice before, they'll just choose to pass every turn because unless they're 100% accurate, their shooting will make Alice fire back in case they miss, and decrease their survival rate to less than 100%. When all 3 players are alive, if Bob and Charles must shoot, they will want to shoot the person whose death gives them higher surviving probabilities. It is obvious that person can't be Alice. So they shoot each other, and when one of them dies, the survivor enters the blissful situation described above, surviving indefinitely. But wait! Who says they must shoot? They'll be fools if they do! As soon as Alice announced her strategy, the cunning Bob and Charles follow suit and announce the same strategy. A precarious balance by mutual threats is thus established in which nobody will venture to shoot.

Answer 4

The answer is

the Mediocre!

Because

A threeway-duel with turns, such as this, always ends up in a duel with turns. The worst gun is always in that duel as a bigger threat for the other two always exists. In most cases, the worst gun passes and ends up starting the duel. But sometimes the odds of facing the mediocre gun in the duel, even when the mediocre gun starts, are better than facing the best gun with the worst gun starting. Sometimes hitting the best gives better probabilities overall than missing/passing. This yields a set of probabilities for each gun picking. Iterating those pickings and adding the probabilities together gives the best educated guess of the gun that makes surviving (winning) most probable.

Results

Worst: 5151798.6976851 - 33.4%
Mediocre: 5481543.8630309 - 35.5%
Best: 4804657.4392835 - 31.1%
Worst shoots in 2756406 out of 15438000

Worst doesn't shoot
Worst: 5127133.1895262 - 33.2%
Mediocre: 5324462.4832485 - 34.5%
Best: 4986404.3272247 - 32.3%
Worst shoots in 0 out of 15438000

Worst shoots always
Worst: 3985277.060324 - 25.8%
Mediocre: 7396272.7532691 - 47.9%
Best: 4056450.1864092 - 26.3%
Worst shoots in 15438000 out of 15438000

first post (assuming naively that only comparison is against worst-best and mediocre-worst duels for the worst)
Worst: 5143589.5619746 - 33.3%
Mediocre: 5598586.3788909 - 36.3%
Best: 4695824.0591346 - 30.4%
Worst shoots in 4218360 out of 15438000

Proof

<?php

$inc=0.004;

/**
 * The worst gun can either wait for the two better guns to battle it
 * out and take the first shot at the winner in the duel that follows,
 *
 * or
 *
 * decide to shoot at the best and introduce a fork where when hitting
 * he will face the mediocre in a duel with the mediocre starting and
 * when missing have the same outcome as passing (ie get the first
 * shot). If the odds in the hits-best scenario are worse than in the
 * misses scenario he should pass, because
 *
 * Pworst * Pduel-vs-mediocre + (1 - Pworst) * Ppassing <= Ppassing
 * 
 * with all values of Pworst when Pduel-vs-mediocre <= Ppassing
 **/
function shouldWorstShoot($w,$m,$b){
 // probability of winning the whole battle after missing/passing
 $prob_missing = ($m/($m+(1-$m)*$b))*($w/($m+$w-$m*$w))+($b*(1-$m)/($m+(1-$m)*$b))*($w/($w+(1-$w)*$b));

 // probability of winning the battle after hitting the best
 // (i.e. duel against mediocre with mediocre starting)
 $prob_against_mediocre = ((1-$m)*$w)/($m+((1-$m)*$w));
 return $prob_against_mediocre>=$prob_missing;
}

/**
 * Duel: Worst fires first against mediocre
 *
 * updates the global win stats
 **/
function duelWorstMediocre($w,$m,$prob){
 global $worst_wins,$mediocre_wins;
 $tot = $w+((1-$w)*$m);
 $worst_wins+=($w/$tot)*$prob;
 $mediocre_wins+=(((1-$w)*$m)/$tot)*$prob;
}

/**
 * Duel: Worst fires first against best
 *
 * updates the global win stats
 **/
function duelWorstbest($w,$b,$prob){
 global $worst_wins,$best_wins;
 $tot=$w+((1-$w)*$b);
 $worst_wins+=($w/$tot)*$prob;
 $best_wins+=(((1-$w)*$b)/$tot)*$prob;
}

/**
 * Duel: Mediocre fires first against worst
 *
 * updates the global win stats
 **/
function duelMediocreWorst($m,$w,$prob){
 global $worst_wins,$mediocre_wins;
 $tot=$m+((1-$m)*$w);
 $mediocre_wins+=($m/($tot))*$prob;
 $worst_wins+=(((1-$m)*$w)/$tot)*$prob;
}


// these represent the combined odds of each of the gun position
// winning in every situation. They add up to number of pickings
$worst_wins=0;
$mediocre_wins=0;
$best_wins=0;

$worstShootsCount=0;
$n=0;
$a=[];
for($i=0.001;$i<=1;$i+=$inc){
 for($j=0.001;$j<=1;$j+=$inc){
  if($j===$i){
   continue;
  }
  for($k=0.001;$k<=1;$k+=$inc){
   if($k===$j||$k===$i){
    continue;
   }
   $n++;
   $a=[$i,$j,$k];
   sort($a);

   // only need to account for the first lap of 3way as others repeat
   $w_m_prob=0; // probablity of ending in worst-mediocre duel
   $m_w_prob=0; // mediocre-worst duel prob
   $w_b_prob=0; // worst-best duel prob

   $worst_shoots = shouldWorstShoot($a[0],$a[1],$a[2]);

   if($worst_shoots){
    $worstShootsCount++;
    $m_w_prob = $a[0]; // worst manages to hit -> m-w duel
    $w_m_prob=(1-$a[0])*$a[1]; // worst misses, mediocre hits -> w-m duel
    $w_b_prob=(1-$a[0])*(1-$a[1])*$a[2]; // worst misses, mediocre misses, best hits  -> w-b duel
   }
   else{
    $w_m_prob=$a[1]; // mediocre hits -> w-m duel
    $w_b_prob=(1-$a[1])*$a[2]; // mediocre misses, best hits -> w-b duel
   }
   $tot_prob = $m_w_prob + $w_m_prob + $w_b_prob; // normalize the odds
   duelWorstMediocre($a[0],$a[1],$w_m_prob/$tot_prob);
   duelMediocreWorst($a[1],$a[0],$m_w_prob/$tot_prob);
   duelWorstBest($a[0],$a[2],$w_b_prob/$tot_prob);
  }
 }
}
$tot = $worst_wins+$mediocre_wins+$best_wins;
echo str_pad("Worst:",14).str_pad($worst_wins,20)." - ".(round(1000*$worst_wins/$tot)/10)."%\n";
echo str_pad("Mediocre:",14).str_pad($mediocre_wins,20)." - ".(round(1000*$mediocre_wins/$tot)/10)."%\n";
echo str_pad("Best:",14).str_pad($best_wins,20)." - ".(round(1000*$best_wins/$tot)/10)."%\n";
echo "Worst shoots in ".$worstShootsCount." out of ".$n."\n";

Answer 5

Why not choose the

worst gun

and then

pass

Here's why:

The one with the best gun would then observe between the mediocre gun and the worse, or if the mediocre gun is next he would observe between the best and the worst. In both cases the one who's gun is better is doomed to be shot at. Then Alice can shoot her gun to the remaining person, and have a little more than half probability that she will live.