You are Johnny Depp 2!

An extension of this question repeated below.

A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins.

Arriving on a deserted island, they now have to split up the loot. You, as the captain of the band, have to propose a distribution plan (who gets what). What's your proposal?

Consider that this bunch is a democratic lot. If your proposal is accepted by half of the group, then everybody adheres to it. However, if folks feel you are getting greedy, and less than half of the band agrees to your proposal, then they kill you, and then your First Mate gets to make a proposal. And so it goes in decreasing order of hierarchy/seniority.

These pirates are unhappy with the poor definition of democratic voting and now insist that the vote must be carried by a clear majority and voting is compulsory! These are bloodthirsty pirates so life is cheap. Specifically it is worth 1 coin so the pirates criteria for accepting a proposal is (in order)

1. They do not die
2. It makes them the most money
3. It allows them to kill the most pirates

How does this change the outcome?

For $n$ pirates, let $P_1$ be the last pirate, $P_2$ be the next to last and so on up to $P_n$ who is the (temporary?) leader.

1. For $n=1$, $P_1$ takes all the money.
2. For $n=2$, $P_2$ is a dead man since $P_1$ can vote no, kill $P_2$ AND get all the money.
3. For $n=3$, $P_3$ can count on $P_2$ since if he votes no he is going to die.
4. For $n=4$?

I will post an answer after the weekend if no one else has.

-
Regarding your analysis for the case with 2 pirates, does that mean that you assume that pirates are friendly, and not bloodthirsty? (same meaning as in the linked question) – Ivan Loh May 8 '13 at 5:26
I am assuming that they will kill if it makes them richer but won't kill if they stay the same or are better off. Seems pretty bloodthirsty to me but maybe not for pirates. – Dale M May 8 '13 at 5:50
Wouldn't that just result in the first pirate getting everything for $n \geq 3$? (which isn't very interesting) We can prove this by induction on $n \geq 3$, the number of pirates. If for $k$ pirates the 1st pirate can get everything, then when there are $k+1$ pirates, the 1st pirates proposes to get everything. The 3rd to last pirate will get nothing regardless of whether or not they accept the proposal, so they will accept the proposal, and we get a clear majority. The base case $n=3$ is similar. – Ivan Loh May 8 '13 at 5:57
I agree with $n=3$. Think again for $n=4$. I will refine my "bloodthirstyness" comment - the pirates don't care either way if it does not affect their wealth. – Dale M May 8 '13 at 6:00
Do you mean that they will abstain from the vote if it does not affect them? If your intention was for the pirates to vote for the proposal in the case where it does not affect the wealth (since they opt to not kill), then my analysis above should be correct. If they abstain from voting if it doesn't matter, that's completely different. – Ivan Loh May 8 '13 at 6:08

Assumptions:

1. Pirates are rational, greedy, and bloodthirsty.
2. If the head pirate has multiple possible proposals in which he maximizes his profit, he will choose between them randomly, with a uniform probability distribution.
3. The first two items on this list are common knowledge among pirates.

Notation:

Let $G$ be the number of gold coins. A proposal in which $P_i$ receives $g_i$ gold coins will be denoted by $(g_n,\ldots,g_1),$ where $P_n$ is the most senior pirate.

Case $n=4$:

$P_4$ must garner the support of two other pirates to obtain a clear majority. For the case $n=3$, $P_1$ and $P_2$ receive nothing, so a proposal of $(G-2,0,1,1)$ is accepted.

Case $n\ge 5$

A proposal of $(G+1-2\lfloor \frac{n}{2}\rfloor,0,1,g_{n-3},g_{n-4},\ldots,g_1)$ is accepted, where for $i=1,2,\ldots,n-3$, exactly $\lfloor\frac{n}{2}\rfloor-1$ of the $g_i$'s are $2$, and the rest are $0$. First, notice that by assumption $2$, for $i=1,2,\ldots,n-3$, the expected value of the proposal for $P_i$ is

$$E_n=\frac{2\lfloor\frac{n}{2}\rfloor-2}{n-3}=\begin{cases}1&\text{if n is odd}\\[.1in]\frac{n-2}{n-3}&\text{if n is even}\end{cases}$$

What is most important is that $1\le E_n<2$ for $n\ge 5$.

We prove that this proposal is accepted by induction. For the case $n=5$, the two possible proposals are $(G-3,0,1,2,0)$ and $(G-3,0,1,0,2)$. Comparing with case $n=4$, we see that $P_5$, $P_3,$ and $P_2$ will vote for the first proposal, while $P_5$, $P_3,$ and $P_1$ will vote for the second proposal.

Now assume that the proposal holds for $n-1$ pirates, and that there are $n$ pirates. $P_{n-2}$ receives $0$ gold coins in the case of $n-1$ pirates, so he will vote for the proposal. Since $1\le E_n<2$, any pirate from $\{P_1,\ldots,P_{n-3}\}$ will vote for a proposal in which he receives at least $2$ coins, and will vote against a proposal in which he receives less than $2$ coins. Thus, exactly $\lfloor\frac{n}{2}\rfloor-1$ of the pirates $P_1,\ldots,P_{n-3}$ vote for the proposal.

Remembering that $P_n$ will vote for the proposal, that makes $1+1+\lfloor\frac{n}{2}\rfloor-1=1+\lfloor\frac{n}{2}\rfloor$ votes for the proposal, so it passes.

For the case of $n=9$ and $G=1000$, $P_9$ receives $993$ coins.

Comparing this with the result of the first question, it seems that the new voting system requires that $P_n$ give up exactly $2\lfloor\frac{n}{2}\rfloor-\lfloor\frac{n-1}{2}\rfloor-1$ extra gold coins ($n\ge 5$).

Edit

If, instead of assumption $2$, we assume that the head pirate chooses between multiple possible proposals that maximize his profit by rewarding seniority, then a proposal of $(G-1-\lfloor\frac{n}{2}\rfloor,0,1,2,0,1,0,1,\ldots,\frac{1+(-1)^n}{2})$ will be accepted. The proof is similar to the induction above. In the case of $n=9$ and $G=1000$, we see that $P_9$ receives $995$ gold coins.

-
According to the "bloodthirsty" criteria, assumption 2 is wrong. Given the choice between equal offers the pirate will choose a. The one where he doesn't die b. the one where he gets to kill more pirates. My $n=3$ solution is wrong according to this so I will edit it. – Dale M May 9 '13 at 20:32
@DaleM: If $P_n$'s proposal is accepted, he doesn't die and no one is killed. Thus, all he cares about is finding a proposal that is accepted in which he gets the most gold coins possible. There might be many ways to do this, depending on which pirates he chooses to bribe. My assumption says that he bribes pirates indiscriminately. Consider the case $n=5$ which I've written out explicitly. – Jared May 9 '13 at 20:50
Sorry, I misread. – Dale M May 9 '13 at 20:56
So you are saying that pirates will vote for a proposal if it is better than their expected value? As pure rationalists, this seems fair enough. – Dale M May 9 '13 at 21:02
I had in mind the simpler assumption that he rewards seniority but both are good. – Dale M May 9 '13 at 21:04

In case of 1 pirate, there's no debate.

If there are 2, then the n1 gets all the money, n2 gets none. Because if n2 proposes anything less, n1 will not agree, hence proposal won't get clear majority, hence n2 will die and n1 will get everything nonetheless. (1000,0)

If there are 3 pirates, then n3 just has to give n2 1 coin to buy his loyalty. n1 goes penniless. (0,1,999)

If there are 4 pirates, then n4 has to buy the loyalty of 2 pirates. He can give 1 coin to n1. That's easy. Next, he can give 2 coins to n2 and nothing to n3 (1,2,0,997)

5 pirates (2,0,1,0,997)

6 pirates (0,1,2,1,0,996)

7 pirates (1,2,0,0,1,0,996) OR (1,0,0,2,1,0,996) (yup, it gets messy)

8 pirates if 7 pirate arrangement was (1,2,0,0,1,0,996) then (2,0,1,1,0,1,0,995) OR (0,0,1,1,2,1,0,995)
if 7 pirate arrangement was (1,0,0,2,1,0,996) then (2,1,1,0,0,1,0,995) OR (0,1,1,0,2,1,0,995)

9 pirates if 8 pirate arrangement was (2,0,1,1,0,1,0,995) then (0,1,2,0,1,0,1,0,995) OR (0,1,0,2,1,0,1,0,995) OR (0,1,0,0,1,2,1,0,995)
if 8 pirate arrangement was (0,0,1,1,2,1,0,995) then (1,1,2,0,0,0,1,0,995) OR (1,1,0,2,0,0,1,0,995) OR (1,1,0,0,0,2,1,0,995)
if 8 pirate arrangement was (2,1,1,0,0,1,0,995) then (0,2,0,1,1,0,1,0,995) OR (0,0,2,1,1,0,1,0,995) OR (0,0,0,1,1,2,1,0,995)
if 8 pirate arrangement was (0,1,1,0,2,1,0,995) then (1,2,0,1,0,0,1,0,995) OR (1,0,2,1,0,0,1,0,995) OR (1,0,0,1,0,2,1,0,995)

So there's actually multiple proposals (permutations) that work (the question asks that the solver lay down the proposal, not merely calculate the number of coins the captain gets).

But if we look a little more closely, what does this mean?

7 pirates step is crucial. For the first time, it gives us 2 proposals that may pass.

If there are 8 pirates, then they don't know which of the two proposals will be made if they kill their captain. Even if they believe that the First Mate will randomly make one of the two proposals, their possible outcomes can be expressed as expected values: (1,1,0,1,1,0,996)

In fact, there is an argument to be made that both n2 and n4 are optimistic and each see their 7 pirate outcomes to be bettered as 2 coins.

Meaning the outcomes to be bettered in an 8 pirate group is (1,2,0,2,1,0,994)

So that's what the Captain needs to propose (2,0,1,0,2,1,0,994)

Which means, in case of 9 pirates the distribution will be (0,1,2,1,0,0,1,0,995) OR (0,1,0,1,0,2,1,0,995)

-
Nice try but ... if I am $P_3$ for $n=3$, I won't give anything to anybody, $P_1$ will vote against but $P_2$ will vote for since if he doesn't he will get no coins AND DEAD! – Dale M May 10 '13 at 5:25
In case of 2 pirates, n1 gets everything, n2 gets nothing. But n2 doesn't end up DEAD (remember, head of the lot is killed only if his proposal is rejected) because this is proposal that n2 makes! That's why in case of 3 pirates, you need to imporove n2's outcome to 1 coin. If n2's outcome is zero the he'd be ambivalent. – OC2PS May 10 '13 at 11:27