Fair division
|
|
Fair division, also known as the cake cutting problem, is the problem of dividing a resource in such a way that each recipient believes 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. 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.
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, and each of these two people then divide their portion 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 <math>1/n<math> of the resource (for <math>n<math> people). Each following person then examines the portion in turn, removing a part for themselves if they believe the portion to be larger than <math>1/n<math>. The last person to remove part receives the portion. The process continues until the entire resource has been fairly divided.
The problem may be modified by requiring the division to be envy-free: that is, each recipient should not only believe that they have at least <math>1/n<math> of the resource (according to their measure) but that no other recipient has received more than they have. A procedure for envy-free division was first published by Brams and Taylor in 1995.
Fair division is usually taught in lower level college math courses and can elude math majors, paradoxically.
See also
References
- S J Brams and A D Taylor, "An Envy-Free Cake Division Protocol", American Mathematical Monthly 102, 9-19, 1995.
- Jack Robertson, William Webb, Cake-Cutting Algorithms: Be Fair If You Can, AK Peters Ltd, March 1998. ISBN 1568810768.
External Links
- [1] (http://3quarksdaily.blogs.com/3quarksdaily/2005/04/3qd_monday_musi.html) Short essay about the cake-cutting problem by S. Abbas Raza of 3 Quarks Daily