From: "Robert A. Rosenberg" <hal9001@panix.com>
Date: Sat, 27 Jul 1996 14:48:01 +0800
To: ichudov@algebra.com (Igor Chudov)
Subject: Re: Twenty Bank Robbers -- Game theory:) [Classic Answer]
Message-ID: <v03007803ae1eb746c1b4@[166.84.220.80]>
MIME-Version: 1.0
Content-Type: text/plain


At 9:09 -0500 7/25/96, Igor Chudov 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

This is a variant on the normal distribution problem/game where you have a
number of homogeneous/identical items that are either too numerous to
distribute by the "one for you and one for me" method or are not equivalent
to each other. The "goal" is to have a method of distributing so that each
person feels that they got "their fair share". The classic solution is to
have #1 divide the items into 20 piles (any of which he is willing to take
as his share). Then number #2 is offered the choice of accepting #1's
distribution or rearranging the distribution until he is happy to accept
any of them. This accept/rearrange process goes on until #19 has made his
decision. Then #20 is allowed to select any one pile as his share. The
"choose a pile" option then goes back up the line (to #19, #18, etc) with
each taking one of the remaining piles until it gets to whoever was before
the person who did the last rearrangement. This person then has the option
of doing a new rearrangement or approving the current distribution. After
he does a rearrangement or approves the distribution, the option keeps
going up the line until it gets to #1 (who selects a pile). You then keep
going down [and up] the line until there are only two piles and the last
approver/rearranger gets the last pile after the choice of piles is made by
the other person.

This is "fair" since at all times the person who is making a pile selection
has already approved the distribution (or at the end is offered his choice
of the two remaining piles).