Re: Twenty Bank Robbers -- Game theory:)
At 09:09 AM 7/25/96 -0500, you wrote:
Here's a puzzle for our game theorists.
Twenty cypherpunks robbed a bank. They took 20 million bucks. Here's how they plan to split the money: they stay in line, and the first guy suggests how to split the money. Then they vote on his suggestion. If 50% or more vote for his proposal, his suggestion is adopted.
Otherwise they kill the first robber and now it is the turn of guy #2 to make another splitting proposal. Same voting rules apply.
The question is, what will be the outcome? How will they split the money, how many robbers will be dead, and so on?
igor
Here's my guess: Eache robber is going to want the largest share of the money possible. Therefore The first guy dies automatically because that increases the share size. This continues on until there are only two robbers left. Robber #19 suggests that he receives the full 20 million and since his vote is 50%, he receives it all. 18 robbers dead. vagab0nd@sd.cybernex.net http://ww2.sd.cybernex.net/~vagab0nd/index.html Visit web page for public key.
"Peter D. Junger" <junger@pdj2-ra.F-REMOTE.CWRU.Edu> notes
a proposal by the first guy to split the proceeds equally among the first ten should be satisfactory to the first ten.
To extend this reasoning, the first person in line announces that the first nine (in any order) to join his "coalition" will split the $2 million. At that point, it's a win-win (or at least win-break-even) for the entire group. Martin Minow minow@apple.com
At 3:55 PM -0700 7/25/96, Erle Greer wrote:
At 09:09 AM 7/25/96 -0500, you wrote:
Here's a puzzle for our game theorists.
Twenty cypherpunks robbed a bank. They took 20 million bucks. Here's how they plan to split the money: they stay in line, and the first guy suggests how to split the money. Then they vote on his suggestion. If 50% or more vote for his proposal, his suggestion is adopted.
Otherwise they kill the first robber and now it is the turn of guy #2 to make another splitting proposal. Same voting rules apply.
The question is, what will be the outcome? How will they split the money, how many robbers will be dead, and so on?
igor
Here's my guess: Eache robber is going to want the largest share of the money possible. Therefore The first guy dies automatically because that increases the share size. This continues on until there are only two robbers left. Robber #19 suggests that he receives the full 20 million and since his vote is 50%, he receives it all. 18 robbers dead.
No. Robber 18 knows that he will be killed under those circumstances, so he proposes that Robber 20 gets all the money. 20 votes with him. Now iterate backwards. If, under my assumption the proposers are selected by lot at each stage, then 18 still knows he'd be killed, but not knowing which of 19 or 20 is the next proposer, suggests 19 and 20 split 50-50. Since each knows that he might be #20 and get nothing on the next round, they accept. Now iterate that one backwards. David
David Sternlight wrote:
Twenty cypherpunks robbed a bank. They took 20 million bucks. Here's how they plan to split the money: they stay in line, and the first guy suggests how to split the money. Then they vote on his suggestion.
^^^^ ^^^
No. Robber 18 knows that he will be killed under those circumstances, so he proposes that Robber 20 gets all the money. 20 votes with him.
I think many are assuming that the cypherpunk making the suggestion gets a vote. My reading of the puzzle is that he does not. Gary -- pub 1024/C001D00D 1996/01/22 Gary Howland <gary@systemics.com> Key fingerprint = 0C FB 60 61 4D 3B 24 7D 1C 89 1D BE 1F EE 09 06
Gary Howland <gary@systemics.com> wrote:
No. Robber 18 knows that he will be killed under those circumstances, so he proposes that Robber 20 gets all the money. 20 votes with him.
I think many are assuming that the cypherpunk making the suggestion gets a vote. My reading of the puzzle is that he does not. I hadn't thought of that. If the proposer gets no vote, and assuming he still gets counted to make up 50%, for N > 3, he should suggest giving some money to the penultimate ceil(N/2) robbers. In the case of N <= 3, the last robber gets everything. -- Paul Foley <mycroft@actrix.gen.nz> --- PGPmail preferred PGP key ID 0x1CA3386D available from keyservers fingerprint = 4A 76 83 D8 99 BC ED 33 C5 02 81 C9 BF 7A 91 E8 ---------------------------------------------------------------------- Fine day to work off excess energy. Steal something heavy.
Gary Howland wrote:
David Sternlight wrote:
Twenty cypherpunks robbed a bank. They took 20 million bucks. Here's how they plan to split the money: they stay in line, and the first guy suggests how to split the money. Then they vote on his suggestion.
^^^^ ^^^
No. Robber 18 knows that he will be killed under those circumstances, so he proposes that Robber 20 gets all the money. 20 votes with him.
I think many are assuming that the cypherpunk making the suggestion gets a vote. My reading of the puzzle is that he does not.
Everyone who is still alive, including the one making a suggestion, can vote. - Igor.
David Sternlight <david@sternlight.com> wrote: No. Robber 18 knows that he will be killed under those circumstances, so he proposes that Robber 20 gets all the money. 20 votes with him. Now iterate backwards. If, under my assumption the If there are 3 robbers, #1 can work out any split he likes that gives a portion of the money to #3, since #3 knows he won't see a cent unless he goes along with it. If he chooses not to give anything to #3, #3 loses nothing but may decide to kill him out of spite. In the case of 4 robbers, #1 could decide to split the money with #3 or #4. #3 will vote with him if he chooses #3 because he won't get anything otherwise. #4 will vote with him if he chooses #4, because #4 knows that he has no choice but to agree with anything #2 decides, and on the assumption that the proposer at each round wishes to maximize his share, he'll offer #4 less than #1 did. (In this case, #3 has nothing to lose, so he may vote with 1 and 4, but it doesn't matter) Iterating backwards from here to the case of N robbers, #1 only has to offer any floor((N-1)/2) of robbers #3..#N any amount in order to get their votes. proposers are selected by lot at each stage, then 18 still knows he'd be killed, but not knowing which of 19 or 20 is the next proposer, suggests 19 and 20 split 50-50. Since each knows that he might be #20 and get nothing on the next round, they accept. Now iterate that one backwards. In this case, 18 will be killed anyway if the other two are willing to bet their half of the money on being next in line. It's possible that for N robbers, all of them will vote against the proposer at every stage until one of them ends up with all the money. -- Paul Foley <mycroft@actrix.gen.nz> --- PGPmail preferred PGP key ID 0x1CA3386D available from keyservers fingerprint = 4A 76 83 D8 99 BC ED 33 C5 02 81 C9 BF 7A 91 E8 ---------------------------------------------------------------------- #define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255) #define BX_(x) ((x) - (((x)>>1)&0x77777777) \ - (((x)>>2)&0x33333333) \ - (((x)>>3)&0x11111111))
Gary Howland <gary@systemics.com> writes:
I think many are assuming that the cypherpunk making the suggestion gets a vote. My reading of the puzzle is that he does not.
As we have seen apparently the intention was that he does get a vote. However I don't think the answer changes even with Gary's interpretation. With two people, #1 (the front of the line) must propose that all money go to #2, otherwise #2 (who is the only one with a vote in Gary's version) will vote against it (and get all the money when #1 dies). With this proposal #2 will vote in favor since he gets the same amount of money either way, and it keeps more people alive (see the post which describes the goals of the robbers). This is different than the original problem, but it is the only case which differs. With three people, #1 (in front) proposes to keep it all. #2 will vote in favor since if the proposal doesn't pass, #2 will end up with nothing anyway (per above). So #2's third goal comes into play, maximizing the number of players alive, and he will vote in favor. #3 may vote against but #2's vote will be 50% (#2 and #3 get to vote in Gary's version) and will carry. So #1 keeps it all, the same answer as in the original version. Extensions to n players are again left as an exercise, but I think the answers come out the same in Gary's version. Hal
Erle Greer writes: : At 09:09 AM 7/25/96 -0500, you wrote: : >Here's a puzzle for our game theorists. : > : >Twenty cypherpunks robbed a bank. They took 20 million bucks. Here's : >how they plan to split the money: they stay in line, and the first guy : >suggests how to split the money. Then they vote on his suggestion. If : >50% or more vote for his proposal, his suggestion is adopted. : > : >Otherwise they kill the first robber and now it is the turn of guy #2 : >to make another splitting proposal. Same voting rules apply. : > : >The question is, what will be the outcome? How will they split the : >money, how many robbers will be dead, and so on? : > : >igor : > : : Here's my guess: : Eache robber is going to want the largest share of the money possible. : Therefore The first guy dies automatically because that increases the share : size. This continues on until there are only two robbers left. Robber #19 : suggests that he receives the full 20 million and since his vote is 50%, he : receives it all. 18 robbers dead. That ``solution'' assumes that cypherpunks are rather stupid. Since everyone can do that calculation it is quite clear that at least 18 would refuse to vote (or fail to vote) in a way that produces such a result. On the other hand, a proposal by the first guy to split the proceeds equally among the first ten should be satisfactory to the first ten. On that basis nobody dies and ten receive two million each, if we assume that each is a simple profit maximizer. I think that that result is stable, but am not going to try to prove that it is. (If the result is not stable, it should be relatively easy to establish that fact.) -- Peter D. Junger--Case Western Reserve University Law School--Cleveland, OH Internet: junger@pdj2-ra.f-remote.cwru.edu junger@samsara.law.cwru.edu
participants (8)
-
David Sternlight -
Erle Greer -
Gary Howland -
Hal -
ichudov＠algebra.com -
Martin Minow -
Paul Foley -
Peter D. Junger