Twenty Bank Robbers -- CLARIFICATION

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

I forgot to say what the GOALS are. The goals of every individual
cypherpunk are (in from highest to lowest priority): 

1. Stay alive
2. Get as much money as possible
3. Keep as many cypherpunks alive as possible, all other things being equal.

	- Igor.

-----BEGIN PGP SIGNED MESSAGE-----

Assuming "perfect" intelligence on the part of the robbers (i.e. they will
follow deterministic behavior and do the "right" thing), then here's what
must happen IMO (1 being the first guy and 20 being the last):

1 must propose that 1, 3, 5, 7, 9, 11, 13, 15, 17, and 19 all split
the money evenly. All of these will vote for it, assuming they're all
perfectly smart and deduce the inevitable outcome.

I arrived at this working backward from the case where two robbers are left.

If 2 are left (19 & 20), 19 gets all the money. So 20 will vote for whatever
18 says, which MUST include 20 in the deal. Since 19 knows this, 19
will vote for whatever 17 says, which must include 19 in the deal, and so
forth. Eventually you arrive at the conclusion that 1,3,5...,19 must
all agree to split the money at the beginning.


On Thu, 25 Jul 1996, Igor Chudov wrote:

> 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?
> > 
> 
> I forgot to say what the GOALS are. The goals of every individual
> cypherpunk are (in from highest to lowest priority): 
> 
> 1. Stay alive
> 2. Get as much money as possible
> 3. Keep as many cypherpunks alive as possible, all other things being equal.
> 
> 	- Igor.
> 

- -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Jeremey Barrett
Senior Software Engineer			jeremey@forequest.com 
The ForeQuest Company       			http://www.forequest.com/

   "less is more."
		-- Mies van de Rohe.

   Ken Thompson has an automobile which he helped design.  Unlike most
   automobiles, it has neither speedometer, nor gas gage, nor any of the
   numerous idiot lights which plague the modern driver.  Rather, if the
   driver makes any mistake, a giant "?" lights up in the center of the
   dashboard.  "The experienced driver", he says, "will usually know
   what's wrong."

		-- 'fortune` output

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBMfgENS/fy+vkqMxNAQEauAP+Ns7g50LTtdRmLg8/ffoveH6x6o/ml6a8
ELGw6/gA0oRq81gVDA/q48uUDOK3+RirV+HcAnB3/QobocxgqftOvcpwk6ewCLOB
bh0f2u8OpcXd/ArrC+Upi4l87Eo1IONDudsluaEVYCBX6cTmyrK3kRskjue/3Xr6
I0UIlz6UxFE=
=lvhl
-----END PGP SIGNATURE-----

At 4:33 PM -0700 7/25/96, Jeremey Barrett wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>Assuming "perfect" intelligence on the part of the robbers (i.e. they will
>follow deterministic behavior and do the "right" thing), then here's what
>must happen IMO (1 being the first guy and 20 being the last):
>
>1 must propose that 1, 3, 5, 7, 9, 11, 13, 15, 17, and 19 all split
>the money evenly. All of these will vote for it, assuming they're all
>perfectly smart and deduce the inevitable outcome.
>
>I arrived at this working backward from the case where two robbers are left.
>
>If 2 are left (19 & 20), 19 gets all the money. So 20 will vote for whatever
>18 says, which MUST include 20 in the deal. Since 19 knows this, 19
>will vote for whatever 17 says, which must include 19 in the deal, and so
>forth. Eventually you arrive at the conclusion that 1,3,5...,19 must
>all agree to split the money at the beginning.

Your solution fails if the proposer is determined by lot, stage by stage.
Any other approach will be felt unfair by some, but that approach will be
thought fair by all.

David

First, the line is established before the proposals begin.  So the
proposer is not determined by lot, everyone knows who will be #1, #2,
etc.  Second, I think the proposer gets to vote.  The wording is a bit
ambiguous, but it just says that "they" vote, and I think "they" pretty
clearly refers to the whole group.

Now here is the solution for two people:

#1 (first in line) proposes that he gets it all.  #1 votes yes, #2 votes
no.  The proposal passes.

Here it is for three people:

#1 (first in line) proposes that he gets it all.  #1 votes yes, #2
probably votes no (since he will get it all if the proposal fails, by
the above) and #3 (end of line) reasons like this: if the proposal
fails, he (#3) will get nothing because #2 will get it all.  Therefore
voting yes or no makes no difference to whether #3 stays alive (his
first priority) or how much money he makes (his second priority).  But
it does make a difference in terms of keeping as many people alive as
possible (his third priority).  So he votes yes because of this third
reason.  Therefore the proposal passes and the first person in line
gets it all in this case.

Of course, #1 could have offered some money to #3 and gotten his vote,
but that would violate the terms of the problem: #1 wants to make as
much money as possible.  And since he can get #3's vote even while
offering nothing to him, that is what he will do.

Hal

-----BEGIN PGP SIGNED MESSAGE-----

 Someone like Hal <hfinney@shell.portal.com> wrote something like: 
>  
> Here it is for three people:
>
> #1 (first in line) proposes that he gets it all.  #1 votes yes, #2
> probably votes no (since he will get it all if the proposal fails, by
> the above) and #3 (end of line) reasons like this: if the proposal
> fails, he (#3) will get nothing because #2 will get it all.  Therefore
> voting yes or no makes no difference to whether #3 stays alive (his
> first priority) or how much money he makes (his second priority).  But
> it does make a difference in terms of keeping as many people alive as
> possible (his third priority).  So he votes yes because of this third
> reason.  Therefore the proposal passes and the first person in line
> gets it all in this case.
>
> Of course, #1 could have offered some money to #3 and gotten his vote,
> but that would violate the terms of the problem: #1 wants to make as
> much money as possible.  And since he can get #3's vote even while
> offering nothing to him, that is what he will do.
   
  
Well this isn't quite true because the cypherpunks are 
apparently allowed to change their votes based upon how their 
votes will effect other cyhpherpunks' votes.  So #3 can vote 
"No" on "#1 gets it all" proposals because he knows that #1 
_knows_ he will vote "No" on "#1 gets it all" proposals and thus
#1 will instead give #3 some money.
 
 
So if you are going to play it that way then you have to be sure
that none of your cypherpunks are allowed to think about the 
possibility that their own (probable) voting will affect their
companions' voting.


Regards,

Bryce




-----BEGIN PGP SIGNATURE-----
Version: 2.6.2i
Comment: Auto-signed under Unix with 'BAP' Easy-PGP v1.1b2

iQB1AwUBMfjiRkjbHy8sKZitAQHq7wL/QKAA1Zz7s7PvBWs5SNEqD8X1bivgFg2l
eFuUgcsM1ZJeZ9XHc6cWVwDWfn7Z8Xu15sflbTBvkIyN7IVKBq5ff2nchHdqj4XQ
y58h0lU0ZYyqlRceeTymrEB2Lebw6WJM
=qJ1E
-----END PGP SIGNATURE-----

Hal <hfinney@shell.portal.com> wrote:

   Of course, #1 could have offered some money to #3 and gotten his vote,
   but that would violate the terms of the problem: #1 wants to make as
   much money as possible.  And since he can get #3's vote even while
   offering nothing to him, that is what he will do.

It was a much more interesting question before the addition of this
"clarification," IMO.

-- 
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
----------------------------------------------------------------------
Kin, n.:
	An affliction of the blood

-----BEGIN PGP SIGNED MESSAGE-----

Does the proposer have a vote? I assumed he did.

On Thu, 25 Jul 1996, Igor Chudov wrote:

> 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?
> > 
> 
> I forgot to say what the GOALS are. The goals of every individual
> cypherpunk are (in from highest to lowest priority): 
> 
> 1. Stay alive
> 2. Get as much money as possible
> 3. Keep as many cypherpunks alive as possible, all other things being equal.
> 
> 	- Igor.
> 

- -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Jeremey Barrett
Senior Software Engineer			jeremey@forequest.com 
The ForeQuest Company       			http://www.forequest.com/

   "less is more."
		-- Mies van de Rohe.

   Ken Thompson has an automobile which he helped design.  Unlike most
   automobiles, it has neither speedometer, nor gas gage, nor any of the
   numerous idiot lights which plague the modern driver.  Rather, if the
   driver makes any mistake, a giant "?" lights up in the center of the
   dashboard.  "The experienced driver", he says, "will usually know
   what's wrong."

		-- 'fortune` output

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBMfjwES/fy+vkqMxNAQFKqAP/WAsGcyj68bzCWPBPv2olelyb/cdr9fZF
yaDxGwHSMz/wCNFD9OOpjrNhhANFPBoFpI7fyhXLMsiazmQD/8t5wdywS7ILyWJl
jw+BnFHuU5aT8y+1KfADLtLrX3R2EHpEh5Rn3T7ZK7bBHdolML52JJfHFZEyaU1f
2yTVG+KbLWw=
=sjJf
-----END PGP SIGNATURE-----

At 6:59 AM -0700 7/26/96, Hal wrote:
>First, the line is established before the proposals begin.  So the
>proposer is not determined by lot, everyone knows who will be #1, #2,
>etc.  Second, I think the proposer gets to vote.  The wording is a bit
>ambiguous, but it just says that "they" vote, and I think "they" pretty
>clearly refers to the whole group.
>
>Now here is the solution for two people:
>
>#1 (first in line) proposes that he gets it all.  #1 votes yes, #2 votes
>no.  The proposal passes.
>
>Here it is for three people:
>
>#1 (first in line) proposes that he gets it all.  #1 votes yes, #2
>probably votes no (since he will get it all if the proposal fails, by
>the above) and #3 (end of line) reasons like this: if the proposal
>fails, he (#3) will get nothing because #2 will get it all.  Therefore
>voting yes or no makes no difference to whether #3 stays alive (his
>first priority) or how much money he makes (his second priority).  But
>it does make a difference in terms of keeping as many people alive as
>possible (his third priority).  So he votes yes because of this third
>reason.  Therefore the proposal passes and the first person in line
>gets it all in this case.
>
>Of course, #1 could have offered some money to #3 and gotten his vote,
>but that would violate the terms of the problem: #1 wants to make as
>much money as possible.  And since he can get #3's vote even while
>offering nothing to him, that is what he will do.

But Hal, these are Cypherpunks, which means some of them are smart and some
are uh, er, um, not so smart. I would not want to be first in line.

David

-----BEGIN PGP SIGNED MESSAGE-----

Allright, considering the 3rd goal, I think the first guy gets all the 
money and everyone lives.

Here's why:

in the case of 2, 19 takes it all and 20 gets nothing. So with 3,
since 20 will get nothing with 2 left, he may as well vote for 18 to get 
it all, since that increases the number who survive.

So with 4, 17 proposes that 17 get all the money, and since 19 and 20
are already resigned to getting nothing, they will go along with 17.

Following this to the end, the first guy gets all the money and everyone  
lives.

On Thu, 25 Jul 1996, Igor Chudov wrote:

> 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?
> > 
> 
> I forgot to say what the GOALS are. The goals of every individual
> cypherpunk are (in from highest to lowest priority): 
> 
> 1. Stay alive
> 2. Get as much money as possible
> 3. Keep as many cypherpunks alive as possible, all other things being equal.
> 
> 	- Igor.
> 

- -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Jeremey Barrett
Senior Software Engineer			jeremey@forequest.com 
The ForeQuest Company       			http://www.forequest.com/

   "less is more."
		-- Mies van de Rohe.

   Ken Thompson has an automobile which he helped design.  Unlike most
   automobiles, it has neither speedometer, nor gas gage, nor any of the
   numerous idiot lights which plague the modern driver.  Rather, if the
   driver makes any mistake, a giant "?" lights up in the center of the
   dashboard.  "The experienced driver", he says, "will usually know
   what's wrong."

		-- 'fortune` output

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBMfkOiC/fy+vkqMxNAQEo3wP/V+DuUGKc9YUBC/QzFtx/hX+arZwJqAU5
rXdvHF7DGnRbjiqRqFvZGy8DpoDhGD/UZkO71Ilf25iSW7Nkq/FUaYuyR3An/axi
YqUxw+Mq3b42FyNWXZRENqG1aGZDRMxy41mEIBzp8gljIqRBCQh+EUrvrFzs+xP0
UX+RQJ5N+Zs=
=u5PJ
-----END PGP SIGNATURE-----