From: Paul Foley <mycroft@actrix.gen.nz>
Date: Fri, 26 Jul 1996 21:56:02 +0800
To: david@sternlight.com
Subject: Re: Twenty Bank Robbers -- Game theory:)
In-Reply-To: <v03007805ae1e24c262c7@[192.187.162.15]>
Message-ID: <199607261026.WAA12047@mycroft.actrix.gen.nz>
MIME-Version: 1.0
Content-Type: text/plain


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))