From Jeff.Parker@East.Sun.COM (Jeff Parker) Mon Jan 30 10:00:57 1995 Date: Mon, 25 Jan 93 11:31:40 EST From: Jeff.Parker@East.Sun.COM (Jeff Parker) To: dbh@doc.ic.ac.uk Subject: Re: "Cut & Choose" for several players Content-Length: 2114 I think Rev. Charles Dodgeson (Lewis Carrol) addressed this years ago. As I recall, his solution allowed players j (j > 1) to pick the portion designed by player 1 in turn, if they took a hunk off it. That is 1) Player 1 slices pie in half 2) Player 2 likes it, so he removes a portion of pie, 3) Player 3 likes it, so he decreases it again CLearly the strategy for each player is to approximate 1/n + epsilon to the best of their ability. When they don't get a slice they were working on, it is because epsilon was too large. In article 93Jan25160822@wombat.doc.ic.ac.uk, dbh@doc.ic.ac.uk (Denis Howe) writes: In article <727745474snz@panache.demon.co.uk> raph@panache.demon.co.uk (Raphael Mankin) wrote: >The general rule is that the player who divides does not choose. >This negative feedback prevents bias in the divisions -- assuming >that there are no collusions. A Byznatine generals' solution would >be much more complex. A what? What's a Byznatine (or even Byzantine) generals' solution? >Player 1 divides the pile into a 1-portion and a (n-1)-portion. >Player 2 decides whether he or player 1 gets the 1-portion. Whoever >gets it drops out. The division continues with n-1 players and the >(n-1)-portion. That ensures that each person is satisfied with his own share but the new version of the problem requires that each person be satisfied that nobody else has a better portion. Player 3 may think that the 1-portion was too big but he has no chance to object according to the above algorithm. I believe the problem is insoluble because anyone who is not involved in making a division can always veto it. There is thus no incremental approach which successively excludes people from the decision making. This means that everyone must simultaneously agree to all divisions but that is just a restatement of the problem. -- Denis Howe Who is the potter and who the pot? Jeff Parker jparker@east.sun.com Sun Microsystems (508) 671-0588 "If I haven't seen as far as others, it's because I'm standing on the shoulders of midgets." - Paul Callahan