Game theory and pirates type problem! [Archive]

CallMeIshmael

03-02-2006, 12:02 AM

The following is taken from espn.com... I believe I have a solution, but Im curious to hear what others get

There are five pirates in a boat, with 100 pieces of gold to divide among them. They decide to divide the gold by the following methodology:

The smallest pirate will distribute the gold, and then each pirate will vote on the distribution. If the smallest pirate gets a clear majority (including himself) to agree on his distribution, then that is the way the gold will be divided. If not, he is thrown overboard and the next smallest pirate will re-divide the gold among the three remaining pirates. They all then vote again with the exact same conditions (acceptance requires a majority, lack of acceptance implies the pirate who divided the gold is thrown overboard and the next smallest pirate takes his place as gold distributor). Each pirate will only accept that outcome that guarantees him the most gold he will get under any scenario. No other consideration can trump that.

The question is this: How many pieces of gold can the smallest pirate keep and remain in the boat?

dun_noo

03-02-2006, 12:12 AM

20 each?

bunny

03-02-2006, 12:20 AM

Does a tied vote count as not-accepted?

New001

03-02-2006, 12:26 AM

[ QUOTE ]
Does a tied vote count as not-accepted?

[/ QUOTE ]
I assume the smallest pirate can vote for himself.

My first thought is to give two pirates nothing, and split the 100 up among the other two pirates and himself. So in white 33 gold?

Edit: Hid it in white.

bunny

03-02-2006, 12:28 AM

I meant what happens when there are only 4 or 2 pirates?

CallMeIshmael

03-02-2006, 12:28 AM

[ QUOTE ]
Does a tied vote count as not-accepted?

[/ QUOTE ]

Im really not an expert in this at all, and Ive given all the info I have.

I took the wording to assume that a tied vote means that the majority was not reached, and therefore the gold dividing pirate goes.

New001

03-02-2006, 12:30 AM

[ QUOTE ]
I meant what happens when there are only 4 or 2 pirates?

[/ QUOTE ]
Well if the smallest pirate (smallest of the five, that is) isn't in the boat anymore, then he took too much gold. Or am I missing something?

CallMeIshmael

03-02-2006, 12:32 AM

[ QUOTE ]
[ QUOTE ]
I meant what happens when there are only 4 or 2 pirates?

[/ QUOTE ]
Well if the smallest pirate (smallest of the five, that is) isn't in the boat anymore, then he took too much gold. Or am I missing something?

[/ QUOTE ]

But actions that WOULD occur if the smallest pirate got voted off are relevant to the solution

mroels

03-02-2006, 12:37 AM

[ QUOTE ]
My first thought is to give two pirates nothing, and split the 100 up among the other two pirates and himself. So in white 33 gold?

Edit: Hid it in white.

[/ QUOTE ]

Either this or 50/50 with only the two biggest pirates left assuming a tied vote will for the split as suggested.

TomCollins

03-02-2006, 12:41 AM

Would a pirate prefer 0 gold to getting thrown overboard?

bunny

03-02-2006, 12:47 AM

OK - seems strange but 95?

My reasoning is - consider what happens if it gets down to three pirates:
smallest pirate remaining offers 99 to himself, 1 to the second smallest and nothing to the biggest. Second smallest will have to accept this as otherwise he is going to be heads up with the biggest pirate (and will get 0).
Thus, top two pirates have to stop this from happening and will do so if the second smallest pirate offers them something better.
Second smallest pirate can offer them 97 for himself, nothing for the middle pirate and 2 and 1 for the second biggest and biggest pirates respectively (the 2 biggest pirates would have to take this as if they rejected it they will be forced to accept the next offer which is worse. Unless, smallest pirate offers them something better instead:

Thus:
Smallest pirate keeps 95 himself, offers nothing to the fourth and third pirates and offers 3 coins to the second biggest pirate and 2 the biggest. If the big two dont accept this, they will never be able to do anything better.

CallMeIshmael

03-02-2006, 12:48 AM

[ QUOTE ]
Would a pirate prefer 0 gold to getting thrown overboard?

[/ QUOTE ]

This was an assumption I made

bunny

03-02-2006, 12:48 AM

Obviously I think this is wrong but I cant work out where /images/graemlins/tongue.gif

mroels

03-02-2006, 01:05 AM

[ QUOTE ]
Would a pirate prefer 0 gold to getting thrown overboard?

[/ QUOTE ]

No

[ QUOTE ]
Each pirate will only accept that outcome that guarantees him the most gold he will get under any scenario. No other consideration can trump that.

[/ QUOTE ]

bunny

03-02-2006, 01:08 AM

[ QUOTE ]
[ QUOTE ]
I meant what happens when there are only 4 or 2 pirates?

[/ QUOTE ]
Well if the smallest pirate (smallest of the five, that is) isn't in the boat anymore, then he took too much gold. Or am I missing something?

[/ QUOTE ]
If he gets thrown overboard then he gets no gold (at least as I read it - the next pirate up "re-distributes" the gold)

Go Blue

03-02-2006, 01:25 AM

[ QUOTE ]
The following is taken from espn.com... I believe I have a solution, but Im curious to hear what others get

There are five pirates in a boat, with 100 pieces of gold to divide among them. They decide to divide the gold by the following methodology:

The smallest pirate will distribute the gold, and then each pirate will vote on the distribution. If the smallest pirate gets a clear majority (including himself) to agree on his distribution, then that is the way the gold will be divided. If not, he is thrown overboard and the next smallest pirate will re-divide the gold among the three remaining pirates. They all then vote again with the exact same conditions (acceptance requires a majority, lack of acceptance implies the pirate who divided the gold is thrown overboard and the next smallest pirate takes his place as gold distributor). Each pirate will only accept that outcome that guarantees him the most gold he will get under any scenario. No other consideration can trump that.

The question is this: How many pieces of gold can the smallest pirate keep and remain in the boat?

[/ QUOTE ]

I believe that I have an answer. You need to work backwards to solve this problem. I will call the pirates by numbers, 1 through 5, with 5 being the tallest one.

The last possible game (n) is that only Pirate 5 remains and he gets to keep everything.

The next to last game (n-1) is that Pirates 4 and 5 remain. Pirate 5 knows that in the next game, he can get everything by voting aginst #4 and will do so unless #4 offers him everything, which he does.

In game (n-2), Pirate 3 knows that the only way that #5 doesn't get everything is if the game ends right now and to do this, he will offer 99 pieces to himself and 1 piece to #4. In this case, only #5 votes against this and thus the game ends (#4 will vote for this becuase he will get nothing otherwise if the game goes on).

In game (n-3), Pirate 2 needs 3 votes to end the game or be thrown overboard (so his own vote plus two others). He knows the outcome of game (n-2) so the only thing he can do is offer #3 99 pieces and #4 1 pieces. He himself and #5 get nothing. This is the only way that both #4 and #3 will vote for this proposition.

Finally, in the first game (n-4), Pirate 1 knows the outcome for the next game (n-3) and he needs 2 more votes besides his own to end the game right there. I believe it should go as follows: If the game goes on, in the next round, #4 will get 1 piece, so he will accept anything greater than 1. Thus #1 offers #4 2 pieces. In addition, #2 will get nothing if the game goes on, so #1 will offer #2 1 piece, and he will accept that. Pirate 1 will keep the remaining 97 pieces and the game will end right there, with #1, #2, and #4 all voting in favor of this. #3 and #5 get nothing.

By the way, all of this is assuming that a tie vote does in fact mean that there is no majority and that the shortest remaining pirate will get thrown overboard.

Edit: Just to be clear:
Pirate #1 (shorest) gets 97.
Pirate #2 gets 1.
Pirate #3 gets 0.
Pirate #4 gets 2.
Pirate #5 (tallest) gets 0.

bunny

03-02-2006, 01:40 AM

[ QUOTE ]
Edit: Just to be clear:
Pirate #1 (shorest) gets 97.
Pirate #2 gets 1.
Pirate #3 gets 0.
Pirate #4 gets 2.
Pirate #5 (tallest) gets 0.

[/ QUOTE ]

I dont think this works -

Pirate #2 will vote against this - evicting pirate 1 because he can then offer 97 to himself, 2 to pirate #4 and 1 to pirate #5 (both of whom will accept as it is better than the three pirate ending).

I think you have to make your offer to pirates #4 and #5 - in my solution, I assumed that the big pirates would vote against if they could be guaranteed of being no worse off.

CallMeIshmael

03-02-2006, 01:58 AM

[ QUOTE ]
In game (n-3), Pirate 2 needs 3 votes to end the game or be thrown overboard (so his own vote plus two others). He knows the outcome of game (n-2) so the only thing he can do is offer #3 99 pieces and #4 1 pieces. He himself and #5 get nothing. This is the only way that both #4 and #3 will vote for this proposition.

[/ QUOTE ]

I disagree here.

The offer of 98,0,1,1 is accepted.

Clearly P2 accepts 98.

P3 rejects 0.

P4 accepts 1 because he is indifferent. Either he gets one this round, or next (this is perhaps debatable)

P5 accepts 1 because he gets 0 in the next round

Go Blue

03-02-2006, 03:28 AM

I think I mistyped something somewhere. I just did this problem over again and I got the same numbers, but for different pirates.

In addition, one assumption that I made was that someone had to be offered one EXTRA piece of gold to be assured that he would vote yes. For example, if #x knew that #y would receive z pieces in the next round, he would necesarilly offer him z+1 pieces this round to assure that #y would if fact accept that offer. If he only offered him z pieces and not z+1, then this would make #y indifferent between accepting and rejecting and thus #x can't be assured of a favorable vote. Unlike in the typical bargaining game, we can't assume that the pieces of gold is like "splitting up a pie" because with the pie, in order to make someone accept because he'll get less next round, he needs to be offered an infinitely small amount greater than what he can get in the next round. What I'm saying is, is that you can't do that here because the pieces of gold can't be cut up into infinitely small pieces. It's either one or nothing. Does that make sense?

Ok so that said, let me redo this. I think I did mess something up before, slightly. This should be right:

n: 5 gets 100

n-1: 5 gets 100, 4 gets 0

n-2: 5 gets 0, 4 gets 1, 3 gets 99

n-3: 5 gets 1, 4 gets 2, 3 gets 0, 2 gets 97

n-4: 5 gets 2, 4 gets 0, 3 gets 1, 2 gets 0, 1 gets 97

There, I think that works. The first time I tried it, I kind of overlooked something but now I'm quite sure that this is the correct answer for good:

#5 (tallest): 2
#4: 0
#3: 1
#2: 0
#1 (shortest): 97

Let me know if that's right (also don't forget the assumption that I made in paragraph 2).

BruceZ

03-02-2006, 07:15 AM

[ QUOTE ]
#5 (tallest): 2
#4: 0
#3: 1
#2: 0
#1 (shortest): 97

[/ QUOTE ]

That's what I got.

In your first post, for game (n-3), your offer 0,99,1,0 could be declined since the pirates with 99 and 1 could do just as well on the next round. The offer 97,0,2,1 would be accepted, and that is much better for the pirate making the offer who now gets 97 instead of 0. Then the shortest pirate 1 just needs to bump the two pirates with the least 0->1, and 1->2, and keep 97 for himself.

BruceZ

03-02-2006, 07:21 AM

[ QUOTE ]
[ QUOTE ]
In game (n-3), Pirate 2 needs 3 votes to end the game or be thrown overboard (so his own vote plus two others). He knows the outcome of game (n-2) so the only thing he can do is offer #3 99 pieces and #4 1 pieces. He himself and #5 get nothing. This is the only way that both #4 and #3 will vote for this proposition.

[/ QUOTE ]

I disagree here.

The offer of 98,0,1,1 is accepted.

Clearly P2 accepts 98.

P3 rejects 0.

P4 accepts 1 because he is indifferent. Either he gets one this round, or next (this is perhaps debatable)

[/ QUOTE ]

It's not debatable; it's wrong. /images/graemlins/laugh.gif P4 may be indifferent, but P2 certainly isn't! He can't afford to have his offer rejected, so he must offer (97,0,2,1). This leads to the final answer (97,0,1,0,2). If we were to assume that indifferent pirates will always accept, then the final answer would be different (98,0,0,1,1).

Now it's true that this latter solution would allow P1 to keep 1 extra piece, so strictly speaking it may answer the question "what is the most that he can keep and remain in the boat", but he has no guarantee that he will remain in the boat with this strategy, and he would be risking his life for 1 measly piece of gold.

Captain Salty

03-02-2006, 08:26 AM

Arrrr! I be thinkin the premises fer this aaaaalll be wrong. No pirate would cheat on booty, it be fair share, cept Capn usually gets a 4-share.

Pirates be honourable men with other pirates, arrrrr!

hencole

03-02-2006, 11:19 AM

This is a clearer version of the question in which a tied vote goes with the most senior pirate or in our case the shortest one. It makes much more sense that way

[ QUOTE ]
Five pirates discover a chest full of 100 gold coins. The pirates are ranked by their years of service, Pirate 5 having five years of service, Pirate 4 four years, and so on down to Pirate 1 with only one year of deck scrubbing under his belt. To divide up the loot, they agree on the following:

The most senior pirate will propose a distribution of the booty. All pirates will then vote, including the most senior pirate, and if at least 50% of the pirates on board accept the proposal, the gold is divided as proposed. If not, the most senior pirate is forced to walk the plank and sink to Davy Jones’ locker. Then the process starts over with the next most senior pirate until a plan is approved.
These pirates are not your ordinary swashbucklers. Besides their democratic leanings, they are also perfectly rational and know exactly how the others will vote in every situation. Emotions play no part in their decisions. Their preference is first to remain alive, and next to get as much gold as possible and finally, if given a choice between otherwise equal outcomes, to have fewer pirates on the boat.

The most senior pirate thinks for a moment and then proposes a plan that maximizes his gold, and which he knows the others will accept. How does he divide up the coins? What plan would the most senior pirate propose on a boat full of 15 pirates?

[/ QUOTE ]

BruceZ

03-02-2006, 01:53 PM

[ QUOTE ]
This is a clearer version of the question in which a tied vote goes with the most senior pirate or in our case the shortest one. It makes much more sense that way

[ QUOTE ]
Five pirates discover a chest full of 100 gold coins. The pirates are ranked by their years of service, Pirate 5 having five years of service, Pirate 4 four years, and so on down to Pirate 1 with only one year of deck scrubbing under his belt. To divide up the loot, they agree on the following:

The most senior pirate will propose a distribution of the booty. All pirates will then vote, including the most senior pirate, and if at least 50% of the pirates on board accept the proposal, the gold is divided as proposed. If not, the most senior pirate is forced to walk the plank and sink to Davy Jones’ locker. Then the process starts over with the next most senior pirate until a plan is approved.
These pirates are not your ordinary swashbucklers. Besides their democratic leanings, they are also perfectly rational and know exactly how the others will vote in every situation. Emotions play no part in their decisions. Their preference is first to remain alive, and next to get as much gold as possible and finally, if given a choice between otherwise equal outcomes, to have fewer pirates on the boat.

The most senior pirate thinks for a moment and then proposes a plan that maximizes his gold, and which he knows the others will accept. How does he divide up the coins? What plan would the most senior pirate propose on a boat full of 15 pirates?

[/ QUOTE ]

[/ QUOTE ]

Thanks for the clarifications. The part in bold is actually what I was arguing for earlier. The fact that ties now go to the distributor means that this version has a different answer. For 5 pirates it is (98,0,1,0,1), where the most senior pirate who goes first is on the left. For 15 pirates, the answer is (93,0,1,0,1,0,1,0,1,0,1,0,1,0,1).

The pattern is that for an odd number of pirates, there will be an equal number of 0's and 1's, in addition to the senior pirate who has the rest. Then for the next number of pirates which is even, the 0's and 1's swap, the former most senior member who becomes the 2nd most senior member goes to 0, and there will be enough 0 -> 1 transitions so that the most senior pirate maintains the same number as the previous most senior member, since a 0 -> 1 transition implies a yes vote. For example, when going from 5 -> 6 pirates, the distribution goes (98,0,1,0,1) -> (98,0,1,0,1,0). Note that both 5 and 6 require 3 yes votes, or 2 besides the most senior. Every odd->even pair will require the same number of yes votes, so the distributor will have the same number. Then on the even -> odd transitions, we require 1 additional yes vote, and this will come from the one extra 0 which transitions to a 1. So again the 0's and 1's swap places, the new 2nd most senior goes to 0, giving an equal number of 0s and 1s, and this time the new most senior member decreases by 1. Here is the pattern starting from the beginning.

Code:<hr /><pre>
100 (n = 1)
100 0
99 0 1
99 0 1 0
98 0 1 0 1 (n = 5)
98 0 1 0 1 0
97 0 1 0 1 0 1
97 0 1 0 1 0 1 0
96 0 1 0 1 0 1 0 1
96 0 1 0 1 0 1 0 1 0 (n = 10)
...
93 0 1 0 1 0 1 0 1 0 1 0 1 0 1 (n = 15) [/quote]
</pre><hr />

soon2bepro

03-02-2006, 06:59 PM

The bigger pirates won't agree on any distribution since if the smallest pirate is thrown offboard then there is one less pirate among which to divide the gold. This repeats until ultimately the bigger pirate gets all. Unless the rest of the pirates are smart enough to realize this and can come up to an alternate solution, but this is all speculation and doesn't provide any particular alternate solution; other than the pirates teaming up to eiter scam the biggest pirate before it's too late, or once there are only 2 pirates left, the smallest one could give all to the other and vote to agree in order to remain onboard.

BruceZ

03-03-2006, 01:38 AM

[ QUOTE ]
The bigger pirates won't agree on any distribution since if the smallest pirate is thrown offboard then there is one less pirate among which to divide the gold. This repeats until ultimately the bigger pirate gets all. Unless the rest of the pirates are smart enough to realize this and can come up to an alternate solution, but this is all speculation and doesn't provide any particular alternate solution; other than the pirates teaming up to eiter scam the biggest pirate before it's too late, or once there are only 2 pirates left, the smallest one could give all to the other and vote to agree in order to remain onboard.

[/ QUOTE ]

There is a single solution which we obtain by working backward. My above post is not the solution despite the title. It assumes you already know the solution method from the rest of the thread, and it extends the answer for 1-15 pirates and describes the pattern.

It turns out that the bigger pirates will accept a very small amount (1 or 2 pieces) because if they decline they will end up with nothing. Contrary to intuition, fewer pirates does not translate into more gold for everyone because the small pirate making the distribution keeps almost all of it.

Here are the solutions to both versions of the problem. Note that the clarified version of the problem assumes that we only need a 50-50 vote for acceptance. It is assumed that this is the only difference between the two versions. All else is as stated by hencole in his clarified statement of the problem.

Solution to the clarified problem (50-50 or better for acceptance):

The last pirate (P5) can't get all the gold because when it comes down to P4 vs. P5, P4 will simply vote to keep it all. P3 knows this, and so he offers P5 1 piece, P4 nothing, and keeps 99 for himself. P5 accepts because if he doesn't he will get nothing. Now P2 only needs 1 other vote besides himself, so he offers P4 1 piece, P3 and P5 get nothing, and he keeps 99 for himself. P4 accepts because otherwise he gets nothing. Finally, P1 needs 2 votes besides himself, so he offers P3 and P5 both 1, P2 and P4 nothing, and keeps 98 for himself. P3 and P5 accept since otherwise they get nothing, and that's the final solution. P1 = 98, P3 = P5 = 1, and P2 = P4 = 0.

Solution to the OP problem (> 50% majority required for acceptance):

If it comes down to P4 vs. P5, P5 will decline any offer by P4 and keep all the gold for himself. P3 knows this, and so he offers P4 1 piece, P5 nothing, and keeps 99 for himself. P4 accepts because if he doesn't he will get nothing. Now P2 needs 2 other votes besides himself, so he offers P4 2 pieces, P5 1 piece, P3 nothing, and he keeps 97 for himself. P4 and P5 accept because otherwise they get less. Finally, P1 needs 2 votes, so he offers P3 1 piece, P5 2 pieces, P2 and P4 nothing, and keeps 97 for himself. P3 and P5 accept since otherwise they get less, and that's the final solution. P1 = 97, P3 = 1, P5 = 2, and P2 = P4 = 0.

holmansf

03-03-2006, 04:44 PM

[ QUOTE ]

Solution to the OP problem (> 50% majority required for acceptance):

If it comes down to P4 vs. P5, P5 will decline any offer by P4 and keep all the gold for himself. P3 knows this, and so he offers P4 1 piece, P5 nothing, and keeps 99 for himself. P4 accepts because if he doesn't he will get nothing. Now P2 needs 2 other votes besides himself, so he offers P4 2 pieces, P5 1 piece, P3 nothing, and he keeps 97 for himself. P4 and P5 accept because otherwise they get less. Finally, P1 needs 2 votes, so he offers P3 1 piece, P5 2 pieces, P2 and P4 nothing, and keeps 97 for himself. P3 and P5 accept since otherwise they get less, and that's the final solution. P1 = 97, P3 = 1, P5 = 2, and P2 = P4 = 0.

[/ QUOTE ]

I think your answer is correct, but I don't quite agree with the reasoning. At the last game, with only P4 and P5, as you say P5 will decline any offer. Thus at the second to last P4 will approve any offer if he wants to live, and so P3 can keep all 100 for himself. Therefore P2 only needs to give 1 each to P4 and P5. P1 can choose either P4 or P5 to give two gold, and also give one to P3. Thus P1 keeps 97.

GreekHouse

03-03-2006, 07:25 PM

[ QUOTE ]
Solution to the OP problem (> 50% majority required for acceptance):

If it comes down to P4 vs. P5, P5 will decline any offer by P4 and keep all the gold for himself. P3 knows this, and so he offers P4 1 piece, P5 nothing, and keeps 99 for himself. P4 accepts because if he doesn't he will get nothing. Now P2 needs 2 other votes besides himself, so he offers P4 2 pieces, P5 1 piece, P3 nothing, and he keeps 97 for himself. P4 and P5 accept because otherwise they get less. Finally, P1 needs 2 votes, so he offers P3 1 piece, P5 2 pieces, P2 and P4 nothing, and keeps 97 for himself. P3 and P5 accept since otherwise they get less, and that's the final solution. P1 = 97, P3 = 1, P5 = 2, and P2 = P4 = 0.

[/ QUOTE ]

The problem stated that a pirates top priority is to stay alive didn't it? In that case, it seems as though an offer of (100,0,0) should be accepted by P3 and P4 since P4 prefers 0 gold to death.

Then, P2 makes an offer of (98,0,1,1) which will be accepted and P1 makes an offer of (97,0,1,0,2) or (97,0,1,2,0), each which should be accepted, so basically the same result.

BruceZ

03-03-2006, 10:08 PM

You wrote:

[ QUOTE ]
The problem stated that a pirates top priority is to stay alive didn't it? In that case, it seems as though an offer of (100,0,0) should be accepted by P3 and P4 since P4 prefers 0 gold to death.

[/ QUOTE ]

And holmansf wrote similarly:

[ QUOTE ]
At the last game, with only P4 and P5, as you say P5 will decline any offer. Thus at the second to last P4 will approve any offer if he wants to live, and so P3 can keep all 100 for himself.

[/ QUOTE ]

Now I'll be P4 and you be P3. As an element of my strategy, known to all as stated in the problem, I have decided that if I am offered P3=100, P4=0, P5=0 that I will reject the offer under threat of certain death on the next round. Do you still want to make me that offer? Have I satisfied my goal of life and maximizing gold by having this element of my strategy?

Go Blue

03-04-2006, 05:20 AM

Yeah that's what I'm kind of wondering about the problem too. I'm pretty sure that my answer is correct if my assumption is correct. Again, my assumption is that if someone is indiffirent between accepting and rejecting (because he'll get the same amount this round or the next and because the pieces are indivisible [see my second post in this thread]), then he could go either way. He MUST be offered an extra pieces compared to what he can hope to get in the next round in order to assure that he will accept your offer. No one has said anything about this. Is this a valid assumption?

holmansf

03-04-2006, 10:04 PM

[ QUOTE ]

Now I'll be P4 and you be P3. As an element of my strategy, known to all as stated in the problem, I have decided that if I am offered P3=100, P4=0, P5=0 that I will reject the offer under threat of certain death on the next round. Do you still want to make me that offer? Have I satisfied my goal of life and maximizing gold by having this element of my strategy?

[/ QUOTE ]

I may be misunderstanding you, but I think you're asking whether if, before any splitting occurs, pirate 4 publicly states that he's one crazy mofo and that he'll choose death over no gold, will he maximize his chance for life/gold. I don't think so- in that case your solution applies and pirate 4 has no chance of getting any gold (the split will be P1 = 97 P2 = 0 P3 = 1 P4 = 0 P5 = 2). If on the other hand pirate 4 stays quiet, my solution will apply and he'll have some chance of getting two gold- it will be at pirate 1's discretion whether pirate 4 or pirate 5 gets the 2 gold.

wmspringer

03-05-2006, 06:00 AM

Hmm.

Suppose there are two pirates left. If the smaller pirate takes any for himself, the bigger one will throw him overboard. So if it gets down to 2, the biggest pirate gets everything.

Suppose there are 3. The two smallest pirates know they must accept this deal or they get nothing. Pirate B takes 1 piece and pirate C gets 199 pieces. Pirate A (the biggest) gets nothing. B agrees to 1 because he gets nothing otherwise.

Extend to 4 pirates. C won't agree to any deal that doesn't give him all but 1 piece of gold, but D can propose that B gets 2, A gets 1, and he gets the rest...that's the 3 votes he needs. (He could say B gets 1 and he gets the rest, but then A and B have the choice of how to vote since they get the same thing either way)

Extend to 5 pirates. He can't get C and D easily, so he proposes that A gets 2, B gets 3, and he gets the rest. (He could say B gets 1 and he gets the rest, but then A and B have the choice of how to vote since they get the same thing either way)

So depending on how you resolve that one bit (is giving A and B the same thing enough) he gets to keep 95 or 99 coins.

Leaky Eye

03-05-2006, 06:54 AM

[ QUOTE ]
Their preference is first to remain alive, and next to get as much gold as possible and finally, if given a choice between otherwise equal outcomes, to have fewer pirates on the boat.

[/ QUOTE ]

2p= certain death for shortest.
3p= 100, 0 , 0 middle votes yes to avoid certain death
4p= 98, 0, 1, 1
5p= 97, 0, 1, 2, 0 or 97, 0, 1, 0, 2 both winning plays. Middle voting yes for one gold to avoid the 4p game. Either above him accepting 2g to beat the 4p outcome.

The most the shortest can get is 97g.

GreekHouse

03-05-2006, 10:35 PM

[ QUOTE ]
You wrote:

[ QUOTE ]
The problem stated that a pirates top priority is to stay alive didn't it? In that case, it seems as though an offer of (100,0,0) should be accepted by P3 and P4 since P4 prefers 0 gold to death.

[/ QUOTE ]

And holmansf wrote similarly:

[ QUOTE ]
At the last game, with only P4 and P5, as you say P5 will decline any offer. Thus at the second to last P4 will approve any offer if he wants to live, and so P3 can keep all 100 for himself.

[/ QUOTE ]

Now I'll be P4 and you be P3. As an element of my strategy, known to all as stated in the problem, I have decided that if I am offered P3=100, P4=0, P5=0 that I will reject the offer under threat of certain death on the next round. Do you still want to make me that offer? Have I satisfied my goal of life and maximizing gold by having this element of my strategy?

[/ QUOTE ]

I don't think this matters. You can tell me beforehand that this is your strategy, but once I've pushed all-in with my (100,0,0) offer, you have no choice but to accept it since your primary goal is not to die, and you will die if you don't accept it.

Leaky Eye

03-06-2006, 12:09 AM

BruceZ

03-06-2006, 12:39 AM

From the problem statement:

[ QUOTE ]
All pirates will then vote, including the most senior pirate, and if at least 50% of the pirates on board accept the proposal, the gold is divided as proposed.

[/ QUOTE ]

You wrote:

[ QUOTE ]
3p= 100, 0 , 0 middle votes yes to avoid certain death

[/ QUOTE ]

You are answering hencol's version here, where only 50-50 is required for acceptance. In this case, the middle (P4) doesn't die if he votes no here; he wins all the gold by offering 100,0 on the next round and then accepting his own proposal.

[ QUOTE ]
The most the shortest can get is 97g.

[/ QUOTE ]

98. See my solution to the 50-50 case in my post marked "detailed solution" below. There are no ambiguities with the solution to this version.

Leaky Eye

03-06-2006, 03:01 AM

It is obvious that I was using the quoted rules but requiring a majority.

The question has no answer without the definition for a pirate's preference when he can get the same money on a later round. So I used that part to answer the original question.

BruceZ

03-06-2006, 04:40 AM

[ QUOTE ]
It is obvious that I was using the quoted rules but requiring a majority.

[/ QUOTE ]

Oh, I thought you were solving the same problem as my post to which you responded, which used the rules from which you quoted.

BruceZ

03-06-2006, 04:48 AM

[ QUOTE ]
Extend to 4 pirates. C won't agree to any deal that doesn't give him all but 1 piece of gold, but D can propose that B gets 2, A gets 1, and he gets the rest...that's the 3 votes he needs.

[/ QUOTE ]

You have A = 1, B = 2, C = 0, D = 97.

[ QUOTE ]
Extend to 5 pirates. He can't get C and D easily, so he proposes that A gets 2, B gets 3, and he gets the rest.

[/ QUOTE ]

A = 2, B = 0, C = 1, D = 0, E = 97 is better and gets accepted for sure.

Leaky Eye

03-06-2006, 05:47 AM

Maybe obvious is too strong. These threads can be unclear when they start getting different games in them.

SNOWBALL

03-06-2006, 08:16 AM

I would be surprised if the answer is larger than zero. I'm pretty sure the way it would play out is everyone gets thrown overboard except the largest pirate who keeps all the gold.

Leaky Eye

03-06-2006, 04:13 PM

If you make the game so that a pirate will only throw another off the boat if it nets him gold, but will otherwise preserve his crewmates, then the answer becomes 100 for the smallest pirate for all games where pirates > 2. Which is kind of gross.

TomCollins

03-06-2006, 04:23 PM

[ QUOTE ]
I would be surprised if the answer is larger than zero. I'm pretty sure the way it would play out is everyone gets thrown overboard except the largest pirate who keeps all the gold.

[/ QUOTE ]

Be surprised, you are wrong.

A_PLUS

03-09-2006, 04:57 PM

Before I read through, let me give it a shot.

I have heard a similar problem with Christians and Lions used.

Start at the end, and build outward. (1=biggest, 5=smallest)
-Biggest pirate will have 100 if he is alone
-2 pirates: smaller pirate must give all of the gold to pirate 1, or be thrown overboard.
-3 pirates: if he offers, pirate 2 1 piece of gold, he is better off, and they have majority.
-4 pirates: P1 gets 1 (better than letting it get to 3 left), P2 gets 2, P3 gets 0, P4 gets 97
-5 pirates: P1 gets 2, P2 gets 3, P3 gets 0, P4 gets 0, last pirate keeps 95.

At least thats what I get. I am assuming this has to be attacked sequentially, but I may be wrong.

A_PLUS

03-09-2006, 05:01 PM

Looks like I was on the right track. I think I am right if you assume the pirates prefer more room on the boat when the amount of gold is constant.

Leaky Eye

03-09-2006, 08:22 PM

[ QUOTE ]
I think I am right if you assume the pirates prefer more room on the boat when the amount of gold is constant.

[/ QUOTE ]

Your answer contains a cascading mistake beginning at the two player game, given that assumption.

purnell

03-09-2006, 09:51 PM

[ QUOTE ]
[ QUOTE ]
Would a pirate prefer 0 gold to getting thrown overboard?

[/ QUOTE ]

No

[ QUOTE ]
Each pirate will only accept that outcome that guarantees him the most gold he will get under any scenario. No other consideration can trump that.

[/ QUOTE ]

[/ QUOTE ]

Yarr, Correct ye be, says I.

Dazarath

03-10-2006, 07:08 AM

If the game gets down to 2 pirates, and 4 offers (0, 100), giving 5 all the gold, does 5 reject the offer? If not, I'm assuming that it's due to a preference for keeping crewmates over tossing them for the same amount of gold. If so, then I guess 3 offering (100, 0, 0) would work, since 4 would rather get 0 gold and keep pirate 3 than get 0 gold and toss him? We need to determine what the pirates pick in a neutral EV situation.

EDIT: Oops, I didn't realize that Leaky Eye had already pointed this out.

I think the problem is only interesting if we say the pirates will only keep their crewmates if it nets them more than tossing them. Man, what kind of pirates are these guys?