From: jim bell <jimbell@pacifier.com>
Date: Sat, 27 Jul 1996 07:46:59 +0800
To: "Clay Olbon II" <cypherpunks@toad.com>
Subject: Re: Twenty Bank Robbers -- Game theory:)
Message-ID: <199607261757.KAA18208@mail.pacifier.com>
MIME-Version: 1.0
Content-Type: text/plain


At 10:04 AM 7/26/96 -0400, Clay Olbon II wrote:
>jim bell <jimbell@pacifier.com> wrote:
>>My previous answer was incomplete, of course.  I continue to believe that 
>>the problem is unsolveable as stated, if for no other reason than the 
>>"weight" of the negative represented by dying is not stated.  It's a VERY 
>>complex problem, unless there's some trick I'm not seeing.
>
>Jim is right.  The problem with any optimization problem is when
>unquantifiable negatives are included.  The "classic" example of this is an
>inventory problem.  The optimal solution is minimal (or no) inventory,
>however there are unquantifiable negatives that arise when a customer
>cannot get his product when he wants it.  I don't think the problem is that
>complex if the negative is that you get no money rather than "you die".  As
>an aside, many game theory problems (possible including the simplified
>version of this one) are solvable using linear programming (and no, that is
>not writing C one line at a time ;-).  It has been far too long since my
>last game theory course to consider trying to set this problem up however
>(I've found that I don't use either game theory or LP a whole lot in the
>"real world" of engineering).  

Here is my best (currently!) guess at an APPROXIMATION of the solution.   In 
order to avoid the indeterminacy of the weight of a death versus money, I 
assume that a solution can be found on the first proposal.  (presumably, the 
first chooser is _motivated_ to find one, right?!?)  This means that the 1st 
chooser must select a distribution that will make at least 50% happy.

The first wild guess is that he's offer equal shares of the money to himself 
(#1) and the next nine (#2-#10).  But the problem with that is that the 
higher-numbered people might feel inclined to defect, possibly figuring that 
by getting rid of the people before them, they could increase the size of 
their likely reward.  Probably the solution is to offer those higher enough 
money so that they have no reason to defect.

The amount that should be offered to each could be related to the maximum 
amount that person might reasonably be able to expect, if all of the people 
ahead of him in line had been eliminated.  #1 and #2 can, at best, expect 
1/10th of the reward each, #3 and #4 can expect 1/9th, #5 and #6 can expect 
1/8th, #7 and #8 can expect 1/7, and finally #9 and #10 can expect 1/6.

Of course, all this adds up to more than 1 (actually, 1627/1260), so the 
result must be normalized to bring the total amount offered down to "1".  

BTW, as extra "inducement" the people at the beginning of the line (2, 3, 4, 
etc) can agree and publicly announce that if anyone between 2 and 10 defects 
from this arrangement, he will be passed over in subsequent iterations of 
this process, selecting people starting from #11 and above in their place.  
Thus, the people between #1 and #10 are strongly motivated to go along with 
this arrangement from the beginning, particularly those near #10.


Of course, this raises yet another possibility.  Suppose #1 made an proposal 
like this:

"The money is to be split equally among everybody who votes for this 
proposal."    The high numbers (11-20) are motivated to vote for this, for 
fear that in the absense of such an agreement the low numbers would agree to 
split the pot without them.  Likewise, the low numbers would be inclined to 
get an agreement rather than risk having their proposals rejected and them 
killed.    Anyone who defects risks losing out on everything.


(However, in order for proposals like this to be properly evaluated, it is 
necessary to establish certain issues, such as whether there's a secret 
ballot or not, etc.  Also, even if the results of the ballot are not secret, 
are the votes revealed all at one time, or are the participants polled 
individually, and in what order.  Can a participant adjust his vote 
according to the votes of another?)

Jim Bell
jimbell@pacifier.com