Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The pirate game is a popular problem that is often asked in interviews (which is how I stumbled upon it). The problem asks

There are 5 rational pirates, A, B, C, D and E. They find 100 gold coins. They must decide how to distribute them. The pirates have a strict order of seniority: A is superior to B, who is superior to C, who is superior to D, who is superior to E. The pirate world's rules of distribution are thus: that the most senior pirate should propose a distribution of coins. The pirates, including the proposer, then vote on whether to accept this distribution. If the proposed allocation is approved by a majority or a tie vote, it happens. If not, the proposer is thrown overboard from the pirate ship and dies, and the next most senior pirate makes a new proposal to begin the system again. Pirates base their decisions on three factors. First of all, each pirate wants to survive. Second, given survival, each pirate wants to maximize the number of gold coins he receives. Third, each pirate would prefer to throw another overboard, if all other results would otherwise be equal. The pirates do not trust each other, and will neither make nor honor any promises between pirates apart from the main proposal.

Let us consider this problem without the third condition (in my opinion, the pirates wouldn't be very rational if they can't make any proposals). What would the solution be in this case?

Considering a case with only three pirates, A, B, and C, the original solution proposes that A gives only a single coin to C to maximize his gains. This is because if only B and C remain, B can hoard all the gold and still maintain a tie vote.

However, C knows that B will always vote "no" (since he gets everything otherwise), so can't he tell A that he will vote "yes" with a probability $\frac{x}{100}$ where $x$ is the number of coins that he receives in the distribution (let's assume that A and C have a fully trust worthy way of doing this). If we treat death as equivalent to obtaining no gold, then wouldn't the expected gold pieces that C receives be $50$?

This is just one strategy, which does not include B. What is the optimal strategy for each pirate even in this simple case?

share|improve this question
2  
Just a quick comment - A and C could arrange that A will place $x$ gold coins and $100-x$ wooden coins in a bag, and that C will determine his vote by picking a coin from the bag - if it's gold he votes 'yes', if it's wooden he votes 'no'. The rules of this game generally state that surviving with any number of coins is infinitely preferable to death, though. If you were to follow that rule A should always pick a strategy that gives zero probability of death - in other words, he wouldn't agree to the probabilistic strategy. –  Chris Taylor Nov 22 '11 at 23:47
    
Hmm... you're right. But C doesn't really need A's approval to use this strategy. –  Anne Nonimus Nov 23 '11 at 0:14
1  
They asked the original problem, but failed to mention the third condition (probably by oversight). I managed to figure out the correct solution to the original problem, but it was only after the interview that I thought about this some more and read that Wikipedia article (which included the third condition). –  Anne Nonimus Nov 23 '11 at 2:49

2 Answers 2

Your version raises a number of interesting points.

I disagree with Chris' comment about the pirates infinitely preferring life over coins. In the standard version, there's no opportunity to gauge the relative weight of these outcomes for the pirates, since with deterministic outcomes it makes no difference whether we count death as $0$ coins or as $-\infty$ coins; that question only arises in the probabilistic version. From your statement that C can get $50$, I gather that you count death as equivalent to $0$ coins (so life without money means nothing to the pirates), and I'll assume this in the following.

Your version raises the problem of non-credible threats. You write "let's assume that A and C have a fully trustworthy way of doing this". However, that trustworthy way would need to be integrated into the voting norms. It's not enough for there to be some mechanism by which C can reliably and without opportunity for manipulation determine a random vote according to the agreed distribution. She also has to be somehow constrained to actually vote according to that result, since it won't be in her interest to do so, no matter what she promised beforehand, and this can't be done by some mechanism – casting a vote is a necessarily voluntary act, so even a machine mechanically moving her mouth to form "yes" or "no" wouldn't do. So "the pirate world's rules of distribution" need to be changed on the normative level – it must be impossible to vote contrary to an agreement. (Alternatively, the pirates could be assumed to have a fully internalized code of honour that prevents them from breaking agreements, thus violating the original premise that they are rational.)

So let's assume that this problem has been resolved and the pirates can make promises about how they will vote. You haven't specified how the negotiations over these promises proceed. A priori it's possible that if B and C can change their promises depending on what the other has promised, there might not be an equilibrium. Let's find out first how A would act given fixed promises from B and C. In its most general form, each promise is a function that assigns to each proposal from A a probability of rejecting it. Thus, the probability might depend not only on the promiser's share but also on the split between the other two. Assuming A is risk-neutral, she will then try to maximize the expected number of coins she gets. Since both of the other two have to reject for the proposal to be rejected, this is $(1-p_Bp_C)n_A$, where $n_A$ is the number of coins the proposal allocates to A, and $p_B$ and $p_C$ are the probabilities that B and C will reject the proposal, respectively.

The value of the proposal for B is $100p_Bp_C+(1-p_Bp_C)n_B$, and the value for C is $(1-p_Bp_C)n_C$, where and $n_B$ and $n_C$ are the numbers of coins the proposal allocates to B and C, respectively. Given some promise by B, C will choose a promise that maximizes the expected value of the game for C. That will fix the proposal that A chooses (assuming there are no ties). Note that since A chooses deterministically, C might as well make his rejection probability for the proposal that A will choose $0$ and all others $1$, since that won't change A's choice. Thus, if B's choice is fixed and C can react to it, there's no probabilistic element in C's strategy after all – he just picks the best proposal that he can get A to make and then promises to accept that proposal and reject all others.

In the case that you considered, where B "promises" to always reject, the best proposal that C can get A to make is 1 for A and 99 for C, and he should promise to accept this proposal and reject all other proposals, securing 99 coins for himself.

If B and C can react to each other's promises or negotiate with A, of if B and C are allowed to have mixed strategies, that is, they can choose "meta-distributions" over the rejection probabilities they might promise, things might get more complicated.

share|improve this answer

I don't have a complete answer but I guess this is how it'll look like. I'm extending from @joriki's answer. So, please read that first.

In the first case where B does not make a deal,

C can say, I'll vote yes with a probability of 1/(n-x+1), where n is the total number of coins (here 100) and x is the number of coins he gets. Here, the best strategy for A is to give (n-1) coins to C and keep only 1.

Now, B too can make such an offer. All A can do is distribute it such that (1-pB pC)* nA is maximized. If the distributions of probability are not same, A will give more coins to the person offering a better probability increase per added coin ($ \delta p _X/\delta n _X $)

Hence, to get the best deal,both B and C will have to offer the same distribution which gives the best rate.

I haven't calculated the distribution with the best rate yet. But the final split would be something like 1, 49, 48 or something similar.

P.S: I've done a lot of hand waving here. I think B might offer a worse distribution function than C and still get the optimum value 100*pBpC+(1-pBpC)*nB. Need to figure out how to find the optimal probability function for B and C.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.