Proportional (fair division)

Proportional division or simple fair division is the original and simplest problem in fair division. Fair division problems are also called "cake-cutting" problems. A proportional division of a cake between $N$ people would ensure each of them got at least $1/N$ of the cake by their own valuation. The cake can have an irregular structure, for instance a fruit-cake with icing, and the recipients may value the different parts differently. There is no requirement for a division to be envy-free.

There are two main types of solution studied: "discrete" procedures require one person at a time to divide the resource, "moving knife" ones have one or more knives move over the resource and people can choose when to stop them.

The problem generalizes directly to other resources that can be split easily without losing value. The methods adapt easily to similar problems in chore division (dividing up an undesirable resource). Proportional division problems also include dividing a resource where each recipient is entitled to a different proportion. Fair division of indivisible good is however a much harder problem.

Two players

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.

Many players

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

A simple method, the Successive Pairs Algorithm, [Optimization in Integers and Related Extremal Problems. T.L.Saaty. McGraw-Hill 1970] 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.

An early method due to Banach and Knaster, the Last Diminisher Algorithm, depends on trimming pieces. It 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.

Straightforward algorithms like those above can lead to the resource being divided into a very large number of tiny bits. Straightforward use of the successive pairs algorithm would generate $n!$ pieces, in fact only about $n^3/3$ are needed as each person only really needs to do $n-1$ cuts when the $n$^th player comes along. Last diminsher only needs $n\; imes(n-1)/2$ cuts. Algorithms using divide and conquer can reduce the number considerably to bring the number of cuts down to about $n\; imeslog\_2(n)$.

The Dubins-Spanier moving knife procedure also achieves proportional division. It was the first example of a continuous procedure in far division. The knife is passed over the cake from one end to the other. A player says stop when they think $1\; /\; n$ of the cake is to the left of the knife, the cake is cut and they get that piece. Repeat with the remaining cake and players, the last player gets the remainder of the cake. This is similar to the last diminisher procedure and like it can be used to cut the cake into contiguous parts for each player.

Proportional division where the entitlements of he players differ can for rational ratios be handled by treating each player as a number of proxy players each entitled to the same amount.

See also

* Allocative efficiency

References

* Jack Robertson and William Webb (1998). "Cake-Cutting Algorithms: Be Fair If You Can", AK Peters Ltd, . ISBN 1-56881-076-8.
* Steven J. Brams and Alan D. Taylor (1996). "Fair Division - From cake-cutting to dispute resolution" Cambridge University Press. ISBN 0-521-55390-3