[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?

[Yoruichi-san]

Oops, I forgot to clarify one thing...but actually it brings up a good exercise, so answer the question in these cases:

I. They're malevolent pirates, given their first two preferences, their third preference is to see someone walk the plank.

II. They're benevolent pirates, given their first two preferences, their third preference is not to see someone walk the plank.

Edit: Being voted off the ship is not the same as walking the plank. If they're voted off, they leave alive with their accumulated gold .

Edited October 16, 2008 by Yoruichi-san

[Guest]

I am not sure I understand the rules clearly. If I understand:

8 crew - does this include the starting captain? (I assume yes)

Pirates will always vote in a manner that makes them a captain ... including long shots (meaning newbie would effectively never need to be bribed)?

if my understanding is correct, then my answer is:

Either the Captain can never win because the final vote will be captain vs whomever and that person cannot be bribed not to become the captain (1 to 1 vote == 50% for no so the captain walks the plank).

OR

1 Gold - Captain always proposes current #2, so all others vote that person out as it makes themselves as close to captain as if the current captain left except the final vote in which the captain must bribe to win.

[Guest]

I am not sure I understand the rules clearly. If I understand:

8 crew - does this include the starting captain? (I assume yes)

Pirates will always vote in a manner that makes them a captain ... including long shots (meaning newbie would effectively never need to be bribed)?

if my understanding is correct, then my answer is:

Either the Captain can never win because the final vote will be captain vs whomever and that person cannot be bribed not to become the captain (1 to 1 vote == 50% for no so the captain walks the plank).

OR

1 Gold - Captain always proposes current #2, so all others vote that person out as it makes themselves as close to captain as if the current captain left except the final vote in which the captain must bribe to win.

You've analysed the 1:1 case wrong - the wording is "If half or more of the remaining pirates vote yes, the proposal is followed" so in this case half (ie the captain) would vote for the proposal and it passes.

In the case of benevolent pirates, your second solution is almost there - except the final pirate doesn't need bribing. The captain can outvote him on his own.

During the earlier votes, the pirates below the second rank have the choice between voting for number 2 to get fired, or (effectively) voting for the captain to walk the plank. Both outcomes would bring them nearer to captaincy (so preference 1 doesn't come into play), and in the absence of bribery the pirates' malevolence is the deciding factor - malevolent pirates would vote no and see the captain plank walk; benevolent ones vote yes and see the number 2 get the sack.

So, the malevolent situation is the 'interesting' one:

A winning strategy would be to bribe three pirates the first and second rounds (to get 4:4 and 4:3 votes) two in rounds three and four (3:3 and (3:2) one in round four and five (2:2 and 2:1) and no-one in the final round. The pirates you bribe would have to be ones lower in rank than the pirate you have nominated (else preference 1 comes into play and overides the bribes) so simplest strategy is to nominate pirate 2 each time and bribe the lowest ranked pirates. 12 bribes are needed overall.

[Yoruichi-san]

You've analysed the 1:1 case wrong - the wording is "If half or more of the remaining pirates vote yes, the proposal is followed" so in this case half (ie the captain) would vote for the proposal and it passes.

In the case of benevolent pirates, your second solution is almost there - except the final pirate doesn't need bribing. The captain can outvote him on his own.

During the earlier votes, the pirates below the second rank have the choice between voting for number 2 to get fired, or (effectively) voting for the captain to walk the plank. Both outcomes would bring them nearer to captaincy (so preference 1 doesn't come into play), and in the absence of bribery the pirates' malevolence is the deciding factor - malevolent pirates would vote no and see the captain plank walk; benevolent ones vote yes and see the number 2 get the sack.

So, the malevolent situation is the 'interesting' one:

A winning strategy would be to bribe three pirates the first and second rounds (to get 4:4 and 4:3 votes) two in rounds three and four (3:3 and (3:2) one in round four and five (2:2 and 2:1) and no-one in the final round. The pirates you bribe would have to be ones lower in rank than the pirate you have nominated (else preference 1 comes into play and overides the bribes) so simplest strategy is to nominate pirate 2 each time and bribe the lowest ranked pirates. 12 bribes are needed overall.

Good thinking, but you're forgetting two things...the preference is based on the amount of coins that the pirates have when they leave the ship, so you may not need to give a bribe to a pirate a particular round if they know they're going to get a bribe in future rounds , and don't forget that their #1 preference is to be Pirate King, then gold, then benevolence/malevolence...

Edited October 16, 2008 by Yoruichi-san

[Yoruichi-san]

Sorry, I was trying to clarify a point by adding the addendum, but I guess I made the problem more confusing. What I meant was, that assuming that preference #2 takes priority, i.e. if they know they will get a bribe at some point, they vote yes, if they know they won't, they vote no, assuming that, the malevolence/benevolence clarifies ambiguous cases. That's the problem that was meant. Sorry if that was confusing.

The point is

where the order shifts depending on who is voted off, etc...and you want to find the ideal shift to minimize your expenditure.

[Prime]

Do pirates know their succession order?

I mean…

Captain’s position in the early stage of the game is rather unfortunate. She does not earn any bribe money, but rather spends it, and risks walking the plank any round.

[Yoruichi-san]

Do pirates know their succession order?

I mean…

Captain’s position in the early stage of the game is rather unfortunate. She does not earn any bribe money, but rather spends it, and risks walking the plank any round.

Yes, the pirates have a ranking from the beginning and it is known. Actually the Captain is lucky b/c he is in the best position to become the Pirate King, which is the #1 priority.

[Prime]

Couple more things need clarification.

Does off-the-ship candidate participate in voting?

Is captain the only one who can bribe other pirates?

[Yoruichi-san]

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.

[Prime]

What stops a pirate from taking a bribe and voting against the captain anyway? This way he gets money and fun. His position for succession is the only thing to take into consideration then. Or do pirates have some kind of honor code requiring them to follow through on an agreement?

Also, there is no sense for pirates to be benevolent. Benevolence does not pay. The pirates should vote against the captain by default, even if only to encourage him to pay bribes.

Assuming there is an honor code, and the off-the-ship candidate does not vote...

When there are only 2 crewmen, captain can vote them off one by one and become a king.

When there are 3 crewmen, captain can bribe one of them and get his way again. The question is: can captain bribe the 1st man in succession? If there is an honor code, then he can. For the first crewman must understand, if he refuses the bribe, the captain will get his way regardless by bribing someone else. Clever pirates also understand that there is no reason for the 3rd crewman to refuse the bribe, as he has no chance of becoming pirate king.

So any time, the last two men in succession know there is no chance for them to become kings, no matter what happens. From the onset, when there are 8 men (including the captain, I presume), the last 2 totally bribable pirates together with their captain constitute a minority. Does it make sense for others to resist bribe attempts? The first crewman stands to get the captain's position, which becomes unshakable when only 7 men left. However, all other pirates only stand to lose money by refusing the bribe. Since the first crewman understands that, he must accept the bribe too.

Conclusion:

1. All pirates must vote against captain, unless bribed and bound by honor code.

2. Captain must bribe enough men each round to make the majority. It turns out, it does not matter, which of the crewman the captain picks to vote off the ship (the most principled ones first), nor does it matter which crewmen he bribes (the more agreeable ones). Captain pays 3 coins in the first round, 2 coins in the second and third, and 1 coin in the fourth and fifth rounds for a total of 9 coins.

[Yoruichi-san]

What stops a pirate from taking a bribe and voting against the captain anyway? This way he gets money and fun. His position for succession is the only thing to take into consideration then. Or do pirates have some kind of honor code requiring them to follow through on an agreement?

Also, there is no sense for pirates to be benevolent. Benevolence does not pay. The pirates should vote against the captain by default, even if only to encourage him to pay bribes.

Assuming there is an honor code, and the off-the-ship candidate does not vote...

When there are only 2 crewmen, captain can vote them off one by one and become a king.

When there are 3 crewmen, captain can bribe one of them and get his way again. The question is: can captain bribe the 1st man in succession? If there is an honor code, then he can. For the first crewman must understand, if he refuses the bribe, the captain will get his way regardless by bribing someone else. Clever pirates also understand that there is no reason for the 3rd crewman to refuse the bribe, as he has no chance of becoming pirate king.

So any time, the last two men in succession know there is no chance for them to become kings, no matter what happens. From the onset, when there are 8 men (including the captain, I presume), the last 2 totally bribable pirates together with their captain constitute a minority. Does it make sense for others to resist bribe attempts? The first crewman stands to get the captain's position, which becomes unshakable when only 7 men left. However, all other pirates only stand to lose money by refusing the bribe. Since the first crewman understands that, he must accept the bribe too.

Conclusion:

1. All pirates must vote against captain, unless bribed and bound by honor code.

2. Captain must bribe enough men each round to make the majority. It turns out, it does not matter, which of the crewman the captain picks to vote off the ship (the most principled ones first), nor does it matter which crewmen he bribes (the more agreeable ones). Captain pays 3 coins in the first round, 2 coins in the second and third, and 1 coin in the fourth and fifth rounds for a total of 9 coins.

Umm...good thinking, and yes, the Pirates are bound to follow the rules of the Game (they are on National Television, after all ;P), but I guess I took it for granted that everyone attempting this problem would be familiar w/ the Pirates Game, and so I neglected to mention that all pirates are basically game theory experts, and I apologize for that. For example, in the original Pirates Game, the solution is found by working backwards, i.e. in the last round, where there are two pirates remaining and the last ranked pirate knows there is nothing he can do to get any of his preferences, so the round beforehand he will vote yes if he gets a bribe and no if he doesn't. Now he knows he will get a bribe in the second to last round as long as he is in that position in that round, so the rest of the decisions will depend on how he can remain in a position to receive the bribe.

I know the original Pirate's Game has been posted here, I believe if you do a search for "pirates" and "gold" you will find it.

The benevolence/malevolence is to clarify cases where there is ambiguity. For example, say Pirate A is currently in position 4, and he knows that if he is in position 3 next round he will get a bribe. However, he will be in position 3 regardless of whether he votes off the first mate or he votes to have the Captain planked, so there is ambiguity. The benevolence/malevolence clears this up: if he is benevolent, he will vote off the first mate, if he is malevolent, he will vote to have the Captain planked (unless there is another bribe).

I hope that helps. I admit this is a very theoretical Game Theory problem, but I think it is an interesting one.

[Prime]

Umm...good thinking, and yes, the Pirates are bound to follow the rules of the Game (they are on National Television, after all ;P), but I guess I took it for granted that everyone attempting this problem would be familiar w/ the Pirates Game, and so I neglected to mention that all pirates are basically game theory experts, and I apologize for that. For example, in the original Pirates Game, the solution is found by working backwards, i.e. in the last round, where there are two pirates remaining and the last ranked pirate knows there is nothing he can do to get any of his preferences, so the round beforehand he will vote yes if he gets a bribe and no if he doesn't. Now he knows he will get a bribe in the second to last round as long as he is in that position in that round, so the rest of the decisions will depend on how he can remain in a position to receive the bribe.

...

I don't know the original game. However, for this one I've shown that it does not matter, which of the pirates captain chooses to vote off the ship, nor does it matter which pirates he choses to bribe. Captain flips a coin to chose who to vote off and who to bribe, spends total of 9 coins, and keeps his position. If he tries to spend less -- he walks the plank. But that does not happen, as he is a game expert. Is there anything else to solve here?

For example, if you are a first crewman in succession, and the captain offers you a bribe -- you should take it and consequently vote with the captain. Refusing would only lose you money and not gain anything at all. Same for all other pirates. That works as long as all pirates are game experts and understand how to maximize their win. Being closer or further away in succession order carries no advantage in this set-up. "Benevolence" has no place in this arrangement. It means less chance of bribe to pirates, so it should never be a consideration.

[Yoruichi-san]

I don't know the original game. However, for this one I've shown that it does not matter, which of the pirates captain chooses to vote off the ship, nor does it matter which pirates he choses to bribe. Captain flips a coin to chose who to vote off and who to bribe, spends total of 9 coins, and keeps his position. If he tries to spend less -- he walks the plank. But that does not happen, as he is a game expert. Is there anything else to solve here?

For example, if you are a first crewman in succession, and the captain offers you a bribe -- you should take it and consequently vote with the captain. Refusing would only lose you money and not gain anything at all. Same for all other pirates. That works as long as all pirates are game experts and understand how to maximize their win. Being closer or further away in succession order carries no advantage in this set-up. "Benevolence" has no place in this arrangement. It means less chance of bribe to pirates, so it should never be a consideration.

No, the point is that the Captain doesn't flip a coin, he chooses wisely which ones to vote off. The pirate in the last position knows he will get a bribe in the second to last round as long as he stays in the last position. "Benevolence" means that he would rather vote with the Captain to remove a player from the ship than to plank the Captain each round. And the Captain knows that he doesn't have to bribe the last position pirate as long as he keeps voting off pirates in front of him, until the second to last round.

And in my last post, I answered your question...there is no double-crossing as they must play by the rules in the Game.

[Yoruichi-san]

Looking at my solution again, I realized Prime was correct about the "benevolence" thing not having a place...I realized I can do it with no benevolence/malevolence specification, as long as I choose the correct pirate to vote off. And the solution actually works better without that uncertainty. I still get the same minimum bribe number . I apologize for all the confusion, forget about that part. Just go with the OP and the clarifications that were asked for if you need them .

[Prime]

No, the point is that the Captain doesn't flip a coin, he chooses wisely which ones to vote off. The pirate in the last position knows he will get a bribe in the second to last round as long as he stays in the last position. "Benevolence" means that he would rather vote with the Captain to remove a player from the ship than to plank the Captain each round. And the Captain knows that he doesn't have to bribe the last position pirate as long as he keeps voting off pirates in front of him, until the second to last round.

And in my last post, I answered your question...there is no double-crossing as they must play by the rules in the Game.

I read the original problem where 5 pirates divi up 100 gold coins. Captain gets to keep 98 quite obviously. The logic in that puzzle is simple, straightforward, unambiguous and it does not apply here at all. In that puzzle, correct analysis leads to a single round.

There is no such thing as "the pirate in the last position knows he will get a bribe in the second to last round". You must have missed that bit in my analysis. I devoted a whole paragraph to it.

When there are 2 men left beside the captain, the captain choses one to throw off the ship and his own vote is enough to do so according to your conditions. The last man shares the same fate. None of them gets any money. So in the round before that when there are 3 men left beside the captain, any pirate must accept bribe, as it is the last chance to get paid. If the bribe is offered to the first mate who stands to become captain, should captain fail -- he should accept the bribe too, if he knows what's good for him. For if he refuses, the captain will simply walk over to the next pirate and offer bribe to him. And for 2nd and 3rd men that's the last chance to make any money as well as for the first. So there is no guaranty, which pirate gets the bribe. No pirate can count on anything here. And pirate's succession position bears no significance in this setup. Unlike the original pirate problem.

[Yoruichi-san]

I read the original problem where 5 pirates divi up 100 gold coins. Captain gets to keep 98 quite obviously. The logic in that puzzle is simple, straightforward, unambiguous and it does not apply here at all. In that puzzle, correct analysis leads to a single round.

There is no such thing as "the pirate in the last position knows he will get a bribe in the second to last round". You must have missed that bit in my analysis. I devoted a whole paragraph to it.

When there are 2 men left beside the captain, the captain choses one to throw off the ship and his own vote is enough to do so according to your conditions. The last man shares the same fate. None of them gets any money. So in the round before that when there are 3 men left beside the captain, any pirate must accept bribe, as it is the last chance to get paid. If the bribe is offered to the first mate who stands to become captain, should captain fail -- he should accept the bribe too, if he knows what's good for him. For if he refuses, the captain will simply walk over to the next pirate and offer bribe to him. And for 2nd and 3rd men that's the last chance to make any money as well as for the first. So there is no guaranty, which pirate gets the bribe. No pirate can count on anything here. And pirate's succession position bears no significance in this setup. Unlike the original pirate problem.

No, if there are two men besides the Captain, the Pirate in first mate position will never vote yes b/c his #1 priority is to become Pirate King, no matter how much gold he is offered, like in the original Pirates Game, where the #1 preference was to be Captain. So the Captain will offer the last positioned pirate a bribe in the second to last round.

[Prime]

Also, in the original puzzle the man dividing up gold was a voter as well. Here I asked for clarification whether the off-the-ship candidate votes and the answer was -- no. If that's not the case, the amount of bribes changes, but not the essense of the solution.

[Yoruichi-san]

Also, in the original puzzle the man dividing up gold was a voter as well. Here I asked for clarification whether the off-the-ship candidate votes and the answer was -- no. If that's not the case, the amount of bribes changes, but not the essense of the solution.

The man dividing up the gold was the Captain...and the Captain is a voter...?

[Prime]

No, if there are two men besides the Captain, the Pirate in first mate position will never vote yes b/c his #1 priority is to become Pirate King, no matter how much gold he is offered, like in the original Pirates Game, where the #1 preference was to be Captain. So the Captain will offer the last positioned pirate a bribe in the second to last round.

Then the first mate is dumb. He is not versed in game theory. His decision will only lose him money, but not gain any position.

Note, unlike the original pirate puzzle, where captain divides money and puts it up for voting, without any chance of changing anything if it does not go his way, here captain can make rounds offerening bribes to anyone.

If you don't believe me, conduct a trial game. Be a captain, and as far as pirates are concerned stick to this strategy: vot Aye if you got a bribe, and Nay if you didn't. Try choosing different men to vote off the ship. See how much pirates earn collectively if they refuse reasonable bribe offer, versus when they don't. Remember as a captain you can offer bribe to anyone. Try offering it to the first man in succession first before going to the next pirate. See if the first man ends up better off when refusing the bribe.

[Prime]

The man dividing up the gold was the Captain...and the Captain is a voter...?

You refered me to the original pirates' puzzle, and I read and solved it before returning here.

[Prime]

Or are we refering to different puzzles. There are so many copies of those. I am talking about 5 pirates dividing 100 gold coins. Where first pirate offers how to split the loot and votes with the others on whether to accept his proposal.

[Yoruichi-san]

Then the first mate is dumb. He is not versed in game theory. His decision will only lose him money, but not gain any position.

Note, unlike the original pirate puzzle, where captain divides money and puts it up for voting, without any chance of changing anything if it does not go his way, here captain can make rounds offerening bribes to anyone.

If you don't believe me, conduct a trial game. Be a captain, and as far as pirates are concerned stick to this strategy: vot Aye if you got a bribe, and Nay if you didn't. Try choosing different men to vote off the ship. See how much pirates earn collectively if they refuse reasonable bribe offer, versus when they don't. Remember as a captain you can offer bribe to anyone. Try offering it to the first man in succession first before going to the next pirate. See if the first man ends up better off when refusing the bribe.

The first mate may be dumb, but that's just the way his priorities are set. He wants to be Captain/Pirate King more than he wants to have money (must be all those endorsement deals ;P).

And the pirates don't "collectively" do anything...there are no coalitions formed, they don't make a pact to refuse the offer unless it is above some set amount, they just look out for themselves. I understand that you're thinking that in a multi-round game coalitions usually form in social experiments, but as I said before, I admit this is a very theoretical problem, but that's the way the problem is. You should know that I respect your abilities in math and logical reasoning, and I do think your solution works well for the way you interpreted the problem. However, that is not what the OP was intended to be. The fact that I based the characters on cartoon characters hopefully suggests that this is not a real-life situation, but a theoretical one ;P.

I made this puzzle to show a very interesting phenomenon, the shifting pirates game, so please respect the way I intended this puzzle to be. Thank you.

[Prime]

The first mate may be dumb, but that's just the way his priorities are set. He wants to be Captain/Pirate King more than he wants to have money (must be all those endorsement deals ;P).

And the pirates don't "collectively" do anything...there are no coalitions formed, they don't make a pact to refuse the offer unless it is above some set amount, they just look out for themselves. I understand that you're thinking that in a multi-round game coalitions usually form in social experiments, but as I said before, I admit this is a very theoretical problem, but that's the way the problem is. You should know that I respect your abilities in math and logical reasoning, and I do think your solution works well for the way you interpreted the problem. However, that is not what the OP was intended to be. The fact that I based the characters on cartoon characters hopefully suggests that this is not a real-life situation, but a theoretical one ;P.

I made this puzzle to show a very interesting phenomenon, the shifting pirates game, so please respect the way I intended this puzzle to be. Thank you.

New puzzles do not necessarilly come out right the first time around. Like computer programs they need testing and debugging. I am not sure what you meant the solution should be, but it's apparent at this point the statement of the problem needs work.

There seems to be a contradiction with the notion that pirates possess perfect reasoning ability. There is a test you can apply to your problem/solution:

Try all variations and see if any of the pirates made a wrong decision when acting according to your scheme. If that's the case, then pirate made a mistake, which contradicts the notion of perfect logic ability in pirates, which we know, all of them possess.

We pretty much zeroed in on the discrepancy here. Test the case where captain attempts to bribe his next successor, before moving on to bribe next pirate. Make best effort on the part of captain. See if the first mate ended up better refusing the bribe vs. taking it. When testing cases where you chose first mate to be voted off the ship, start by offering bribe to the next man. When enough men accepted bribes to secure the vote, captain need not offer more bribes. Check for all cases when any pirate refused bribe, see if that pirate ended up better off.

[Yoruichi-san]

New puzzles do not necessarilly come out right the first time around. Like computer programs they need testing and debugging. I am not sure what you meant the solution should be, but it's apparent at this point the statement of the problem needs work.

There seems to be a contradiction with the notion that pirates possess perfect reasoning ability. There is a test you can apply to your problem/solution:

Try all variations and see if any of the pirates made a wrong decision when acting according to your scheme. If that's the case, then pirate made a mistake, which contradicts the notion of perfect logic ability in pirates, which we know, all of them possess.

We pretty much zeroed in on the discrepancy here. Test the case where captain attempts to bribe his next successor, before moving on to bribe next pirate. Make best effort on the part of captain. See if the first mate ended up better refusing the bribe vs. taking it. When testing cases where you chose first mate to be voted off the ship, start by offering bribe to the next man. When enough men accepted bribes to secure the vote, captain need not offer more bribes. Check for all cases when any pirate refused bribe, see if that pirate ended up better off.

Okay, the statement of the problem does need work, and I should link to the original Pirate's Game. However, the first mate always voting against the captain was established by the original Pirate's Game, and is due to the fact that he values becoming Captain/Pirate King beyond any amount of gold. If you have an argument against this, please direct it to the original Pirate's Game. This spin uses the original Pirates Game but puts a shift on the positions, which is what makes it different and (I think) interesting. The spin does not change the first mate's preference, that was established by the original.

Now instead of arguing here, I believe finding the solution would be much more productive.

And, as for your test...

In my solution, the first mate is never voted off (until the second to last round that is) ;P

Edited October 18, 2008 by Yoruichi-san

[Yoruichi-san]

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 .

Edited October 18, 2008 by Yoruichi-san