[Yoruichi-san]

After long months of adventuring the seven seas, the Pirates return with a eighth crewman just in time to star on "Who Wants to be Pirate King" on the Grand Line Network, the new hit reality Pirate Game show. The rules are as follows:

Every round the current Captain makes a proposal on who to vote off the ship that round, which the pirates vote yes or no on. If half or more of the remaining pirates vote yes, the proposal is followed and a new round begins. If more than half of the pirates vote no, the Captain walks the plank and the next ranked pirate becomes Captain, and a new round starts.

Of course, being pirates, the Captain can influence his crewmen's votes by bribing any pirate(s) with an counting number of gold coins during any and every round. The pirate's preferences are as follows:

1) Becoming Pirate King

2) The amount of gold they leave the ship with

What is the minimum number of gold coins that the Captain Straw Hat (the current Captain) has to spend in order to become Pirate King?

[Prime]

Okay, I think I see what is confusing you...the phrase:

the Captain can influence his crewmen's votes by bribing any pirate(s) with an counting number of gold coins during any and every round.

was meant to mean that the bribes can only be offered once per round, but can be offered to any number of pirates any round. Sorry, I should have made that more clear in the OP. Does that solve the discrepancy for you?

Edit: I apologize for not reading your answer closely enough the first time and not seeing what the misunderstanding of the terms of the OP was. I'm just used to you asking questions about things that aren't totally clear. My bad .

The way I uderstood bribing:

Every round, after announcing who is the candidate to be off the ship, the captain can walk up to any pirate and confidentially offer a bribe -- one gold coin. The pirate may accept or decline. Then captain walks to another pirate if he still needs to influence more votes, and so on. When captain feels secure he has enough men on his side, the voting commences. If the captain approached every pirate in turn and still didn't secure enough votes, the voting shall commence, anyway.

Another assumption is that the pirates can calculate all possible outcomes and follow the strategy which gives highest return.

I don't see how announcing bribery attempt to a group of pirates in the open changes things. Make a link to the "original" pirate problem, as there are number of duplications of pirate problems in this forum.

You should also be able to show where you think my analysis

is wrong. That is a different strategy, where captain paid less money, and didn't walk the plank, or where a pirate followed a different pattern and ended up richer or king in all possible outcomes.

We, pirates are mercyless.

[Yoruichi-san]

The way I uderstood bribing:

Every round, after announcing who is the candidate to be off the ship, the captain can walk up to any pirate and confidentially offer a bribe -- one gold coin. The pirate may accept or decline. Then captain walks to another pirate if he still needs to influence more votes, and so on. When captain feels secure he has enough men on his side, the voting commences. If the captain approached every pirate in turn and still didn't secure enough votes, the voting shall commence, anyway.

Another assumption is that the pirates can calculate all possible outcomes and follow the strategy which gives highest return.

I don't see how announcing bribery attempt to a group of pirates in the open changes things. Make a link to the "original" pirate problem, as there are number of duplications of pirate problems in this forum.

You should also be able to show where you think my analysis

is wrong. That is a different strategy, where captain paid less money, and didn't walk the plank, or where a pirate followed a different pattern and ended up richer or king in all possible outcomes.

We, pirates are mercyless.

Okay, yes your analysis is very insightful for your interpretation of the OP. However, your interpretation is not what I intended in the OP. I ask that you respect my original intent now that I've clarified it, which was that the bribe offer is made basically as part of the proposal each round, i.e. it is part of the game being played and not done covertly and the bribing action occurs once each round, i.e. the Captain cannot address each pirate individually and sequentially. This is in the spirit of the Pirate's Game. As I specifically said before, the point of this variation of the Pirate's Game is the shift that is created in the ranking positions by which pirate gets voted off the ship. The goal for the Captain is to try to utilize this to his advantage to minimize the amount of bribes that go out.

Edited October 19, 2008 by Yoruichi-san

[unreality]

To clarify, the Captain makes all the bribes (one bribe to each pirate, 0 gold to a pirate that he's not bribing) at the exact same time, and the bribes are accepted/denied non-sequentially without the pirates knowing what the others were bribed or if they accepted/declined?

[Yoruichi-san]

To clarify, the Captain makes all the bribes (one bribe to each pirate, 0 gold to a pirate that he's not bribing) at the exact same time, and the bribes are accepted/denied non-sequentially without the pirates knowing what the others were bribed or if they accepted/declined?

Thank you, that's a good way of thinking about it. Another way of thinking about it is that the bribes are part of the proposal, i.e the Captain says "Okay, this round I propose to vote off Pirate A and I offer x amount of gold to the following pirates", etc, and the bribed pirates get the gold if they vote yes. Actually, that's probably what I should have said in the OP, sorry again about the ambiguity. :/

[unreality]

So each pirate knows the amount offered to the other pirates? And the Captain's proposal format is like this? "Vote off a, offer x gold to b, y gold to c, z gold to d, etc". The pirates that accept get their gold as well as contribute the captain's vote, and those that vote against it do not get the gold amount. And they hear what each pirate is bribed?

thanks for all the clarifying

[Yoruichi-san]

So each pirate knows the amount offered to the other pirates? And the Captain's proposal format is like this? "Vote off a, offer x gold to b, y gold to c, z gold to d, etc". The pirates that accept get their gold as well as contribute the captain's vote, and those that vote against it do not get the gold amount. And they hear what each pirate is bribed?

thanks for all the clarifying

Yep, basically, although...

The assumption that the Pirates are well versed in game theory basically means that they already know what's going to come down...

And

Spoiler for Hint...:

although a pirate who accepts a bribe must vote yes, it does not take a bribe each round to make a pirate vote yes, their preference is based on the gold they have when they leave the game...i.e. if they know that if they vote yes a particular round they will get gold in a future round, but if they vote no, they won't, then they will vote yes.

Thank you for asking! My intention was to share an interesting puzzle that is a variation of the Pirate's Game, and I'm sorry that I failed in wording the OP to describe the puzzle in a clear and unambiguous way, but I'm happy to answer any questions to clarify it .

[unreality]

say there are 2 pirates, Captain © and Pirate 2 (P2). C props P2 {P2 0} = P2's decision doesn't matter, C wins with 0 gold loss (the bribe is in the curly brackets)

3 pirates, C/P2/P3. If C props P3 {P2 1; P3 0}, P3 will vote against, P2 will vote against because then he becomes captain and wins. In fact, in all cases, P2 will vote against. So C props P2 {P2 0; P3 1}, and P2 votes against, however P3 must accept because if they decline, P2 will win next turn with an offer of 0 to P3. 1 gold > 0 gold, cuz P3 cannot win. So then it comes down to C and P3, and then C props P3 off with a bribe of 0, thus C wins with gold loss of 1

4 pirates. C knows that P2 will vote against because then P2 becomes the C in the 3-pirate scenario. P4 knows that they will receive 1 gold in the 3-pirate scenario, so must be offered 2 to comply. P3 (P2 in the 3-person scenario) will get nothing in the next scenario, and thus would accept a bribe of 1 because 1>0 and they have no hope of winning

so: C props P2 {P2 0; P3 1; P4 0}

Making the total cost for the Captain to win 1+1 (1 from this round, 1 from previous rounds) = 2 gold

5 pirates. From now on P2 will always vote against C, we've established that [unless we start getting into "well he knows what will happen and that he will win so he'll just go for the bribe" and so "then he won't" and "then he will" infinitely recurring switchbacks]. So the C should always vote out P2 (from now on). Now once that happens, P3 will be the next P2 to go in the 4-pirate scenario, in which they get nothing AND get voted out, so P3 would go for a bribe of 1. But C needs 2 pirates on his side, not just 1. P5 becomes P4 next turn, who gets 0 gold and becomes P3 the turn after that, who gets voted out. So P3 and P5 both have no prospects unless they're bribed

so: C props P2 {P2 0; P3 1; P4 0; P5 1}

total gold = 2+2 (2 this round, 2 previous round) = 4 gold total loss if there are 5 pirates to start with

6 pirates. C still needs just 2 extra votes. The P3 of this round becomes the prospectless P2 of next round, and the P5 of this round becomes the 0gold P4 of next round who becomes the one-gold P3 of the round after that. Thus P4 (next round's P3), P5 (P4 next round) or P6 (P5 next round) will do for the third vote, however all three require a bribe of 2. We'll just say that we give the bet to P6 cuz he's the new guy

so: C props P2 {P2 0; P3 1; P4 0; P5 0; P6 2}

total gold = 4+3 = 7

7 pirates. C now needs 3 extra votes to win him the round. He always votes out P2 and bribes 1 to the P2 of next round (P3 of this round), but after that he needs two more supporters! Those should be P5 and P6 (the P4/5 of next round, who both get 0), however they both eventually boil down to getting 1 at later times, so both require 2

C props P2 {P2 0; P3 1; P4 0; P5 2; P6 2; P7 0}

total gold = 7+5 = 12

8 pirates! The finale! C still needs 3 extra votes. As usual, he props P2 and bribes 1 to P3. Judging on the previous pattern, adding 1 to the previous, then 2, then 3, etc, the total gold loss is 12+6 = 18

Note that this is assuming that pirates are MALEVOLENT, and thus if at a later round they would receive a bribe of 1, they must receive a bribe of 2 in this round to not vote for the captain, because otherwise they could vote out the captain and be in the same spot next round, cuz 1=1 tie, and they'd rather see a pirate die than see a pirate live ;D A benevolent situation would mean reducing all the 2's to 1's (or at least most), and probably reduce the answer by about 5

Anyway, there's probably a strategy that works better for the Captain

[Yoruichi-san]

say there are 2 pirates, Captain © and Pirate 2 (P2). C props P2 {P2 0} = P2's decision doesn't matter, C wins with 0 gold loss (the bribe is in the curly brackets)

3 pirates, C/P2/P3. If C props P3 {P2 1; P3 0}, P3 will vote against, P2 will vote against because then he becomes captain and wins. In fact, in all cases, P2 will vote against. So C props P2 {P2 0; P3 1}, and P2 votes against, however P3 must accept because if they decline, P2 will win next turn with an offer of 0 to P3. 1 gold > 0 gold, cuz P3 cannot win. So then it comes down to C and P3, and then C props P3 off with a bribe of 0, thus C wins with gold loss of 1

4 pirates. C knows that P2 will vote against because then P2 becomes the C in the 3-pirate scenario. P4 knows that they will receive 1 gold in the 3-pirate scenario, so must be offered 2 to comply. P3 (P2 in the 3-person scenario) will get nothing in the next scenario, and thus would accept a bribe of 1 because 1>0 and they have no hope of winning

so: C props P2 {P2 0; P3 1; P4 0}

Making the total cost for the Captain to win 1+1 (1 from this round, 1 from previous rounds) = 2 gold

5 pirates. From now on P2 will always vote against C, we've established that [unless we start getting into "well he knows what will happen and that he will win so he'll just go for the bribe" and so "then he won't" and "then he will" infinitely recurring switchbacks]. So the C should always vote out P2 (from now on). Now once that happens, P3 will be the next P2 to go in the 4-pirate scenario, in which they get nothing AND get voted out, so P3 would go for a bribe of 1. But C needs 2 pirates on his side, not just 1. P5 becomes P4 next turn, who gets 0 gold and becomes P3 the turn after that, who gets voted out. So P3 and P5 both have no prospects unless they're bribed

so: C props P2 {P2 0; P3 1; P4 0; P5 1}

total gold = 2+2 (2 this round, 2 previous round) = 4 gold total loss if there are 5 pirates to start with

6 pirates. C still needs just 2 extra votes. The P3 of this round becomes the prospectless P2 of next round, and the P5 of this round becomes the 0gold P4 of next round who becomes the one-gold P3 of the round after that. Thus P4 (next round's P3), P5 (P4 next round) or P6 (P5 next round) will do for the third vote, however all three require a bribe of 2. We'll just say that we give the bet to P6 cuz he's the new guy

so: C props P2 {P2 0; P3 1; P4 0; P5 0; P6 2}

total gold = 4+3 = 7

7 pirates. C now needs 3 extra votes to win him the round. He always votes out P2 and bribes 1 to the P2 of next round (P3 of this round), but after that he needs two more supporters! Those should be P5 and P6 (the P4/5 of next round, who both get 0), however they both eventually boil down to getting 1 at later times, so both require 2

C props P2 {P2 0; P3 1; P4 0; P5 2; P6 2; P7 0}

total gold = 7+5 = 12

8 pirates! The finale! C still needs 3 extra votes. As usual, he props P2 and bribes 1 to P3. Judging on the previous pattern, adding 1 to the previous, then 2, then 3, etc, the total gold loss is 12+6 = 18

Note that this is assuming that pirates are MALEVOLENT, and thus if at a later round they would receive a bribe of 1, they must receive a bribe of 2 in this round to not vote for the captain, because otherwise they could vote out the captain and be in the same spot next round, cuz 1=1 tie, and they'd rather see a pirate die than see a pirate live ;D A benevolent situation would mean reducing all the 2's to 1's (or at least most), and probably reduce the answer by about 5

Anyway, there's probably a strategy that works better for the Captain

Good, that's the way to go about it...but...consider this...;P

Your analysis for 3 pirates is correct. For a thrifty (aka cheap

) Captain, he can manage to get the 4 pirate vote without spending anything...

Spoiler for hint...:

The 4 pirates know that going into the 3 pirate case, the pirate in position 3 will get a gold whereas the pirate in position 2 will get nothing...a smart Captain will make a proposal so that if pirate A votes for him, the next round the shift from removing the proposed pirate will put pirate A in P3 and get the gold, whereas if the pirate A votes against him, the shift from removing the Captain will put pirate A in a non-gold position...;P

[Prime]

Okay, yes your analysis is very insightful for your interpretation of the OP.

...

Aha, a bribery attempt! I love bribes! However, my solution to the problem as stated, is simply a correct one. Not being insightful, I cannot help.

So let's restate the conditions, as I understand them now: Each round, captain announces a proposal of whom to vote off the ship, which comes together with money offering to some crew members. Captain cannot back off his proposal or change money offering.

Let's designate crewman 1 through 7, where 1 is the first mate next to succeed the captain, and 7 -- the last man in succession.

When Captain is left with 2 crewmen, he just votes them out one by one. (Again, assuming that the off-the-ship candidate does not vote.) No one gets paid in the last 2 rounds. The round before that, when there are 3 men left, captain designates any one of the three to go off the ship, and then he needs one more vote to have his way.

In this situation, First Mate becomes unbribable, assuming he is the only one with a payoff offer, as he stands to inherit captain's position by voting nay. Any other man must accept the payoff, or end up with nothing. (In the case, captain designates First Mate to go off the ship, he has a choice of who of the two remaining men to bribe.)

Likewise, captain has a choice in earlier rounds who to kick off the ship and who to bribe. And pirates cannot count on any consistent pattern on the part of captain, nor captain can depend on any unpaid pirate's vote.

It is always possible for the captain to retain his position by paying enough money. That makes the first mate position an unpaid position, if Captain does not want to pay extra that is. That creates a certain appearance of a paradox.

All pirates, except First Mate, fancy they stand a chance to make some money. Now suppose, captain chooses someone other than the first mate to vote off the ship. The pirate who is next in line to inherit fist mate's position knows that if Captain walks the plank, he gets the unpaid dead end position. Also, it moves all, but the last two men closer to that uncoveted position. That seems like an incentive to vote with captain. But can captain count on that? I think no, he cannot. Not even on the vote of the man who stands to inherit First Mate position immediately. Because, such tactics on the part of the captain breaks the first rule, on which this whole reasoning relies. Namely, "it is always possible for the captain to retain his position". For if captain is voted out, then the first mate is no longer a dead end position.

Thus the solution remains simple. Captain must pay up. He can choose anyone to vote off the ship and must pay 3 coins 1st round, 2 coins second and 3rd and 1 coin 4th and 5th round. For a total of 9 coins.

[Prime]

Couple more things need clarification.

Does off-the-ship candidate participate in voting?

Is captain the only one who can bribe other pirates?

No, just the ones still in the Game (like a reality show ;P)

Yes, the current captain is the one who makes the proposal and gives the bribes.

Now you change the rules yet again. So the man who is being voted off the ship does participate in voting?

...

P4 knows that they will receive 1 gold in the 3-pirate scenario, so must be offered 2 to comply.

...

P4 becomes P3 one way or another in your scenario. He should not refuse any pay off offer, even the minimum one.

[Yoruichi-san]

Now you change the rules yet again. So the man who is being voted off the ship does participate in voting?

P4 becomes P3 one way or another in your scenario. He should not refuse any pay off offer, even the minimum one.

I never changed the rules, but I realized that they were ambiguous so I clarified my intent. The members off the boat don't vote, but the Captain (of the current round) does, just like in the original Pirate's Game. I never said that the bribing involved going up to each pirate and offering a bribe, then moving on to the next one, that was your interpretation. My intent all along was to have the Captain make one bribing action a round, i.e. he has to make a commitment to who he offers the bribes to, and if they refuse he is not allowed to try again. I am sorry if that was ambiguous in the OP, but it is what I meant, and I am happy to answer questions and clarify anything.

As someone who actually read the "Terms of Agreement" before I clicked the "I agree" button when I signed up, I distinctly remember there being something about respecting the intent of other ppl's OPs...

[Prime]

I never changed the rules, but I realized that they were ambiguous so I clarified my intent. The members off the boat don't vote, but the Captain (of the current round) does, just like in the original Pirate's Game. I never said that the bribing involved going up to each pirate and offering a bribe, then moving on to the next one, that was your interpretation. My intent all along was to have the Captain make one bribing action a round, i.e. he has to make a commitment to who he offers the bribes to, and if they refuse he is not allowed to try again. I am sorry if that was ambiguous in the OP, but it is what I meant, and I am happy to answer questions and clarify anything.

As someone who actually read the "Terms of Agreement" before I clicked the "I agree" button when I signed up, I distinctly remember there being something about respecting the intent of other ppl's OPs...

You assume I understand your intent. But I honestly don't. And my question was does the man who's designated by the captain to go off the ship vote? And I still don't know what is the "original pirate problem" you're refering to.

At any rate, that does not change the problem significantly. My answer is still the same.

Round 7: Captain and p1 pirate left. Captain votes him off.

Round 6: Captain, p1, and p2. P1 is designated off the ship, p2 gets 1 coin, or votes nay to punish captain. Note: when it is the same financially, pirates who did not get paid must vote against captain to create an incentive for payment. Thus captain must spend 1 coin to keep his position.

Round 5: C, p1, p2, p3. Any of pirates can be designated off. Captain has a choice of p2, or p3 to give coin to.

a). If p2 rejects money, then becomes p1 in round 6 and gets nothing. Note, if p2 is also the man being voted off the ship, he still must accept the money and vote himself off.

b). If p3 rejects money, then becomes p2 in round 6 -- earns 1 coin. Does not reject money also becomes p2 and will have earned 2 coins in rounds 5 and 6. Note, if p3 is also the man being voted off the ship, he'd be financially the same by refusing, or accepting Captain's offer. In that case it's not a good idea on the part of Captain to offer him money, he should bribe p2 instead.

c). Captain does not offer money. P1 votes against in all cases. P2 will have advance to p1 position one way or goes off the ship, not earning anything in either case, so he votes nay to punish stingy captain. P3 advances to p2 position either way, unless he is the one being voted off. In either case he votes nay. Therefore, Captain must pay 1 coin, or lose his position.

Round 4 through 1: C, p1, p2, p3, p4,... Captain designates any random man off the ship and with exception of p1 and, maybe, the off-the-ship candidate, offers 1 coin to the right number of randomly chosen men to secure enough votes. Each pirate must accept money, or be poorer if he doesn't.

The perception that pirates may want to avoid becoming the first mate is false, same as explained in my previous post.

For any individual pirate a perception that breaking equilibrium and starting moving captains off the ship in hope to reach captain's position just in time when it becomes unshakable is also false. Since in that case a pirate will be loosing payoff money for a non-existent chance to become captain. In fact, for any new Captain the first logical choice of the man to be voted off would be that equilibrium breaker who helped him to ascend.

So for this setup, captain has to pay 12 coins total.

Please, don't take it personally, if this solution does not match your intended one. For what's it worth, I think it's a good problem and that's the reason I posted my solutions here -- not to pick on your problem statement.

I consider myself voted off this ship.

[Yoruichi-san]

You assume I understand your intent. But I honestly don't. And my question was does the man who's designated by the captain to go off the ship vote? And I still don't know what is the "original pirate problem" you're refering to.

At any rate, that does not change the problem significantly. My answer is still the same.

Round 7: Captain and p1 pirate left. Captain votes him off.

Round 6: Captain, p1, and p2. P1 is designated off the ship, p2 gets 1 coin, or votes nay to punish captain. Note: when it is the same financially, pirates who did not get paid must vote against captain to create an incentive for payment. Thus captain must spend 1 coin to keep his position.

Round 5: C, p1, p2, p3. Any of pirates can be designated off. Captain has a choice of p2, or p3 to give coin to.

a). If p2 rejects money, then becomes p1 in round 6 and gets nothing. Note, if p2 is also the man being voted off the ship, he still must accept the money and vote himself off.

b). If p3 rejects money, then becomes p2 in round 6 -- earns 1 coin. Does not reject money also becomes p2 and will have earned 2 coins in rounds 5 and 6. Note, if p3 is also the man being voted off the ship, he'd be financially the same by refusing, or accepting Captain's offer. In that case it's not a good idea on the part of Captain to offer him money, he should bribe p2 instead.

c). Captain does not offer money. P1 votes against in all cases. P2 will have advance to p1 position one way or goes off the ship, not earning anything in either case, so he votes nay to punish stingy captain. P3 advances to p2 position either way, unless he is the one being voted off. In either case he votes nay. Therefore, Captain must pay 1 coin, or lose his position.

Round 4 through 1: C, p1, p2, p3, p4,... Captain designates any random man off the ship and with exception of p1 and, maybe, the off-the-ship candidate, offers 1 coin to the right number of randomly chosen men to secure enough votes. Each pirate must accept money, or be poorer if he doesn't.

The perception that pirates may want to avoid becoming the first mate is false, same as explained in my previous post.

For any individual pirate a perception that breaking equilibrium and starting moving captains off the ship in hope to reach captain's position just in time when it becomes unshakable is also false. Since in that case a pirate will be loosing payoff money for a non-existent chance to become captain. In fact, for any new Captain the first logical choice of the man to be voted off would be that equilibrium breaker who helped him to ascend.

So for this setup, captain has to pay 12 coins total.

Please, don't take it personally, if this solution does not match your intended one. For what's it worth, I think it's a good problem and that's the reason I posted my solutions here -- not to pick on your problem statement.

I consider myself voted off this ship.

Thank you. And I do appreciate all your insight and I appreciate constructive criticism on how I could make the problem statement more clear and I believe your analysis of the problem you saw was very insightful and correct, and thanks for accepting my problem.

And yes, everyone on the ship during a particular round votes, including the person who is the one proposed to be voted off.

You are very correct about the equilibrium in the problem, that is the beauty (I think) to the actual solution. However, I have a different solution that uses less coins. Let me point out where I start to differ from your thinking:

What happens if the Captain proposes to vote off P3 (the pirate in the last position)? (This is where the importance of the shift I was talking about earlier comes in...P1 and P2 are left with a choice b/w two possible shifts)

Edited October 20, 2008 by Yoruichi-san

[Prime]

...

You are very correct about the equilibrium in the problem, that is the beauty (I think) to the actual solution. However, I have a different solution that uses less coins. Let me point out where I start to differ from your thinking:

What happens if the Captain proposes to vote off P3 (the pirate in the last position)? (This is where the importance of the shift I was talking about earlier comes in...P1 and P2 are left with a choice b/w two possible shifts)

I see... You mean 5th round when there are captain and three crewmen left (C, P1, P2, P3). Indeed, it appears, in that case P2 has a tangible reason to vote with the captain to kick off P3 even without any pay in order to avoid P1 position in the next round. If you project same reasoning to the rounds before, it would seem always be the case for P2. That leads to a bit of a paradox though, as I mentioned before. For if P2 sticks to that logic, it encourages the captain not to pay for his position. So in a way his position becomes like P1 for earlier rounds. That in turn leads to further regression to P3, P4, etc..

On the other hand, if P2 breaks this strategy, the line moves along, and in 2 turns P2 can end up in the position of the captain. Also, note that there is hardly a reason for P2 to reject payoff at any time. And that would be the way for captain to ensure own position.

So the real question here is can Captain risk his position and not pay P2?

This problem has the element of famous "Unexpected Hanging" paradox. Which has been posted on the forum under "Drop Quiz" title.

I'm still leaning towards the idea that Captain cannot save any money by counting on P2's vote in any round, even the 5th.

Edited October 20, 2008 by Prime

[Yoruichi-san]

I see... You mean 5th round when there are captain and three crewmen left (C, P1, P2, P3). Indeed, it appears, in that case P2 has a tangible reason to vote with the captain to kick off P3 even without any pay in order to avoid P1 position in the next round. If you project same reasoning to the rounds before, it would seem always be the case for P2. That leads to a bit of a paradox though, as I mentioned before. For if P2 sticks to that logic, it encourages the captain not to pay for his position. So in a way his position becomes like P1 for earlier rounds. That in turn leads to further regression to P3, P4, etc..

On the other hand, if P2 breaks this strategy, the line moves along, and in 2 turns P2 can end up in the position of the captain. Also, note that there is hardly a reason for P2 to reject payoff at any time. And that would be the way for captain to ensure own position.

So the real question here is can Captain risk his position and not pay P2?

This problem has the element of famous "Unexpected Hanging" paradox. Which has been posted on the forum under "Drop Quiz" title.

I'm still leaning towards the idea that Captain cannot save any money by counting on P2's vote in any round, even the 5th.

It's not a paradox...the pirate's preference is based on the gold they have when they leave the game, not on getting paid every round...actually that's the beauty of the solution...each pirate who votes yes is trapped in an equilibrium in which they know that only if they keep voting yes, will "payday" (i.e. the round where they receive the bribe) come, if they vote no, the shift changes so that they lose the position to receive a bribe and they cannot get back in position through any action of their own. There is no paradox about it, just delayed rewards, if you want to think about it that way.

Edit: That said, the solution still awaits revealing ;P

Edited October 21, 2008 by Yoruichi-san

[Guest]

Ok, what's wrong with this solution to the benevolent problem?

The captain nominates pirate 2

For the other pirates, this will move them closer to becoming captain* whether or not they vote for or against the captain.

There are no bribes offered.... so the only factor influencing the vote is whether or not they want to see the captain walk the plank. They are benevolent, so will always vote with the captain.

No bribery required.

*or, given that the pirates know that the captain is an amazing game theorist, they could judge that there is no possible way in which they can win, and thus ignore the whole 'getting closer to the captaincy' factor.

[Prime]

Ok, what's wrong with this solution to the benevolent problem?

The captain nominates pirate 2

For the other pirates, this will move them closer to becoming captain* whether or not they vote for or against the captain.

There are no bribes offered.... so the only factor influencing the vote is whether or not they want to see the captain walk the plank. They are benevolent, so will always vote with the captain.

No bribery required.

*or, given that the pirates know that the captain is an amazing game theorist, they could judge that there is no possible way in which they can win, and thus ignore the whole 'getting closer to the captaincy' factor.

I think benevolence/malevolence introduces an extra condition, which does not make problem more deterministic, but just adds another variable to tackle. Benevolence succumbs to greed. And it seems to go against financial interest here. There is much open to dispute without that extra factor. Let's save it for later.

I'm guessing, what Y-S is going for is something as following:

Let's traverse possibilities starting from end, as usual.

1). C, P1: Captain kicks P1 out without paying anything.

2). C, P1, P2: Captain designates any of the two men off the ship and pays P2. P2 must accept, for he has no chance of becoming captain and that's the last time he would be offered any money.

3). C, P1, P2, P3: Captain designates P3 off the ship. P2 votes with captain without any pay, as he expects to be paid in the next round. On the other hand, if he votes against, then he inherits non-paying dead end P1 position.

4). C, P1, P2, P3, P4: Captain can designate either P3, or P4 off the ship, but must pay to P4. Pirate P4 must accept. One way or another he ends up in losing position after that round -- either off the ship, or in unpaid dead end position P3. This is his last chance to get anything. P2 votes with the captain for the same reason as in the previous round -- to avoid P1 position.

5). C, P1, P2, P3, P4, P5: Captain designates P5 off the ship. P2 and P4 vote with the captain without pay to avoid odd-numbered nonpaying dead end positions.

And so on, and so forth. We can call this system "odd man out".

It seems like captain stands to save a whole lot of money. However, I am not convinced by such solution.

[Yoruichi-san]

I think benevolence/malevolence introduces an extra condition, which does not make problem more deterministic, but just adds another variable to tackle. Benevolence succumbs to greed. And it seems to go against financial interest here. There is much open to dispute without that extra factor. Let's save it for later.

I'm guessing, what Y-S is going for is something as following:

Let's traverse possibilities starting from end, as usual.

1). C, P1: Captain kicks P1 out without paying anything.

2). C, P1, P2: Captain designates any of the two men off the ship and pays P2. P2 must accept, for he has no chance of becoming captain and that's the last time he would be offered any money.

3). C, P1, P2, P3: Captain designates P3 off the ship. P2 votes with captain without any pay, as he expects to be paid in the next round. On the other hand, if he votes against, then he inherits non-paying dead end P1 position.

4). C, P1, P2, P3, P4: Captain can designate either P3, or P4 off the ship, but must pay to P4. Pirate P4 must accept. One way or another he ends up in losing position after that round -- either off the ship, or in unpaid dead end position P3. This is his last chance to get anything. P2 votes with the captain for the same reason as in the previous round -- to avoid P1 position.

5). C, P1, P2, P3, P4, P5: Captain designates P5 off the ship. P2 and P4 vote with the captain without pay to avoid odd-numbered nonpaying dead end positions.

And so on, and so forth. We can call this system "odd man out".

It seems like captain stands to save a whole lot of money. However, I am not convinced by such solution.

Yep, that is how the solution works. And you yourself did a good job of showing how it works.

The Captain has the control over the agenda. By proposing the correct pirate to vote off, he manipulates each round so that the choice for the "yes" pirates between voting him planked and voting the pirate off causes different shifts in their positions, one to a gold-getting position and one to a non-gold position. This is a good example of how powerful control over the agenda is ;P.

And it works because each round is only played once, and there is no going back, and everyone is aware of it. Once the Captain makes his proposal for the round the choice b/w the two positions for each of the pirates is clear, and the pirates must act in their own self-interest, with no chance of changing the proposal or bribe amounts. And they know the Captain will act in his own self-interest as well, and will minimize his expenditures. And the Captain has all the power .

[Prime]

Yep, that is how the solution works. And you yourself did a good job of showing how it works.

The Captain has the control over the agenda. By proposing the correct pirate to vote off, he manipulates each round so that the choice for the "yes" pirates between voting him planked and voting the pirate off causes different shifts in their positions, one to a gold-getting position and one to a non-gold position. This is a good example of how powerful control over the agenda is ;P.

And it works because each round is only played once, and there is no going back, and everyone is aware of it. Once the Captain makes his proposal for the round the choice b/w the two positions for each of the pirates is clear, and the pirates must act in their own self-interest, with no chance of changing the proposal or bribe amounts. And they know the Captain will act in his own self-interest as well, and will minimize his expenditures. And the Captain has all the power .

But I am not convinced that solution is correct!

So the greedy captain makes a bad offer putting his neck on the line, and half the pirates must go with it just because the captain is commited and cannot take his offer back? This whole system relies on the assumption that everyone believes such solution is the correct one.

But I don't believe it. Now, let's say Youichi-san is the captain and Unreality is in the position of the first mate (P1). Let's further assume Unreality is of the same frame of mind with Y-s (captain) with respect to that problem. I am in the P2 position and there is a whole bunch of greedy disagreeable pirates behind me. Won't I prove the solution wrong by becoming a pirate king? Note that the pirates in the even positions will end up two steps closer to the captain in the even positions again.

[Yoruichi-san]

But I am not convinced that solution is correct!

So the greedy captain makes a bad offer putting his neck on the line, and half the pirates must go with it just because the captain is commited and cannot take his offer back? This whole system relies on the assumption that everyone believes such solution is the correct one.

But I don't believe it. Now, let's say Youichi-san is the captain and Unreality is in the position of the first mate (P1). Let's further assume Unreality is of the same frame of mind with Y-s (captain) with respect to that problem. I am in the P2 position and there is a whole bunch of greedy disagreeable pirates behind me. Won't I prove the solution wrong by becoming a pirate king? Note that the pirates in the even positions will end up two steps closer to the captain in the even positions again.

Uh...I don't really understand your argument, sorry. If the player in P2 votes no, he now is in an odd position, and is no longer in line for gold. Only if another player in another round who is in line for gold votes no will he be back in a position to gain gold. There is no reason for this other pirate to lose his position for gold once he gains it, unless he makes a deal with P2, but I've stated that we assume that's not allowed in this game (b/c the rounds go too fast and no contact b/w pirates is allowed or something). And it's not what ppl believe...you yourself have shown that it's the logical and rational solution. It seems too good to be true, but it isn't...it works just like the original Pirate's Game (by which I mean the Game Theory scenario which is well established and accepted...try google or wikipedia), except the addition of the shift.

(lol...and where are the other BrainDenizens when you need them...)

But honestly, by logical reasoning the solution works, and is beautiful. So there's nothing else I can say to convince you if you aren't convinced.

On the other hand, if you think you have found a flaw in the Pirate's Game, you could make quite a name for yourself by publishing a paper on it...but that's not something you can accomplish in this thread in this forum .

Edit: Lol...and you could at least spell my name right...

Edited October 22, 2008 by Yoruichi-san

[Yoruichi-san]

Uh...I don't really understand your argument, sorry. If the player in P2 votes no, he now is in an odd position, and is no longer in line for gold. Only if another player in another round who is in line for gold votes no will he be back in a position to gain gold. There is no reason for this other pirate to lose his position for gold once he gains it, unless he makes a deal with P2, but I've stated that we assume that's not allowed in this game (b/c the rounds go too fast and no contact b/w pirates is allowed or something).

To make this more clear, if P2 votes no and planks the Captain, he and the other pirates who were in gold-getting positions (P-Evens) are no longer in gold getting positions, and the P-Odds are now in gold getting positions. But now P1 is the new Captain. In order to become Pirate King P2 (the original P2) needs help, i.e. one of the ppl who are now in gold getting positions (P-odds) to vote no. But doing that shifts the gold-getting positions back to P-Evens, leaving the P-Odds with nothing. Since only the Captain can bribe, the P-Odds have no incentive for voting no and helping P2 become Pirate King, since that would take them from a gold-getting position to non-gold-getting positions. So P2 can't become Pirate King and now P2 will leave the game with no gold. So voting no puts him in a strictly worse position than voting yes in the original round, so he will vote yes.

Edit: Clarification

Edited October 22, 2008 by Yoruichi-san

[Prime]

It does not have to be P2 who initiates the shift. It could be P4 or P6, or someone down the line if there are more pirates. My point is, the odd-man-out solution relies on faith. Within its framework, even-numbered pirates vote with the captain to avoid "dead end" odd positions. However, if pirates do not vote with the captain, the odd-numbered positions are no longer dead end.

There exists another scheme of bribery, whereby captain pays more money and any of the remaining pirates have a chance to get some of it. Seeing that the odd-man-solution has not worked for the late captain, the new one may switch to that other scheme; and, given a sufficient number of pirates remaining, pirates get paid more.

To make a specific example:

In odd-man-out scheme, Captain pays total of 3 coins in the course of the entire game -- to P6, P4, and P2 at different stages. In the Captain-to-make-sure-to-stay-alive scheme, captains pays 12 coins for the duration of the game, which can go to anyone, except P1. Now consider P4 position in the very first round. If he votes Aye without pay, then he is voting for the odd-man-out scheme and stands to earn one gold coin. If he votes Nay, then he votes for the alternative scheme, where captain is still to pay 9 coins to be split in some random fashion between 5 pirates. This way P4's (who became P3) earning expectancy is 1.8 gold coins.

Granted, the alternative scheme is also faith based. Still, when new captain sees that pirates do not wish to stick to the money saving odd-man-out scheme, he may be compelled to try and settle for something more expensive. This is pirates' way force the agenda, even though, captain moves first.

Perhaps, there is a way to settle this issue definitively. We could try to apply the old mini-max algorithm here modified to work for multiple-player game. Also, we may need to set a limit for each individual bribe; otherwise, the problem may not have a definitive solution.

Sorry about misspelling your name, Yoruichi-san. My keboad does not repond to key-press from time to tme. Perhaps, for that reason I don't attempt to write books, or researh papers.

[Yoruichi-san]

It does not have to be P2 who initiates the shift. It could be P4 or P6, or someone down the line if there are more pirates. My point is, the odd-man-out solution relies on faith. Within its framework, even-numbered pirates vote with the captain to avoid "dead end" odd positions. However, if pirates do not vote with the captain, the odd-numbered positions are no longer dead end.

There exists another scheme of bribery, whereby captain pays more money and any of the remaining pirates have a chance to get some of it. Seeing that the odd-man-solution has not worked for the late captain, the new one may switch to that other scheme; and, given a sufficient number of pirates remaining, pirates get paid more.

To make a specific example:

In odd-man-out scheme, Captain pays total of 3 coins in the course of the entire game -- to P6, P4, and P2 at different stages. In the Captain-to-make-sure-to-stay-alive scheme, captains pays 12 coins for the duration of the game, which can go to anyone, except P1. Now consider P4 position in the very first round. If he votes Aye without pay, then he is voting for the odd-man-out scheme and stands to earn one gold coin. If he votes Nay, then he votes for the alternative scheme, where captain is still to pay 9 coins to be split in some random fashion between 5 pirates. This way P4's (who became P3) earning expectancy is 1.8 gold coins.

Granted, the alternative scheme is also faith based. Still, when new captain sees that pirates do not wish to stick to the money saving odd-man-out scheme, he may be compelled to try and settle for something more expensive. This is pirates' way force the agenda, even though, captain moves first.

Perhaps, there is a way to settle this issue definitively. We could try to apply the old mini-max algorithm here modified to work for multiple-player game. Also, we may need to set a limit for each individual bribe; otherwise, the problem may not have a definitive solution.

Sorry about misspelling your name, Yoruichi-san. My keboad does not repond to key-press from time to tme. Perhaps, for that reason I don't attempt to write books, or researh papers.

The solution does not work on faith, it works on sound logic and based on the idea that each pirate is only looking out for the results of their own actions. My argument for P2 works just as well if not better for P4 and P6, who have less chances of being Pirate King. There is no flaw in the logic.

Yes, it seems like a very specific equilibrium, but it is an equilibrium that is found using sound logic. If there is "faith" it is the same kind of "faith" that the astronauts who go into space have that the scientists who worked on the shuttle did all the calculations correctly, since one small error could cost them their lives. But they know that based on the theories of physics and chemistry and rocket science, the mission should be safe if all the science and math was done correctly. Here the "faith" is that the other pirates will do the logic correctly, and since this is a theoretical situation, we assume they do.

[Prime]

The solution does not work on faith, it works on sound logic and based on the idea that each pirate is only looking out for the results of their own actions. My argument for P2 works just as well if not better for P4 and P6, who have less chances of being Pirate King. There is no flaw in the logic.

Yes, it seems like a very specific equilibrium, but it is an equilibrium that is found using sound logic. If there is "faith" it is the same kind of "faith" that the astronauts who go into space have that the scientists who worked on the shuttle did all the calculations correctly, since one small error could cost them their lives. But they know that based on the theories of physics and chemistry and rocket science, the mission should be safe if all the science and math was done correctly. Here the "faith" is that the other pirates will do the logic correctly, and since this is a theoretical situation, we assume they do.

Oh, let's return from space onto our ship. We are pirates -- not astronauts.

Tell me what's wrong with the following example:

Given a situation where captain ( C ) and his first mate (P1) believe into the same logic as you as strongly as you.

Whereas, P2 and P5 have equal faith in the alternative system. Then the alternative system wins. The ex-captain and P1 both lost (walked the board) due to their actions. P2 moved to captain's position and eventually became pirate king. P5 moved into P3 position, which became a potentially paying position under the new captain. (Under alternative system, captain is due to hand out 6 coins for the remainder of the game. Which makes it 1.5 coin payoff expectancy per pirate. Whereas, originally P5's payoff expectancy was 0.)

Edited October 23, 2008 by Prime

[Yoruichi-san]

Oh, let's return from space onto our ship. We are pirates -- not astronauts.

Tell me what's wrong with the following example:

Given a situation where captain ( C ) and his first mate (P1) believe into the same logic as you as strongly as you.

Whereas, P2 and P5 have equal faith in the alternative system. Then the alternative system wins. The ex-captain and P1 both lost (walked the board) due to their actions. P2 moved to captain's position and eventually became pirate king. P5 moved into P3 position, which became a potentially paying position under the new captain. (Under alternative system, captain is due to hand out 6 coins for the remainder of the game. Which makes it 1.5 coin payoff expectancy per pirate. Whereas, originally P5's payoff expectancy was 0.)

Each pirate thinks "what would I do if I were in the Captain's position and wanted to maximize my preferences, becoming Pirate King and spending the least amount of gold to do so so I can leave with the most gold left", and they assume the Captain will do that. The alternative system works, but is not optimal towards maximizing the Captains preferences, and his goal is to maximize his preferences, and they all know that. And the Captain has the power over the agenda.

No pirate can effect a positive change by his own action, each pirate can't trust another pirate to help him at the expense of their own preferences, so each pirate is trapped in the equilibrium.