home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / rec / puzzles / 8531 < prev    next >
Encoding:
Internet Message Format  |  1993-01-25  |  1.9 KB
  1. Xref: sparky rec.puzzles:8531 sci.math:18726 rec.games.misc:19344
  2. Path: sparky!uunet!pipex!doc.ic.ac.uk!news!dbh
  3. From: dbh@doc.ic.ac.uk (Denis Howe)
  4. Newsgroups: rec.puzzles,sci.math,rec.games.misc
  5. Subject: Re: "Cut & Choose" for several players
  6. Date: 25 Jan 93 16:08:22
  7. Organization: Computing Department, Imperial College, London, UK
  8. Lines: 30
  9. Distribution: world
  10. Message-ID: <DBH.93Jan25160822@wombat.doc.ic.ac.uk>
  11. References: <43755@sdcc12.ucsd.edu> <727745474snz@panache.demon.co.uk>
  12. NNTP-Posting-Host: wombat.doc.ic.ac.uk
  13. In-reply-to: raph@panache.demon.co.uk's message of Fri, 22 Jan 1993 23:31:14 +0000
  14.  
  15. In article <727745474snz@panache.demon.co.uk> raph@panache.demon.co.uk
  16. (Raphael Mankin) wrote:
  17.  
  18. >The general rule is that the player who divides does not choose.
  19. >This negative feedback prevents bias in the divisions -- assuming
  20. >that there are no collusions.  A Byznatine generals' solution would
  21. >be much more complex.
  22.  
  23. A what?  What's a Byznatine (or even Byzantine) generals' solution?
  24.  
  25. >Player 1 divides the pile into a 1-portion and a (n-1)-portion.
  26. >Player 2 decides whether he or player 1 gets the 1-portion.  Whoever
  27. >gets it drops out.  The division continues with n-1 players and the
  28. >(n-1)-portion.
  29.  
  30. That ensures that each person is satisfied with his own share but the
  31. new version of the problem requires that each person be satisfied that
  32. nobody else has a better portion.
  33.  
  34. Player 3 may think that the 1-portion was too big but he has no chance
  35. to object according to the above algorithm.
  36.  
  37. I believe the problem is insoluble because anyone who is not involved
  38. in making a division can always veto it.  There is thus no incremental
  39. approach which successively excludes people from the decision making.
  40. This means that everyone must simultaneously agree to all divisions
  41. but that is just a restatement of the problem.
  42. --
  43. Denis Howe <dbh@doc.ic.ac.uk>
  44. Who is the potter and who the pot?
  45.