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