Fair division

From Wikipedia, the free encyclopedia

"Cake cutting" redirects here. For the wedding tradition, see Wedding reception#Wedding_cake.

Fair division, also known as the cake cutting problem, is the problem of dividing a resource in such a way that all recipients believe that they have received their fair share. The problem is hard because each recipient may have a different measure of value of the resource: in the "cake cutting" version, one recipient may like marzipan, another like cherries, and so on.

For two people there is a simple solution which is commonly employed. This is the so-called divide and choose method. One person divides the resource into what they believe are equal halves, and the other person chooses the "half" they prefer. Thus, the person making the division has an incentive to divide as fairly as possible: for if they do not, they will likely receive an undesirable portion. This solution satisfies the problem's mathematical 'envy-free' requirement. However that term assumes they only work on their own valuation and don't know or consider how the other person values theirs. And on the other hand if they don't know how the other values their share the division can be very inefficient in maximising the value for each.

According to Sol Garfunkel, the cake cutting problem had been one of the most important open problems in 20th century mathematics (Ref: Sol Garfunkel. More Equal than Others: Weighted Voting. For All Practical Purposes. COMAP. 1988.), when the most important variant of the problem was finally solved together by Steven Brams and Alan Taylor in 1995.

Contents

[edit] Many players

The problem can be extended to three or more people, but the method for finding an optimum solution becomes complicated.

One method continues the division to successively smaller "equal" portions. The first person divides the resource into what they believe are equal halves. The second then chooses a half, leaving the remainder for the first person. Each of these two people then divide their respective portions into thirds. The third person picks two of the resulting portions: one from the first person and one from the second person. If there are four people, each of the first three people divides their portions into fourths, and the process continues.

A problem with this approach is that the portions may become reduced to absurdly small sizes.

Another method begins with the first person portioning off 1 / n of the resource (for n people). Each following person then examines the portion in turn, removing a part for themselves if they believe the portion to be larger than 1 / n. The last person to remove part receives the portion. The process continues until the entire resource has been fairly divided.

The problem was one of the big open problems of the twentieth century. The first cake cutting procedure that produced an envy-free division of cake for any natural number of persons was first published by Steven Brams and Alan Taylor in 1995. But because the procedure is somewhat impractical when the number of persons is large, fair division continues to be an important problem in mathematics and the social sciences.

[edit] Variants

Some cake-cutting procedures are discrete, whereby players make cuts with a knife (usually in a sequence of steps). Moving-knife procedures, on the other hand, allow continuous movement and can let players call "stop" at any point.

A variant of the fair division problem is chore division: this is the "dual" to the cake cutting problem in which an undesirable object is to be distributed amongst the players. The canonical example is a set of chores that the players between them must do. Note that "I cut, you choose" works for chore division.

Other variants include cakes which contain indivisible items (i.e. nuts or berries on the cake) which must be fairly distributed between players (such pieces are referred to as atoms), or the requirement of having connected pieces (i.e. only whole pieces and not fragments are allowed).

[edit] Limitations

The nature of the resource to be divided may affect fair division. The classic example is the tale of the Judgement of Solomon (1 Kings 3:15-28) in which King Solomon proposes to settle a dispute between two women who each claim a child by dividing the child in half. Solomon assumed the actual mother would place a greater value on the child's life than on raising the child and therefore surrender it rather than have it killed.

[edit] See also

[edit] References

  • Steven J. Brams and Alan D. Taylor (1995). "An Envy-Free Cake Division Protocol," American Mathematical Monthly, 102, pp.9-19. (JUSTOR)
  • Steven J. Brams and Alan D. Taylor (1996). Fair Division - From cake-cutting to dispute resolution Cambridge University Press. ISBN 0-521-55390-3
  • Vincent P. Crawford (1987). "fair division," The New Palgrave: A Dictionary of Economics, v. 2, pp. 274-75.
  • Jack Robertson and William Webb (1998). Cake-Cutting Algorithms: Be Fair If You Can, AK Peters Ltd, . ISBN 1-56881-076-8.
  • Bryan Skyrms (1996). The Evolution of the Social Contract Cambridge University Press. ISBN-13: 9780521555838
  • Hal Varian (1987). "fairness," The New Palgrave: A Dictionary of Economics, v. 2, pp. 275-76.

[edit] External links

v • d • e
Topics in game theory
Definitions
Equilibrium concepts
Strategies
Classes of games
Games
Theorems
Languages