Proportional (fair division)

From formulasearchengine
Jump to navigation Jump to search

{{#invoke:Hatnote|hatnote}} 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 people would ensure each of them got at least 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,[1] 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 of the resource (for people). Each following person then examines the portion in turn, removing a part for themselves if they believe the portion to be larger than . 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 pieces, in fact only about are needed as each person only really needs to do cuts when the th player comes along. Last diminsher only needs cuts. Algorithms using divide and conquer can reduce the number considerably to bring the number of cuts down to about .

The Dubins-Spanier moving knife procedure also achieves proportional division. It was the first example of a continuous procedure in fair division. The knife is passed over the cake from one end to the other. A player says stop when they think 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. Similar to the last diminisher procedure, it can be used to cut the cake into contiguous parts for each player.

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

Comparison with Envy-free division

A proportional division might not be envy-free. That means that a player might get a piece that has size 1/n, but still prefer a piece that other player has.

For two players proportional division happens to be the same as envy-free division: If a player got 1/2 or more (on his subjective value unit) then the other piece is 1/2 or less, and the player does not envy that piece.

However, for three players and more, proportional division is weaker than envy-free division. It could happen that a player believes he received at least 1/n of the resource but also believes that there is a player that received more than he did. For instance, the Successive Pairs Algorithm for three persons could yield to a situation where the first person thinks that the third player received more than he did (if the portion of the second player part that the third player chose looks bigger - to the first player- than the other portions of the second player part).

See also


  1. Optimization in Integers and Related Extremal Problems. T.L.Saaty. McGraw-Hill 1970
  • 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