PolySciFi Blog

As always, say my name and I appear.

I had some time to spend away from my final exam grading, so I decided to explain yet another of Jody's oblique references. This time, it happened most of the way down this post.

But more than that, I want to throw something out that will hopefully provide fuel for what I see as the two things best accomplished by the blogosphere: people expressing their opinions, and people blowing holes in the opinions of others.

And away we go...

Recently, I've taken up the habit of posting brain teasers and other such puzzles on my office door. It gives the people who are waiting to see me something to do while they wait. It's something I should have done a long time ago, back when I had larger crowds filling the hallways, but that's a different story altogether.

In any event, one of the puzzles that I posted ended up sparking a discussion between Jody and myself concerning the invalidity of its solution vis a vis its stated parameters. Only recently - one morning in the shower, no less - did I realize that we had ourselves ignored the stated parameters of the problem in the analysis we made of its flaw. Our potential mistake could actually restore the validity of the original solution. Unfortunately, I'll have to divulge the solution to give you the chance to give you the chance to analyze the problem, the solution, the "problem" with the solution, and the problem with the "problem" with the solution. (Whew!)

I invite you to leave comments concerning the flaw in my own logic.

First, the problem:

A band of five pirates have collected 100 gold pieces in loot. The five pirates decide to divide the loot according to the following procedure:

1. The most senior pirate proposes a division of the gold among the five pirates.
2. If at least 50% of the pirates vote in favor of the division, the gold is divided in the manner proposed.
3. If the vote fails by the requirements of point #2, the most senior pirate is killed, and the next most senior pirate makes a new proposal, per point #1.

All of the pirates are very greedy (each one wants as much money for himself as he can get) and very intelligent (each one will take action to ensure that he receives as much money for himself, and knows that the others will do so as well). But above all, none of the pirates wants to die.

As the most senior pirate, what proposal do you make that will maximize your take and keep you alive?

The primary mode of solution is to work backwards. Let's take the pirates to be numbered 1, 2, 3, 4, and 5, in descending order of seniority.

If there were only one pirate (Pirate 5), he would propose to take 100 gold pieces for himself, and he would vote in favor of his proposal.

If there were two pirates (4 and 5), then Pirate 4 can always propose that he recieve 100 gold pieces, and that Pirate 5 receive nothing. Further, by voting in favor of the proposal, it succeeds with a vote of 50%.

Things get serious when three pirates are involved. According to the previous development, Pirate 3 knows that Pirate 4 will get all of the money if Pirate 3's proposal fails. He also knows that Pirate 5 knows this. Therefore, Pirate 3 has to buy Pirate 5's vote with more money that Pirate 5 would get under Pirate 4's proposal. Since Pirate 5 will get nothing under an eventual proposal by Pirate 4, that amount happens to be 1 gold piece. So Pirate 3 proposes the following division: 99 gold pieces for Pirate 3, 0 gold pieces for Pirate 4, and 1 gold piece for Pirate 5.

Pirate 3 votes in favor of the proposal - after all, he's making out like a bandit, or a buccaneer, or some such. Pirate 4 votes against the proposal - he knows he can do better than 0, and so has every incentive to see Pirate 3 walk the plank. Pirate 5 votes in favor of the proposal - he knows that he'll do worse if Pirate 4 makes the proposal, and that Pirate 4's proposal will pass. So Pirate 3's proposal passes.

We'll come back to this point in a moment.

With 4 pirates, Pirate 2 must now buy one vote. By the previous development, Pirate 2 knows that Pirate 3's proposal will pass as described above. Pirate 2 therefore proposes the following division: 99 gold pieces for Pirate 2, 0 gold pieces for Pirate 3, 1 gold piece for Pirate 4, 0 gold pieces for Pirate 5. Pirates 3 and 5 will vote against the proposal - they both know that they can do better under an eventual proposal by Pirate 3. Pirate 4 will vote in favor of the proposal - he knows that he is doing better now than he will under a proposal by Pirate 3, which will pass as described above. So Pirate 2's proposal passes.

It should be trivial to demonstrate to yourself that Pirate 1 will propose 98 gold pieces for Pirate 1, 1 gold piece each for Pirates 3 and 5, and nothing for Pirates 2 and 4. The proposal will pass with the affirmative votes of everyone receiving money.

Now for the "problem"...

Since the pirates value their lives above money, then instead of viewing each proposal as the having senior pirate buying votes, we should view each propsal as the having the senior pirate buying his life!

With three pirates in play, suppose that it occurs to Pirate 5 to tell Pirate 3, "Give me all the money, or I'll vote to kill you." On the face of it, this is a credible threat. A pirate would never vote against his own proposal, as it puts him one vote closer to sleeping with the sharks. Pirate 5 also knows that Pirate 4 can do better, so he'll vote no anyway. In this situation, Pirate 5 would seem to hold the balance of power, and can (apparently) charge mightily for his services.

This is the point where Jody and I finished looking at the problem, noting that this flaw throws off all of the development that followed it above. In looking elsewhere for commentary on the problem, I found proposals that would correct this seemingly glaring flaw. Among them, constraints on discussion among the pirates before votes (something that I don't think helps as much as it could given that all of the pirates are intelligent enough to figure out all possibilities for themselves) and the replacement of killing the senior pirate with simply disqualifying him from a share of the booty if his proposal fails.

But maybe...just maybe, the simplicity of the original problem shows its genius.

To pick up with the "flaw" in the three-pirate game, Pirate 5 has a moment of clarity that chases away the feeling that people get when they are flush with victory. "Wait a minute. Both of the other pirates know that I can make that threat. Pirate 4 doesn't have to do anything, since if it falls to him to make the proposal, he'll get everything. But he also has to know that he won't get anything under my 'pre-proposal'..."

What we've hit upon here is that Pirate 5 knows that everyone knows that any 'pre-proposal' that he makes to Pirate 3 will result in a division of the booty, since Pirate 3 won't vote to kill himself.

Pirate 5 goes on thinking..."If Pirate 4 knows that he has a 100% chance of getting nothing if I get everything, he'll change his behavior. When I make my threat, Pirate 4 will no doubt think for a moment, and then he'll say. 'Alright, give me 99 gold pieces, or I'll vote to kill you.'"

While it is true that Pirate 4 knows that he would do better than 99 gold pieces if he got to make the proposal, he also knows that he'll never get to make the proposal based on whatever division satisfies Pirates 3 and 5. His only recourse is to make a threat that is "equally credible" but less costly monetarily to Pirate 3. Knowing what we (and they) know about Pirate 3's need to buy one of their votes (because really, we're back to that again), what we have here is a price war. Really, either pirate can threaten, but the other knows that if the threat goes unchallenged with a counter threat, that the initial threat will be accepted.

Pirate 5 continues..."Of course, I can bid down my 'services' to 98 gold pieces, but at that rate, eventually, Pirate 4 will bid 1 gold piece, and I'll get nothing. I might as well be the one to get the 1 gold piece, so I'll just keep my mouth shut."

Here's what we've figured out:

1. Pirate 3 only has to have one of the two less-senior pirates vote for him, and thus any threat made by one of the two guarantees that it will be accepted, unless the other one of the two can do "better" for Pirate 3.
2. Pirate 4 need not make a threat initially, since he'll get all of the money if Pirate 3 dies. However, rather than risk getting cut out of the money if Pirate 5 makes a threat, Pirate 4 will always make a threat that involves Pirate 3 giving away one less gold piece than does Pirate 5's threat. Even though he could do better if he gets the proposal, he knows that he has no chance of doing better if Pirate 3 accepts any threat made by Pirate 5.
3. The only threat that from Pirate 5 that Pirate 4 can't trump is a threat of 1 gold piece for Pirate 5. Rather, he could trump it, but wouldn't. He wouldn't propose to Pirate 3 that he keep all of the money, and this proposal wouldn't be accepted by either of the other two pirates anyway.
4. If Pirate 4 were to make the pre-emptive threat "Give me all of the money," the same development finds Pirate 5 bidding all the way down to 1 gold piece.

Therefore, even though Pirate 3 is buying his life, he can buy it cheaply since either of the other two pirates is in the same position to sell it to him. Further, each of them wants to get something out of the transaction knowing that they both can't.

Or can they? Can one of the two less-senior pirates buy the vote of the other less-senior pirate? Suppose that either Pirate 4 or Pirate 5 tells Pirate 3 "Give me x gold pieces, and give the other pirate (100-x) gold pieces, and I'll vote for you to live." The other pirate can always say, "I won't vote for that, but give me [1oo-(x-1)] gold pieces, and give the other pirate (x-1) gold pieces, and I'll vote for you to live." This will (or could) continue up to the limit point of one pirate "asking" for all of the money, and we've seen the "obvious" problem there.

It would seem though, that the equilibrium offer is 1 gold piece to whoever can't do better under any other circumstances. The "whoever" in this case is Pirate 5, which restores the situation in the original solution and presumably, the rest of the solution as well.

For those of you who cared to get this far, final thoughts and questions to which you can respond in the comments:

1. Where is the flaw in my new logic? Or were Jody and I just that "dumb"to have missed it the first time around?
2. Does the restoration of the three pirate case result in the restoration of the entire solution, or is there a credible threat in the four pirate case (where I suspect not, since the senior pirate only has to buy one vote from a non-senior pirate) or in the five pirate case (which I haven't analyzed)?

Wow, that was fun. I really need to get back to this. But for now, I have to get back to work. Or...playing Civ. Reviews of Civ 4 would also be accepted as comments, since I don't think my computer will run it.

Yarrrrr!

Update #1

I have read commentary elsewhere about the potential meaning of pirates casting "communicative sub-optimal votes." For example, in the five pirate case, Pirate 3 could vote "no" even though 1 gold piece is the most money he could hope for if every pirate plays the game true-to-form. He does this on the assumption that:

1. 1 gold piece is not a lot to lose, given that he could get more than that if other things go his way.
2. Turning down more money than he could get could communicate information to Pirates 4 and 5, namely, that he is willing to settle for less money than he could get under his best circumstances, given that he has already run the risk of getting less money than he would under the expected circumstances.

To some degree, this goes against one of the stated premises - that the pirates are each looking to maximize his gain given that he knows that all of the other pirates are looking to do the same. But if you still want to discuss the role of that piece of human nature in the game(that of - gasp! - compromise) please feel free.

Update #2

Thanks for the commentary! I've responded to a few of them to address some issues that may have been my fault in not explaining very well.

I'm almost sufficiently encouraged to get back into a regular schedule of writing more than once a season...work permitting, of course. Maybe I'll make a puzzler column or something - it works for Car Talk!

|