home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18689 < prev    next >
Encoding:
Internet Message Format  |  1993-01-24  |  2.1 KB
  1. Path: sparky!uunet!usc!sdd.hp.com!network.ucsd.edu!sdcc12!sdcc10!cs161fir
  2. From: cs161fir@sdcc10.ucsd.edu (Anthony Minkoff)
  3. Newsgroups: sci.math
  4. Subject: Re: "Cut & Choose" for several players
  5. Message-ID: <43908@sdcc12.ucsd.edu>
  6. Date: 23 Jan 93 17:57:42 GMT
  7. References: <1993Jan19.213201.24197@zip.eecs.umich.edu> <43773@sdcc12.ucsd.edu> <1993Jan21.101533.19001@acis.comlab.ox.ac.uk>
  8. Sender: news@sdcc12.ucsd.edu
  9. Organization: University of California, San Diego
  10. Lines: 37
  11. Nntp-Posting-Host: sdcc10.ucsd.edu
  12.  
  13. In article <1993Jan21.101533.19001@acis.comlab.ox.ac.uk>,
  14. akay@comlab.ox.ac.uk (Andrew Kay) writes:
  15. >Anthony Minkoff writes:
  16. >>I.e., the statement "each player feels he got a 'fair' share" is not
  17. >>a sufficient condition in my formulation of the problem.  Rather, it
  18. >>is necessary that *no player feels that _any other player_ received
  19. >>a better portion.*
  20. >
  21. >It is not clear to me whether a player is judging (subjective)
  22. >values of shares in themselves, or (subjective) values of 
  23. >shares to particular players.
  24.  
  25. Ah.  Pardon me for not being too clear on that one.  Each player
  26. measures the value of each portion by his own utility function.
  27. So, when I say "player A feels that player B got a better portion,"
  28. I mean "player A would rather have player B's portion than his own
  29. portion."
  30.  
  31.  
  32. It is trivial to show that with the other interpretation, there may not
  33. be an envy-free division.  E.g, suppose UA is A's utility function,
  34. UB is B's u.f., 0 is the "null portion," and P is the original pile.  If
  35. UB(0) > UA(P)-- unusual, but conceivable-- then it is clear that no
  36. envy-free division exists.
  37.  
  38. Even if you impose further constraints on the utility functions so
  39. that an envy-free division must exist-- e.g., U(0) is a constant
  40. across all players-- I doubt there could be an envy-free division
  41. algorithm, because there is no way to test for whether UA(x) > UB(y).
  42. It is, however, possible to test whether UA(x) > UA(y), by forcing
  43. A to chose between portion x and portion y.
  44.  
  45. Tony
  46. -- 
  47. Tony Minkoff                            aminkoff@sdcc13.ucsd.edu
  48. cs161fir@sdcc10.ucsd.edu                cs163wav@sdcc8.ucsd.edu
  49. "This quote is in this .sig for no particular reason."
  50.