Five pirates splitting gold with a twist

Question

Source: This was posted on the Grey Labyrinth Forums many years ago.

The five pirates are back. But this time one of them has the dreaded Zanzibar fever, whose terrible effects are spelled out below.

• 300 gold coins need to be split between the five pirates.
• Same idea as the original: the oldest pirate proposes a split of the gold coins, and everyone votes. If more than half say yes, then that is how the coins are divided. Otherwise the oldest pirate is thrown overboard and the process is repeated with the remaining pirates. (Note the "more than half" which is different from the original version)
• The pirate infected with Zanzibar fever always acts fairly: she always proposes an even split between the remaining pirates, and only votes for such a proposal.
• Each pirate is equally likely to have Zanzibar fever, and no healthy pirate initially knows who has it.
• Voting is done by secret ballot.
• The other pirates are perfect logicians who always act to maximize their own expected earnings. If multiple strategies yield the same expected value, then they randomly select among them. For this puzzle, maximizing likelihood of survival or bloodthirstiness are not factors.

If the oldest pirate is fever-free, how should she propose to divide the gold?

---

Edit: I intended survival really not being a priority at all for the pirates, and that the secret vote only reveals if the plan was accepted or not, no other information. However, JS1 gives a great answer below to the case where survival is more important than any amount of money, and the secret ballot does reveal the number of yes / no votes.

Answer 1

Preliminary work that comes in handy later

Let's first solve without any Zanzibar fever:

1 pirate : 300
2 pirates: 300/dead (pirate 1 votes no)
3 pirates:   0/   0/ 300 (pirate 2 doesn't want to die, votes yes)
4 pirates:   1/   1/   0/ 298
5 pirates:   2/   0/   1/   0/ 297 (or 0/2/1/0/297)

Now let's solve assuming Zanzibar is still in play (and not the oldest pirate remaining):

1 pirate : 300
2 pirates: 150/ 150 (pirate 1 is Zanzibar)
3 pirates: 100/ 100/ 100 (get Zanzibar vote plus self)
                         (Any other split risks dying)
4 pirates: See below, tricky

And now let's solve for when the oldest pirate is the Zanzibar pirate:

1 pirate : 300
2 pirates: 300/dead
3 pirates: 100/ 100/ 100 (pirates 2&3 vote yes)

Notice that for 3 pirates, the result is a 100 split no matter which pirate is Zanzibar, as long as the Zanzibar pirate is still out there.

TL;DR

There are actually 2 solutions that follow. I first assumed that the secret ballot would cause the number of votes to be revealed. The first solution assumes that and the answer I came up with was: 80/80/0/0/140 with pirate 5 getting 140 coins.

Then the OP commented that the secret ballot should be completely secret with the vote count not revealed. Skip to the "parrot" part to read that solution. The final answer I came up with was: 93/93/0/0/114 with pirate 5 getting 114 coins.

Revealed vote count: the tricky part

Suppose there are four pirates, and the 4th is not the Zanzibar. The 4th pirate could propose any of these three:

4 pirates: 101/ 101/   0/  98
           101/   0/ 101/  98
             0/ 101/ 101/  98

Each way results in a 2/3 chance of dying, because you must offer 0 to the Zanzibar pirate to survive. Anything else results in only 1 yes vote other than your own. That isn't very good odds of survival. How about:

4 pirates:  75/  75/  75/  75

Now at first you may think that this will for sure result in a yes from the Zanzibar and two no's from the other pirates. However, if they think you are the Zanzibar pirate (this is a bluff), then recall that the outcome after the Zanzibar has been revealed is 0/0/300. Which means that pirates 1 and 2 might benefit from an even split and vote yes. But all pirates are smart and they know pirate 4 might bluff. So let's figure out how pirates 1-3 would vote knowing that pirate 4 will bluff 100% of the time.

If they all vote yes, the expected value is 75/75/75/75. If they all vote no, there are two cases:

1. Pirate 4 was the Zanzibar pirate (1/3 chance from the perspective of a non Zanzibar pirate 1-3). Votes turn out three no's indicating that only Pirate 4 could have been Zanzibar. Outcome is 0/0/300 because all three pirates realize that there are no Zanzibars left.
2. Pirate 4 was not the Zanzibar pirate. (2/3 chance). Votes turn out two no's one yes indicating that the Zanzibar pirate is still out there. This results in 100/100/100.

Total expected outcome: 66.7/66.7/166.7

So in fact pirate 1 and 2 will vote yes to a 75 split and pirate 4 should always bluff in order to keep themselves alive.

But wait, there's more!

The above assumed all pirates voted yes or no together. It looks like pirate 3 should always vote no. But what if pirates 1-2 only vote yes with probability p? This can help because they might get a yes/no split resulting in pirate 3 not knowing if the Zanzibar pirate is still out there (and not being able to propose 0/0/300). Let's go over the cases again:

1. Pirate 4 is the Zanzibar pirate. (1/3 chance)
    a) 3 no votes (1-p)^2 chance, 0/0/300
    b) 2 no 1 yes votes 2*p*(1-p) chance, 100/100/100 because now pirate 3 can't tell if the Zanzibar is still out there
    c) 1 no 2 yes, p^2 chance, 75/75/75/75
2. Pirate 4 is **not** the Zanzibar pirate (2/3 chance)
    a) Pirate 3 is Zanzibar (1/2 chance)
        a1) 2 no 1 yes votes (1-p)^2 chance, 100/100/100
        a2) 2 or 3 yes votes 1-(1-p)^2 chance, 75/75/75/75
    b) Pirate 3 is not Zanzibar
        b1) 2 no 1 yes votes (1-p) chance, 100/100/100
        b2) 2 yes 1 no votes p chance, 75/75/75/75

To make a long story short, the above simplifies to the expected value of pirates 1 and 2 being:

P1 = P2 = -(100/3)p^2 + (125/3)p + 200/3

Solving for maximum P1 gives p = 5/8. This results in the following expected values for each pirate:

P1 = 79.6875
P2 = 79.6875
P3 = 93.75
P4 = 46.875 (3/8 chance of dying btw)

And finally we reach pirate 5

Now we know that P4's best bet is to propose 75/75/75/75 with P1 and P2 voting yes with 5/8 probabilty and P3 voting no always (except for whichever is the Zanzibar pirate of course). This results in the aforementioned split of:

79.7/79.7/93.8/46.9 (with a chance of dying)

So now, P5 needs to propose: 80/80/0/0/140

This will get votes from P1, P2, P4, and P5, minus whichever might be the Zanzibar pirate (still 3 votes to gain the majority). Note that P4 will vote yes to getting 0 gold because otherwise they run a 3/8 chance of dying.

Notes

I assumed that by "secret ballot", this meant that the votes would be put into a ballot box without anyone being able to determine who voted which way, but that the ballots would be read aloud so that the number of yeses and no would be public information.

The original question said that maximizing chances of surviving wasn't a factor, but in my answer it was, so I'm not sure whether I did something wrong. Maybe someone can double check my math, or the OP can comment on that part of it.

I went and looked at the Grey Labyrinth forums and no one came close to suggesting the answer I gave. So I don't think they ever found the real answer over there. Is there another origin for the puzzle?

Starting Over... With a Parrot

The OP claimed in a comment that the secret ballot was truly secret, with a parrot counting the votes. So given that fact, P4's proposed 75 split will fail because the other pirates will prefer that 3 pirates remain which results in 100/100/100. So we go back to P4 proposing one of three choices:

101/101/0/98
101/0/101/98
0/101/101/98

In 2/3 of the cases, P4 will die with the result:

100/100/100/dead

In 1/3 of the cases, P4 will stay alive with the average result:

67.3/67.3/67.3/98

So the full range of possibilities from a non-Zanzibar P1-P3 point of view:

1. P4 was the Zanzibar (1/3 chance): 100/100/100/dead. Even though only the Zanzibar would commit suicide by proposing an even split, P3 can't actually take the chance of proposing 0/0/300 because P4 could have been bluffing. Because if P3 proposed 0/0/300 with any chance, then P4 should start bluffing with some chance.
2. P4 was not the Zanzibar (2/3 chance)
   a) P4 chose badly (2/3 chance): 100/100/100 (asterisk - see below)
   b) P4 chose well (1/3 chance): 67.3/67.3/67.3/98

The expected outcome from a non-Zanzibar P1-P3 point of view:

92.74/92.74/92.74/21.78

The expected outcome from a non-Zanzibar P4 point of view is different:

1. P4 chose badly (2/3) chance: 100/100/100/dead
2. P4 chose well (1/3) chance: 67.3/67.3/67.3/98

89.1/89.1/89.1/32.7 with a 67% chance of death

So the full expected outcome for each non-Zanzibar pirate from his own point of view (which doesn't necessarily add to 300 because each pirate has information about himself):

92.74/92.74/92.74/32.7 with a 67% chance of death

Given the above, pirate 5 should propose: 93/93/0/0/114

Again, pirates 1,2,4,5 vote for the proposal with one of them possibly not doing so if they are the Zanzibar pirate. Pirate 4 votes yes even with 0 gold to avoid death.

Equivalent proposals are 93/0/93/0/114 and 0/93/93/0/114.

Asterisk - Information Leakage

The asterisk from above is because once P4 chooses badly and dies, the other pirates gain some information: the pirate P4 chose to give 0 to must not be the Zanzibar pirate. Therefore, the results might not always be 100/100/100 after that. Here are the possible results:

If P3 is not the Zanzibar:

1. 101/101/0: Either P1 or P2 is the Zanzibar. P3 must propose 100/100/100 and it will pass. (2/6 chance)
2. 101/0/101: P3 knows P1 is the Zanzibar but P2 doesn't yet. P3 can offer 0/151/149 because P2 will realize P1 is the Zanzibar and know that 151 is better than the 150 he could get if he voted no. (1/6 chance)
3. 0/101/101: P3 knows P2 is the Zanzibar. P3 must offer 100/100/100 otherwise both P1 and P2 will refuse. (1/6 chance)

If P3 is the Zanzibar:

1. 101/0/101: P3 offers 100/100/100. P1 knows that P3 is the Zanzibar and votes no. P2 votes yes though to pass the proposal. (1/6 chance)
2. 0/101/101: P3 offers 100/100/100. P2 knows that P3 is the Zanzibar and votes yes otherwise P2 will get killed. (1/6 chance)

Notice the one case where the outcome is 0/151/149. This results in P1 getting less than P2 and P3 overall (about a 83/108/108 split). But now P1 should choose a mixed strategy. With a low probability p, he can vote the wrong way. Given this mixed strategy, P3 can no longer afford to offer 0/151/149 in the one case above because with probability p, the assumption could be wrong leading to P3's death. P1 can choose p so small that it doesn't affect anyone's expected outcome. However, just the possibility of voting the wrong way deters P3 from deviating from the 100/100/100 strategy. So now all cases lead to a 100/100/100 split.

Answer 2

$ \newcommand{\vec}[1]{\begin{pmatrix} #1 \end{pmatrix}} $

Call the pirates P,Q,R,S,T in order, with P oldest and healthy. Treat the term "expected earnings" as the "expected number" in probability: given a set of non-overlapping states $s_i$ with corresponding probabilities $p_i$ such that $\sum p_i = 1$, and given a payout $n_i$ in a given state $s_i$, the expected number is given by $\sum p_i n_i$. Use the notation $E_n(\mathbf{x})$ to mean the expected earnings of the pirates named in $\mathbf{x}$ when there are only $n$ pirates remaining.

The states correspond to the person with the fever - denote them $F_Q, F_R, F_S, F_T$. To get the expected earnings $E_{k+1}$, calculate the expected earnings in each state based on $E_{k}$ and weight them by the probability of that state. The question, of course, is what the probabilities are. This could be tricky, since pirates can pretend to be fevered, and prior proposals and answers can indicate or preclude fever. Here, however, we are considering the probabilities from the point of view of P before any pirate has made a proposal. At this point, all 4 states are equally likely, so the probabilities of the four states must be equal, i.e. each probability is 1/4.

Start with the youngest pirate and build up from there.

T: T gets 300 coins. $E_1(T) = 300$.

ST: "more than half" means "unanimous" for 2 voters. In the state $F_T$, S must propose 150:150 to retain 150 coins. In any other state, T will always say no. $$E_2 \vec{S\\T} = \frac{1}{4} \vec{150\\150} + \frac{3}{4} \vec{0\\300} = \vec{37.5\\262.5}$$

RST: R needs 1 more vote. In $F_R$, R proposes an even split, which S accepts. In $F_S$, R's cheapest option is also an even split. In $F_Q$ and $F_T$, R's cheapest option is to propose 262:38:0. $$E_3 \vec{R\\S\\T} = \frac{2}{4} \vec{100\\100\\100} + \frac{2}{4} \vec{262\\38\\0} = \vec{181\\69\\50}$$

QRST: Q needs 2 more votes. In $F_Q, F_S, F_T$, Q proposes an even split which is accepted. In $F_R$, Q's cheapest option is to offer 179:0:70:51. $$E_4 \vec{Q\\R\\S\\T} = \frac{3}{4} \vec{75\\75\\75\\75} + \frac{1}{4} \vec{179\\0\\70\\51} = \vec{101\\56.25\\73.75\\69}$$

PQRST: P is fever-free. She only needs 2 more votes, but will pay for 3 in case one of them is fevered. The cheapest are RST. Note that P can't use an even split because only R is expecting less than 60, so if R has the fever, the others will reject an even split.

So P proposes a split of $99:0:57:74:70$.

---

Note: work in progress: $E_3$ and $E_4$ need refining.

Answer 3

Let's work our way from the bottom, the youngest pirate. The youngest pirate either wants all the gold, or to split it evenly with... himself!.

The second youngest pirate will lose if the youngest says no, so he must do a 50/50 split on the off chance the youngest is a Zanzibarbarian (with exploding wigs of death!).

The middle pirate can win with a single vote from below. Given 2's predicament, (and the possibility that one of the lower 2 is feverish), he has to appease one or both of them. If the youngest is feverish, then he could win over 2nd youngest by giving 151 coins and keeping 149. However, if #2 is feverish, then he could do a 100 split since he'll then get the 2nd's vote. That move is also the safest, since it also handles the youngest being feverish.

So, the 2nd oldest now is in a weird state. If he is feverish, he'll attempt to split the pot. The 3rd oldest now thinks that neither of 1st or 2nd are feverish, so he'll go for the 151/149 split. So, that'll fail. If not Zanzibarbarish, he has to give the middle pirate at least 100, since that's the minimum the middle stands to gain. Also, he has to worry about one of the younger ones being feverish. 2nd youngest also stands to gain more than 100, since that is most likely the middle's action. So, taking a risk of 0/101/101/98 is the 4th's play.

Ok, so most of the time, the youngest pirate will say no, and nobody really wants the evenly divided loot (or there aren't enough who do). So, the 2nd youngest stands to make 151/100/101 coins. So, you'll have to offer 2nd youngest at least 102 to win the vote. 3rd youngest stands to make 149/100/101 coins, so the same, 102 coins. 4th stands to make 98, so offer 99. So, offer 99 to the 4th, and 102 to either the 2nd or the 3rd, and keep 99 for yourself.