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.

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

"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