Author |
Topic: Greedy Egalitarian Pirates (Read 2841 times) |
|
hawkxor
Newbie
Gender: 
Posts: 5
|
 |
Greedy Egalitarian Pirates
« on: Dec 7th, 2008, 4:08pm » |
 Quote  Modify
|
There are five pirates who stand to divy up 1000 gold pieces amongst themselves. At each stage:
1. A pirate is randomly selected (without replacement).
2. The pirate makes a proposal for how the gold will be distributed.
3. The pirates vote on the proposal, where a strict majority of the votes is required.
4. If the proposal is accepted, it becomes the "current" proposal. Otherwise, the pirate is thrown overboard.
Once all 5 pirates have submitted proposals, the gold is distributed according the the current proposal.
Given that the pirates, are all infinitely intelligent and rational, what happens?
Caveats:
Assume that the order of pirate priorities is: 1) Survival, 2) Greed, 3) Bloodthirst.
If the proposal which ultimately succeeds attributes gold to any dead pirate, than the proposer is the beneficiary of those extra gold pieces.
Finally, if a pirate is forced to make a decision in which he is individually indifferent, he chooses at random according to the uniform distribution.
|
| « Last Edit: Dec 7th, 2008, 9:46pm by hawkxor » |
 IP Logged |
|
|
|
hawkxor
Newbie
Gender:
Posts: 5
|
|
Re: Greedy Egalitarian Pirates
« Reply #1 on: Dec 7th, 2008, 9:46pm » |
Quote Modify
|
Having done some work on this problem myself, I have restated the second caveat. Furthermore, I believe the 3-pirate case is already very interesting.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Greedy Egalitarian Pirates
« Reply #2 on: Dec 7th, 2008, 9:52pm » |
Quote Modify
|
There is a long thread here.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Noke Lieu
Uberpuzzler
pen... paper... let's go! (and bit of plastic)
Gender:
Posts: 1884
|
|
Re: Greedy Egalitarian Pirates
« Reply #3 on: Dec 7th, 2008, 9:56pm » |
Quote Modify
|
having a quick shufti at it, I'd have to conclude that you also need them to perfect logicians and capable of forethought.
(just went to go and get teh link, and T&B beat me to it)
Can't remember if the other thread includes an idea that came to me- pirate offers to include some more treasure to the pile if he can sit back down.
|
|
IP Logged |
a shade of wit and the art of farce.
|
|
|
hawkxor
Newbie
Gender:
Posts: 5
|
|
Re: Greedy Egalitarian Pirates
« Reply #4 on: Dec 8th, 2008, 12:52am » |
Quote Modify
|
I don't believe this is the same puzzle, or that it is mentioned in that thread, since it is a puzzle of my own invention. This is "Egalitarian" pirates, in which there is no strict order of hierarchy; instead, the order is randomly selected round by round. This variant is trivial without the persistent proposal element (first player proposes [498,0,0,251,251] since expected value to other four players in case of first player's death is 250 by symmetry), but I believe it becomes quite interesting with said element. Try 3 players, assume the caveat that dead players gold is redistributed to the proposer of the successful plan, as written.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Greedy Egalitarian Pirates
« Reply #5 on: Dec 8th, 2008, 1:25am » |
Quote Modify
|
If there is one pirate the proposal will be accepted.
If there are two pirates the proposal will be rejected; this means no pirate will wants to kill the third, because then they may be the one amongst the two left that needs to make a proposal.
So if there are three pirates, the proposal gets accepted unanimously.
This in turn means if there are 4, the proposal will be rejected.
And therefore with 5 it will be accepted.
Spotting a good pattern and running with it: if N is odd, the proposal will be accepted, if it is even it will be rejected.
Now, this puts infinite value on one's life, that's what causes this alternation, but what if a pirate values his life at 100 gold? The then risking making a proposal may occasionally be worth it.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
teekyman
Full Member
Gender:
Posts: 199
|
|
Re: Greedy Egalitarian Pirates
« Reply #6 on: Dec 8th, 2008, 1:33am » |
Quote Modify
|
An also important thing to consider with this set up is probability. Will players take a very small incremental probability of death if it came with a larger expected sum of gold? I'm guessing no, but i just want to make sure
|
|
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Greedy Egalitarian Pirates
« Reply #7 on: Dec 8th, 2008, 2:27am » |
Quote Modify
|
Towr: Why is the proposal rejected when there are 4 pirates? Let us take as given that with 3 pirates the pirates certainly all survive. Then the remaining 3 pirates have expectation a priori of 333 1/3 gold pieces were they to kill the first. Hence with 4 pirates, the first to propose must merely choose a proposal such as [662,334,334,0,0]. EDIT: Actually I am not sure of this because the other pirates will probably all reject just because they know that these numbers from stage 1 are irrelevant anyway.
Despite that towr may be right on that, on the other hand, remember that the game does not end after the first accept. The 3 pirate case ends up being difficult enough to work through. What happens if redistributed gold goes to the successful proposer? What if it is thrown overboard? What if pirates propose for all eventualities?
Any positive probability of death is as bad as certain death.
I deleted some posts because my own attempted solution for 3 pirates is failed.
|
| « Last Edit: Dec 8th, 2008, 2:45am by River Phoenix » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Greedy Egalitarian Pirates
« Reply #8 on: Dec 8th, 2008, 2:47am » |
Quote Modify
|
on Dec 8th, 2008, 2:27am, River Phoenix wrote:| Towr: Why is the proposal rejected when there are 4 pirates? Let us take as given that with 3 pirates the pirates certainly all survive. Then the remaining 3 pirates have expectation a priori of 333 1/3 gold pieces were they to kill the first. Hence with 4 pirates, the first to propose must merely choose a proposal such as [662,334,334,0,0]. |
|
There seems to be a bit more than 1000 in total there. But, your point stands, the fourth pirate only need to convince two compatriots to join him. My bad.
And congratulations on getting your old name back 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
teekyman
Full Member
Gender:
Posts: 199
|
|
Re: Greedy Egalitarian Pirates
« Reply #9 on: Dec 8th, 2008, 3:46am » |
Quote Modify
|
As towr said, when there are three pirates, the first pirate's proposal is accepted unanimously. However, the game continues when a proposal passes, so we aren't done with this case yet, since we keep making proposals. We don't have a nice recursion or even a good dynamic programming set up for this variant of the problem, because we have the notion of persistent proposals.
When there are 3 people and the third person is making a proposal (first two survived), then that third person needs to propose something strictly better than the current proposal for one of the other members and give the other one nothing, since #3 needs exactly one of those people to vote in his favor in order to survive, which is always possible.
If #2 dies, then #3 will be face #1 by himself, and will lose. Thus #3 will always vote in favor of #2's proposal in this situation, and it will always pass. so #2 will pass absolutely anything, and #2 should try to make sure that #3's proposal will net #2 with the cash. if #2 proposes 499 to himself and 501 to #1, then #3 will offer #2 500 and give himself 500 to maximize #3's profit. I think this is also the best #2 can ask for himself without having #3 currying #1's favor instead during #3's turn. Since #1's and #2's proposals will always pass, it doesn't matter what #1's proposal is.
Thus the results for 3 people are that one person will get 0, and 2 people will get 500, and all will survive.
|
|
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Greedy Egalitarian Pirates
« Reply #10 on: Dec 8th, 2008, 4:18am » |
Quote Modify
|
@1337b4k4: That is the solution I expected to the 3-pirate case of this problem!
What if instead of the successful proposer taking the excess money, proposers can specify for any eventuality? Can you answer the following subriddles?
a) What happens if Pirate 1 proposes "[334,333,333] and if a pirate dies his money is thrown overboard"?
b) What if Pirate 1 proposes "[0,500,500] if there are 3 pirates left and [0,1000] if there are 2 pirates left"?
Assume the following:
1. No distribution is taken until the very end (so in the first case, the money is not immediately thrown overboard in case of 2's death as player 3's proposal may override that).
2. 0.5(death) + 0.5(a) is better than 0.5(death) + 0.5(b), if a>b
|
| « Last Edit: Dec 8th, 2008, 11:53am by River Phoenix » |
IP Logged |
|
|
|
teekyman
Full Member
Gender:
Posts: 199
|
|
Re: Greedy Egalitarian Pirates
« Reply #11 on: Dec 8th, 2008, 2:31pm » |
Quote Modify
|
I think specifying any eventuality leaves the problem way too open ended, as we could potentially define very contrived cases in the general problem when we have n pirates. It's unclear what exactly would count and would not count as valid eventualities to test for. The problem as it is stated is interesting enough for me.
I have a question: Is it safe to say that pirates seek to maximize their expected amount of money? Or do they work according to some other utility? Would a pirate take 5 coins over a 6% chance at 100 coins? If we're deciding how the problem is defined as we go along, I think expected value would probably be the way to go.
|
|
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Greedy Egalitarian Pirates
« Reply #12 on: Dec 8th, 2008, 4:28pm » |
Quote Modify
|
on Dec 8th, 2008, 2:31pm, 1337b4k4 wrote:| Is it safe to say that pirates seek to maximize their expected amount of money? Or do they work according to some other utility? Would a pirate take 5 coins over a 6% chance at 100 coins? If we're deciding how the problem is defined as we go along, I think expected value would probably be the way to go. |
|
You're probably right about the other variant of the problem. Too hard for n>3.
Pirates maximize their expected value. Also death has a negative and absurdly large but finite value.
|
| « Last Edit: Dec 8th, 2008, 4:28pm by River Phoenix » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Greedy Egalitarian Pirates
« Reply #13 on: Dec 10th, 2008, 5:58am » |
Quote Modify
|
Let expected gain for optimal strategy for i prisoners case for not selected prisoner yet is denoted by pair gi=(mi,di) where mi is expected money gain and di death probability. For a selected prisoner we similarly define gsi and for other prisoners goi.
g1=gs1=(1000,0) 
go2=max(g1,(accepted offer,0))=g1=(1000,0) so gs2=(0,1) and g2=(500,1/2).
go3=avg(max(g2,(accepted offer,0)))=(accepted offer,0)
so gs3=(1000,0) and g3=(1000/3,0).
go4=avg(max(g3,(accepted offer,0))) so if offer>1000/3 he will vote for. Selected prisoner needs 2 other votes so 2 randomly selected other prisoners get offer 334 and one gets 0.
go4=(2*334/3,0)
gs4=(333,0).
g4=(1000/4,0).
go5=avg(max(g4,(accepted offer,0))) so if offer > 1000/4 he will vote for.
Selected prisoner needs 2 other votes so 2 randomly selected other prisoners get offer 251 and remaining two get 0.
go5=(2*251/4,0)
gs5=(498,0)
g5=(1000/5,0).
In general gi=(1000/i,0) for i#2. And the strategy for selected prisoner can be determined easily.
[edit]Actually only for such small i's that the voters can be paid for.[/edit]
Interestig cases are when i>2000 ... when Towr parity scenario works.
on Dec 10th, 2008, 10:48am, River Phoenix wrote:
Proposals are carried through. |
|
Oh yes, I must read more carefully ... ... I'll return to it later.
|
| « Last Edit: Dec 13th, 2008, 8:43am by Hippo » |
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Greedy Egalitarian Pirates
« Reply #14 on: Dec 10th, 2008, 10:48am » |
Quote Modify
|
on Dec 10th, 2008, 5:58am, Hippo wrote:Let expected gain for optimal strategy for i prisoners case for not selected prisoner yet is denoted by pair gi=(mi,di) where mi is expected money gain and di death probability. For a selected prisoner we similarly define gsi and for other prisoners goi.
g1=gs1=(1000,0)
go2=max(g1,(accepted offer,0))=g1=(1000,0) so gs2=(0,1) and g2=(500,1/2).
go3=avg(max(g2,(accepted offer,0)))=(accepted offer,0)
so gs3=(1000,0) and g3=(1000/3,0).
go4=avg(max(g3,(accepted offer,0))) so if offer>1000/3 he will vote for. Selected prisoner needs 2 other votes so 2 randomly selected other prisoners get offer 334 and one gets 0.
go4=(2*334/3,0)
gs4=(333,0).
g4=(1000/4,0).
go5=avg(max(g4,(accepted offer,0))) so if offer > 1000/4 he will vote for.
Selected prisoner needs 2 other votes so 2 randomly selected other prisoners get offer 251 and remaining two get 0.
go5=(2*251/4,0)
gs5=(498,0)
g5=(1000/5,0).
In general gi=(1000/i,0) for i#2. And the strategy for selected prisoner can be determined easily.
Interestig cases are when i>2000 ... when Towr parity scenario works. |
|
This is definitely the right answer when proposals are accepted immediately rather than carried through. Don't believe it is otherwise. However very interesting analysis and answer to the former question!
It's clear that at least your a-priori expected values of (1000/i,0) are correct as long as it can be proven in the latter case, that no pirate ever dies. I actually am not certain this is the case.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Greedy Egalitarian Pirates
« Reply #15 on: Dec 13th, 2008, 3:45pm » |
Quote Modify
|
May be I interpret the task wrong way. But I suppose whenever an offer is rejected, offerer is killed and they start making offers from beginning.
In that case 3 pirates ... the one selected last gets all 1000. And we got (1000/3,0) as in previous post.
Case of 4 pirates is much harder. As the last pirate selected must pay 334,334, he will stand with under g3 so the last nonselected prisoner votes against independently on the offer. On the other hand who is offered most in third proposal would be skipped to maximize last offerer gain. So third offerer must give more than g3 to voters, and most to the one not voting for him ... what requires more than 1000 so third offerer would be killed. Therefore there is nonzero risk to be killed in 4 pirates case so the safest way to avoid it is to vote against any proposal of the first offerer.
And g4=(1000/4,1/4).
And for five pirates the risk to be killed leaves all pirates to vote for so the last offerer gets all 1000 and we got (1000/5,0) as in previous post. So this is towr's odd/even scenario.
What variant remains? Whenever offer is rejected, pirate is killed and the game continues, noone will offer more than once.
When the last offer is accepted/rejected, split is performed according the last offer and the amount given to killed prisoners is either A) processed from beginning B) thrown away.
|
| « Last Edit: Dec 13th, 2008, 3:47pm by Hippo » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Greedy Egalitarian Pirates
« Reply #16 on: Dec 13th, 2008, 4:04pm » |
Quote Modify
|
Actually, I think the problem is quite simple.
The first pirate must make sure that his proposal gets accepted.
At that point, the (N-1) remaining pirates are all on an equal footing. They don't know who will be chosen next. So, if they reject the proposal, their expected return is 1000/(N-1). So the first pirate just needs to offer a bit more than that to half of the other pirates. He should be able to keep about half of the money. (Well, the more pirates there are, the less he gets, due to rounding up. With more than 2000 pirates, he is out of luck).
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Greedy Egalitarian Pirates
« Reply #17 on: Dec 13th, 2008, 5:14pm » |
Quote Modify
|
on Dec 13th, 2008, 4:04pm, Grimbal wrote:Actually, I think the problem is quite simple.
The first pirate must make sure that his proposal gets accepted.
At that point, the (N-1) remaining pirates are all on an equal footing. They don't know who will be chosen next. So, if they reject the proposal, their expected return is 1000/(N-1). So the first pirate just needs to offer a bit more than that to half of the other pirates. He should be able to keep about half of the money. (Well, the more pirates there are, the less he gets, due to rounding up. With more than 2000 pirates, he is out of luck). |
|
Looks good.
|
|
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Greedy Egalitarian Pirates
« Reply #18 on: Dec 13th, 2008, 5:41pm » |
Quote Modify
|
That's the answer to the original problem I heard (randomized order). But I thought this version might be more extensible for the variant in which proposals are carried over - and that's how I phrased this question. So it's not guaranteed that the pirates will accept the proposal that Grimbal states, and even if they do it may not be the proposal that ultimately wins. However, I'm not sure if the problem as I stated it, is tractable (I do not know the answer).
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Greedy Egalitarian Pirates
« Reply #19 on: Dec 20th, 2008, 6:25am » |
Quote Modify
|
I've worked on the B) case ... when the final accepted proposal proposes something to already killed pirates, the corresponding amount is thrown to the see with them.
There definitly is method how to compute it, but the number of cases to consider is too huge to do it by hand.
I scatch just the method:
-------------------------------------
In a stage of the process there is either A) pending proposal where only the amounts proposed to those who made proposal already and the number of remaining pirates are important or B) all proposals made so far were rejected and only the number of remaining pirates is important.
A pirate is choosen and we are to calculate his strategy for the game paramatrised by current proposal.
He at first looks for gains of each pirate for the case his proposal would be rejected (this is smaller game with known proposal). His goal is to made such proposal which modifies the game such the game results of the new game would be advantages for at least half of the other pirates.
If such a proposal exists, he finds all such proposals giving him maximal gain. Their average is expected value of the game.
If no proposal rescuing him exists, the value of the game corresponds to the rejected case (with the pirate killed).
What is difficulty with the by hand computation? There are cases where the same gain can be obtained several ways and you must consider all the cases. You must precompute all the smaller games to be able to correctly continue ...
To find the optimal first proposal requires tons of precomputed cases.
Of course you can make groups of simillar games, but even in that case the number of groups grows fast.
For 4 pirates the computation by hand seems to be feasible.
... You cannot forget the expected value is what you offer so you often create symmetric proposal to satisfy more (2) pirates by sufficient gain with nonzero(nonone) probability.
An example: current proposal 330,330,167,*,*, we are to made a proposal. If the proposal would be rejected,
clearly one of the first two gains 331 (so expected gain is 165,5), third gets 168 and the last one gains 501. There are 7 possibilities to maximal gain 278:
165/166/167,278,278,277,2/1/0;278,165/166/167,278,277,2/1/0;278,278,167, 277,0. Corresponding gains are
166/167/168,0,0,278,556/555/554;0,166/167/168,0,278,556/555/554;0,0,168, 278,554 so expected value is
71+4/7,71+4/7,24,278,554+6/7.
For 330,330,168,*,* the last possibility is eliminated giving expected value 83.5,83.5,0,278,555.
Finaly for the case 334,334,165,*,* gives 5 possibilities to maximal gain 278
167,278,278,277,0;278,167,278,277,0;278,278,165/166/167,277,2/1/0. Corresponding gains are
168,0,0,278,554;0,168,0,278,554;0,0,166/167/168,278,556/555/554 so expected value is
33.6,33.6,100.2,278,554.6.
Similarly 127,126,124,*,* case gives 250 by either
0,>=250,>=250,249,* (C2253=31878 cases) or 250,251,250,249,0.
giving average
(1+249/63758,0,251/63758,250,748+31629/31879)
------------------------------------------
The A) case is simillar ... after last proposal is accepted/rejected, amount corresponding to killed pirates is to be divided by repeated game. The computation method is simillar, but there are special cases not to be overlooked. ... If a pirate offers himself very small amount, it may prevent rejecting his offer as otherwise game repeat gives death risk as there is not enough money to pay for voters. .... Computation requires table of games with all starting amounts at most 1000 (May be again somehow grouped).
-------------------------------------------
There is are C) and D) cases of the game ... as in A), but pirates are not able to hide the obtained amount between restarts so when the pirate's offer is rejected, he returns gain from previous rounds to bank. In C) game this will be used in the restarted game. In the D) case, it can be offered in the current round.
The results of these games are again well defined as the game becomes smaller at each rejected offer.
But in this case current gain of pirates should be part of subgame parameters as well.
Is there a volunteer to bound computational complexity af the A), B), C) and D) cases (with a dynamic programing without grouping). How to maintain grouping and how it helps? For how many pirates is the game solvable by "current" hardware and for how many by "future" hardware?
|
| « Last Edit: Dec 21st, 2008, 11:39am by Hippo » |
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Greedy Egalitarian Pirates
« Reply #20 on: Dec 21st, 2008, 3:32pm » |
Quote Modify
|
Quote:An example: current proposal 330,330,167,*,*, we are to made a proposal. If the proposal would be rejected,
clearly one of the first two gains 331 (so expected gain is 165,5), third gets 168 and the last one gains 501. |
|
Can you explain this? Are you describing the following situation: there are 5 players, current proposal [330,330,167,0,0], the two pirates that have not yet made proposals are currently assigned 0 and we are next to make a proposal? I am not sure that I follow this logic.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Greedy Egalitarian Pirates
« Reply #21 on: Dec 22nd, 2008, 3:15am » |
Quote Modify
|
on Dec 21st, 2008, 3:32pm, River Phoenix wrote:
Can you explain this? Are you describing the following situation: there are 5 players, current proposal [330,330,167,0,0], the two pirates that have not yet made proposals are currently assigned 0 and we are next to make a proposal? I am not sure that I follow this logic. |
|
I am describing situation with current proposal 330,330,167,x,y
where x+y+167+330+330=1000 and the three with 330,330,167 have their proposals already accepted while these 2 with x,y are to make proposals.
The value of x resp. y does not matter as if his proposal would be accepted the current proposal would be invalidated and if it would be rejected he don't obtain it either.
Of course the expected value 71+4/7,71+4/7,24,278,554+6/7 holds after the fourth proposing pirate is selected. Before this selection the expected value is 71+4/7,71+4/7,24,416+3/7,416+3/7. This game value would be considered when the proposal 330,330,167,*,* of the third pirate is to be accepted.
The computation is actually simplified as you can look only on expected gain vectors and there is much smaller number of them than the number of possible proposals (for example the case E,D,C,*.* where E>D>C,D+C=250 gives the same expected gain mentioned in my previous post).
|
| « Last Edit: Dec 22nd, 2008, 3:39am by Hippo » |
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Greedy Egalitarian Pirates
« Reply #22 on: Dec 22nd, 2008, 10:35am » |
Quote Modify
|
It's tricky to judge one train of thought against another in this problem, can you tell me whether or not you agree with the following logic?
If x's proposal were to be rejected, then the pirates expect 331/2, 331/2, 168, *dead*, 501
So x must devise a situation that is better for 2 of the others in addition to himself given that his proposal passes. y's proposal will always pass and is easy to predict, y will just up the offer to exactly 2 of the pirates by 1 coin. So x should additionally ensure that he is the more expensive of the pair that gets this benefit. Hence to maximize his own value he must offer to two other pirates (other than y) a value higher than his own. I believe the following is actually the single optimal case: [277,277,168,276,0]. (modulo an extra 2 coins that can be assigned to anyone but x; given that x is hurtful he will just assign them to 1, 2, or y in which case they are immaterial)
3rd player will accept b/c he expects 169, x will come home with 277.
|
| « Last Edit: Dec 22nd, 2008, 10:39am by River Phoenix » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Greedy Egalitarian Pirates
« Reply #23 on: Dec 30th, 2008, 1:21pm » |
Quote Modify
|
on Dec 22nd, 2008, 10:35am, River Phoenix wrote:It's tricky to judge one train of thought against another in this problem, can you tell me whether or not you agree with the following logic?
If x's proposal were to be rejected, then the pirates expect 331/2, 331/2, 168, *dead*, 501
So x must devise a situation that is better for 2 of the others in addition to himself given that his proposal passes. y's proposal will always pass and is easy to predict, y will just up the offer to exactly 2 of the pirates by 1 coin. So x should additionally ensure that he is the more expensive of the pair that gets this benefit. Hence to maximize his own value he must offer to two other pirates (other than y) a value higher than his own. I believe the following is actually the single optimal case: [277,277,168,276,0]. (modulo an extra 2 coins that can be assigned to anyone but x; given that x is hurtful he will just assign them to 1, 2, or y in which case they are immaterial)
3rd player will accept b/c he expects 169, x will come home with 277. |
|
Oops, I have given wrong example, I wanted to demonstrate 330,330,166,*,* case . The 278 proposed by me cannot be achieved with vote from 3rd pirate (as he gets the same 168 by rejecting). But [165,278,278,277,2] gives 278 to x so it's one of the 6 possible cases ...
It seems to me you understand it well. But one should be very carefull not to miss a case ...
I was out of net for some days ... and actually I've finished the B) case manualy (not checked by program yet).
The lot of game cases for the fourth selected pirate were followed by very small number of cases for third or even 2nd pirate.
The choice of the first pirate is not important at all.
So next post
|
| « Last Edit: Dec 30th, 2008, 1:41pm by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Greedy Egalitarian Pirates
« Reply #24 on: Dec 30th, 2008, 1:32pm » |
Quote Modify
|
B) case ... if the final accepted proposal gives something to a death pirate, it is thrown away.
(The maximal achievable expected gain for proposing pirate is in parenteses.)
1) An arbitrary first proposal is accepted to prevent the risk to start 4 pirates game what is fatal (36+3/11)
2) Next proposal 201,200,*,*,* is accepted either to prevent the risk of starting >=500,*,*,* what is fatal or by A,B,C because it increases expected gain 291+2/3 to 309+5/33 (36+3/11)
3) Next proposal 396,396,195,*,* is accepted by D and E as it increases expected gains 1,0 to 36+3/11,36+3/11 (126)
4) Next proposal is randomly choosen from 55 possibilities, giving 266 to himself, paying more than expected gain -1 of one of E,D,C and at least 267 to the other two of E,D and C. Expected gains was 198+1/2,198+1/2,196. Both the selected one of E,D,C and A vote for. (267)
5) Next proposal is 1+the previous less proposal to the corresponding pirate,0 to those with proposal>266, 267 to B and rest to himself. It is accepted by both pirates with nonzero proposal.
The 3) case gives maximal gain (126) with nonzero expected proposal to both pirates already proposing.
|
| « Last Edit: Dec 30th, 2008, 1:33pm by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print