Counting problem about pirates and gold coins

Question

Five pirates find a cache of 500 gold coins. They decide that the shortest pirate will serve as the bursar and determine a distribution of the coins however he sees fit, and then they all will vote. If at least half of the pirates (including the bursar) agree on the distribution, it will be accepted; otherwise, the bursar will walk the plank, the next-shortest pirate will become the new bursar, and the process will continue.

Assume that each pirate is super-intelligent and always acts so as to maximize his wealth, and also that each pirate is vindictive: he would like to see someone walk the plank, as long as it does not hurt him financially.

How many coins will the shortest pirate get?

How would I start and what strategy/method would I use to solve this problem?

Answer 1

A good way to start is to reduce your problem. Think about what happens when there are two pirates, for example. In this situation, then the shortest pirate is going to propose he gets all of the gold, and if he votes yes to this then he takes all of the gold.

Hint: Think about three pirates and how this relates to two pirates, then the method becomes clearer.

---

Solution: SPOILERS BELOW! (I recommend you have a go at the hint first!!)

What about three pirates? Well, in this case the tallest pirate knows that if the bursar walks the plank, he'll get absolutely nothing, as then there are only two pirates left - and so he stands to gain provided he gets greater than zero coins. So the bursar can propose the split (499, 0, 1), and the tallest pirate has no choice but to vote yes, as if he votes no he'll get nothing when there are two left.

What about four pirates? Well, in this case it's all about buttering up the second tallest pirate. He knows that if it's reduced to three pirates, then he'll get nothing. So you have to offer him 1. Then that's enough to get his vote, and thus the bursar need only offer the following: (499, 0, 1, 0).

And so we continue, with five pirates; then the bursar need only butter up the tallest and third tallest, as they know if it goes to four pirates then they get nothing. So giving them one coin apiece is enough, and so the optimal for the bursar is (498,0,1,0,1).

So, it turns out, in the pirate universe it really pays to be short!

Answer 2

The solution concept most frequently employed for such questions is that of Nash Equilibrium, which means that each pirate chooses a strategy that is optimal for himself, subject to the other pirates' strategies.

This problem has multiple Nash equilibria. Here's one:

The bursar always claims all the coins for himself and everyone always votes yes.

You can see that if everyone adopts this strategy, the shortest pirate gets all the coins. Moreover, no individual pirate can improve his own outcome by changing strategies, taking everyone else's as given (because no individual pirate can change the outcome of a vote when all four of the others are voting as a block).

Again, this is only one of many Nash equilibria for this problem, and probably not the one that whoever asked you this question was looking for. But it's a perfectly good answer.

(Note: If you want to dig a little deeper, you might look into the concept of a subgame perfect equilibrium, which will lead to a smaller class of solutions.)