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
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:
- 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/300because all three pirates realize that there are no Zanzibars left. - 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:
- 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 proposing0/0/300because P4 could have been bluffing. Because if P3 proposed0/0/300with any chance, then P4 should start bluffing with some chance. - 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:
- P4 chose badly (2/3) chance:
100/100/100/dead - 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:
101/101/0: Either P1 or P2 is the Zanzibar. P3 must propose100/100/100and it will pass. (2/6 chance)101/0/101: P3 knows P1 is the Zanzibar but P2 doesn't yet. P3 can offer0/151/149because 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)0/101/101: P3 knows P2 is the Zanzibar. P3 must offer100/100/100otherwise both P1 and P2 will refuse. (1/6 chance)
If P3 is the Zanzibar:
101/0/101: P3 offers100/100/100. P1 knows that P3 is the Zanzibar and votes no. P2 votes yes though to pass the proposal. (1/6 chance)0/101/101: P3 offers100/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.
No comments:
Post a Comment