Proportional (fair division)
Encyclopedia
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.
method. One person divides the resource into what they believe are equal halves, and the other person chooses the "half" they prefer.
A simple method, the Successive Pairs Algorithm, 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. 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 players differs, can for rational ratios be handled by treating each player as a number of proxy players each entitled to the same amount.
.
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).
Fair division
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 a fair amount...
. 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-freeEnvy-free
In mathematical sociology and especially game theory, envy-free is a property of certain fair division algorithms for a divisible heterogeneous good over which different players may have different preferences....
.
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
Chore division
In problems of fair division, a resource is to be divided amongst a finite number of players; the resource is assumed to be desirable, and more is assumed to be better...
(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 chooseDivide and choose
In problems of fair division, divide and choose is a two-party proportional envy-free allocation protocol. The protocol also works for dividing an undesirable, as in chore division....
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, 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. 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
Entitlement (fair division)
Entitlement in fair division describes that proportion of the resources or goods to be divided that a player can expect to receive. The idea is based on the normal idea of entitlement...
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
Obviously, for two players proportional division is the same as envy-free divisionEnvy-free
In mathematical sociology and especially game theory, envy-free is a property of certain fair division algorithms for a divisible heterogeneous good over which different players may have different preferences....
.
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).