From: tob@world.std.com (Tom Breton)
Date: Mon, 29 Jul 1996 09:22:50 +0800
To: cypherpunks@toad.com
Subject: Re: Twenty Bank Robbers -- Game theory:)
Message-ID: <199607282239.AA07295@world.std.com>
MIME-Version: 1.0
Content-Type: text/plain


What the 20 Cypherpunk Bankrobbers do, aside from writing "Memo: Need
better loot-division scheme. *URGENT*."


Assume every player acts completely rationally, and unwaveringly trusts
every other player to fully understand the situation and act solely to
maximize their profit in this single situation.

Also assume that each player announces an immutable, unconditional
monetary distribution before anyone has voted, and the announced
distribution constitutes the whole of the payoff (no way to make or
enforce promises, no external loyalties, no side payments, etc.)

Also assume no revolt against the rules is possible.

Every proposer makes the most profitable deal for himself that will pass
the vote, if they can predict it (As it happens, they always can with
one exception, see below)

Every player, when voting, compares what he is offered right now with
what he will be offered between now and the first guaranteed successful
proposal.

He inspects the future possibilities and sees that the next offerer can
make a successful proposal if they (the player) vote down the current
proposal, and if his vote is needed this time, it will not be needed for
the next offer to succeed. (You can check this assumption below).

So he sees no reason to hope for a better result by voting against
apparently favorable offers.

----

If we were to keep the condition that all other things being equal,
players vote for the other players to live, the proposer always keeps
the *entire* amount.

If a player expects to be offered no money next time, it makes no sense
to offer him anything this time, because you've got his vote for sure
anyways (nice guys finish last). Working backwards, once a player will
be shut out in the future, it never makes sense to cut him in.

In fact, for each player it makes sense to some proposer to shut him
out. The guy next in line will never vote for the proposer to live, so
is always shut out. So nobody but the proposer expects any money and
everybody but the guy next in line votes for the proposer to live.

----

So instead I'm going to assume that if a player does not do *better*
than he will next time, he votes against the proposer.

The result is that the first player not only lives, but makes out like a
bandit, to the extent that the loot is subdividable. If there were 40
million and 1 guys in line, he'd be meat. Likewise, if the money was all
in $2,500,000 notes he should start framing his last words.

I'm going to write it in reverse order, where #0 is the last guy, #1 is
second to last, etc. because it's easier to see the progression that
way.


1 Player:
    #0: everything
    Voting for: #0
    Trivially succeeds 1/1

2 players:
    #0: nothing
    #1: Everything
    Voting for: #1
    Succeeds 1/2

3 players:
    #0: $.01
    #1: nothing
    #2: Everything else.
    Voting for: #0 #2
    Succeeds 2/3

4 players:
      #1: $.01
      #0, #2: nothing
      #3: Everything else.
    Voting for: #1 #3
    Succeeds 2/4

5 players:
    #1, #3: nothing
    #0, #2: $.01
    #4: Everything else.
    Voting for: #0 #2 #4
    Succeeds 3/5

6 players:
    #1, #3:     $.01
    #0, #2, #4: nothing
    #5: Everything else
    Voting for: #1 #3 #5
    Succeeds 3/6


The other cases proceed similarly, grouping even/odd. In the end, the
guy at the head of the list offers every other guy a penny and keeps the
rest -- and then starts to sweat as he wonders whether our assumption of
perfect rationality will hold up in real life.

Paul Foley nearly got it, but it does matter who is offered money. If it
didn't, then nobody could count on doing worse on the next proposal.

--------

The case where the proposer does not get a vote is completely different:

1 Player:
    #0: everything
    Voting for:
    Vote is indeterminate 0/0
    Player seals himself into a box with the money, Schroedinger's cat,
    and a vial of poison that has a 50% chance of being shattered.

Everything that follows depends on how we resolve that case. If we
assume some probability mixture of money & death, it is not given how to
weight the player's negative payoff (death) vs positive payoff (money).

Let's assume Schroedinger's player gets all the money and is not
required to suicide.

2 players:
    #0: Everything
    #1: nothing
    Voting for:
    Fails 0/1

Remember the assumption that if a player does not do *better*, he votes
against the proposer. This is a null move since the outcome is the same
as above.

3 players:
    #0: nothing
    #1: $.01            (or nothing)
    #2: Everything else
    Voting for: #1
    Succeeds 1/2

Note that we assumed that #1 requires strictly more money than he would
otherwise be offered (His life means nothing to him). Otherwise he would
be offered $0. (Yeah, I don't want to rewrite the analysis just for
that). It would end up with the same pattern, though, just faster.

4 players:
    #0: $.01
    #1: $.02            (or $.01)
    #2: nothing
    #3: Everything else
    Voting for: #0, #1
    Succeeds 2/3

That fact that the proposer cannot vote means he needs to pick up an
extra vote. He can't get it from the guy who would get almost
everything, and a penny secures the vote of the player who would get
nothing. So he has to offer the player who would get $.01 the next
increment of money. If #1 valued his life, he'd be offered $.01 instead.


5 players:
    #0: $.02
    #1: nothing         (or group #0,#1 interchangeably)
    #2: $.01
    #3: nothing
    #4: Everything else
    Voting for: #0, #2
    Succeeds 2/4

...leaving the next (previous) proposer a similar position.

6 players:
    #0: nothing
    #1: $.01            (or group #0,#1,#2 interchangeably)
    #2: $.02
    #3: $.01
    #4: nothing
    #5: Everything else
    Voting for: #1, #2, #3
    Succeeds 3/5

7 players:
    #0: $.01
    #1: ?
    #2: nothing
    #3: ?
    #4: $.01
    #5: nothing
    #6: Everything else
    Voting for: #0, #4, ?
    Succeeds 3/6

For the first time here, one of the proposers has an arbitrary decision.
He has #0 and #4 and he needs to pick up one more vote. He can't do it
for $.01 and there are two ways to do it for $.02.

We would have encountered this situation earlier if #1 valued his life.

Here we have to add some notation to indicate a non-determinate
distribution over a set:
(set): (non-zero payoffs, all others are 0) average

7 players:
    #0: $.01
    (#1,#3): ($.02) average $.01
    #2: nothing
    #4: $.01
    #5: nothing
    #6: Everything else
    Voting for: #0, #4, (#1 or #3)
    Succeeds 3/6



8 players:
    #0: ?
    (#1,#3): ?
    #2: $.01
    #4: ?
    #5: $.01
    #6: nothing
    #7: Everything else
    Voting for: #2, #5, ?, ?
    Succeeds 4/7


The proposer easily gets #2 and #5 and needs two more votes. #6 can't be
reached. The rest all have an expected payoff of $.01, so he gives $.02
to any two of them. Our indeterminate-list seems to be growing.


8 players:
    (#0, #1,#3, #4): ( 2 x $.02) average $.01
    #2: $.01
    #5: $.01
    #6: nothing
    #7: Everything else
    Voting for: #2, #5, 2 of (#0, #1,#3, #4)
    Succeeds 4/7


9 players:
    (#0, #1, #2, #3, #4, #5): ( 3 x $.02) average $.01
    #6: $.01
    #7: nothing
    #8: Everything else
    Voting for: #6, 3 of (#0, #1, #2, #3, #4, #5)
    Succeeds 4/8

The indeterminate-list has now swallowed up everything but the last 3
players and will continue to do so because the average payoff to the
list is always more than $.01 and less than $.02.

10 players:
    (#0, #1, #2, #3, #4, #5, #6): ( 4 x $.02) average $.08/7
    #7: $.01
    #8: nothing
    #9: Everything else
    Voting for: #7, 4 of (#0, #1, #2, #3, #4, #5, #6)
    Succeeds 5/9


--------


Another set of assumptions is that the players do not trust each other
to be rational or to see all outcomes. In this case, the guy at the head
of the line says in a loud voice to the guy behind him: "Whoever would
vote to kill me even though I offer them money would vote to kill you
too even if you split the money with them, so if it gets to you you
should cut out anyone who got my money but voted to kill me, but keep
those who got my money and voted to keep me alive."

He then allocates equal portions to half the group, including himself
and not including the guy behind him. He probably lives.

--------