Jump to content

Proportional division: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
No edit summary
 
(48 intermediate revisions by 20 users not shown)
Line 1: Line 1:
{{for|the scheduling algorithm|Proportionally fair}}
{{for|the scheduling algorithm|proportional-fair scheduling}}{{for|the social choice rule|proportional-fair rule}}
A '''proportional division''' is a kind of [[fair division]] in which a resource is divided among ''n'' partners, giving each partner at least 1/''n'' of the resource by their own subjective valuation. For example, consider a land asset that has to be divided among 3 heirs: Alice and Bob who think that it's worth 3 million dollars, and George who thinks that it's worth $4.5M. In a proportional division, Alice receives a land-plot that she believes to be worth at least $1M, Bob receives a land-plot that ''he'' believes to be worth at least $1M (even though Alice may think it is worth less), and George receives a land-plot that he believes to be worth at least $1.5M.
A '''proportional division''' is a kind of [[fair division]] in which a resource is divided among ''n'' partners with subjective valuations, giving each partner at least 1/''n'' of the resource by his/her own subjective valuation.


proportionality was the first fairness criterion studied in the literature; hence it is sometimes called "simple fair division".
Proportionality was the first fairness criterion studied in the literature; hence it is sometimes called "simple fair division". It was first conceived by Steinhaus.<ref>{{cite journal |last1=Steinhaus |first1=Hugo |title=The problem of fair division|journal=Econometrica |volume=16 |issue=1 |year=1948 |pages=101–104|jstor=1914289}}</ref>

== Example ==
Consider a land asset that has to be divided among 3 heirs: Alice and Bob who think that it's worth 3 million dollars, and George who thinks that it's worth $4.5M. In a proportional division, Alice receives a land-plot that she believes to be worth at least $1M, Bob receives a land-plot that ''he'' believes to be worth at least $1M (even though Alice may think it is worth less), and George receives a land-plot that he believes to be worth at least $1.5M.


== Existence ==
== Existence ==
A proportional division does not always exist. For example, if the resource contains several indivisible items and the number of people is larger than the number of items, then some people will get no item at all and their value will be zero.
A proportional division does not always exist. For example, if the resource contains several indivisible items and the number of people is larger than the number of items, then some people will get no item at all and their value will be zero. Nevertheless, such a division exists with high probability for indivisible items under certain assumptions on the valuations of the agents.<ref>{{cite journal |last1=Suksompong |first1=Warut |title=Asymptotic existence of proportionally fair allocations |journal=Mathematical Social Sciences |volume=81 |year=2016 |pages=62–65| doi=10.1016/j.mathsocsci.2016.03.007|arxiv=1806.00218 }}</ref>


A proportional division is guaranteed to exist if the following conditions hold:
Moreover, a proportional division is guaranteed to exist if the following conditions hold:
* The valuations of the players are ''non-atomic'', i.e., there are no indivisible elements with positive value.
* The valuations of the players are ''non-atomic'', i.e., there are no indivisible elements with positive value.
* The valuations of the players are ''additive'', i.e., when a piece is divided, the sum of a piece is equal to the sum of its parts.
* The valuations of the players are ''additive'', i.e., when a piece is divided, the value of the piece is equal to the sum of its parts.


Hence, proportional division is usually studied in the context of [[fair cake-cutting]].
Hence, proportional division is usually studied in the context of [[fair cake-cutting]]. See [[proportional cake-cutting]] for detailed information about procedures for achieving a proportional division in the context of cake-cutting.


A more lenient fairness criterion is ''partial proportionality'', in which each partner receives a certain fraction ''f(n)'' of the total value, where ''f''(''n'') ≤ 1/''n''. Partially proportional divisions exist (under certain conditions) even for indivisible items.
A more lenient fairness criterion is ''partial proportionality'', in which each partner receives a certain fraction ''f''(''n'') of the total value, where ''f''(''n'') ≤ 1/''n''. Partially proportional divisions exist (under certain conditions) even for indivisible items.


== Procedures ==

For two people, [[divide and choose]] is the classic solution. One person divides the resource into what they believe are equal halves, and the other person chooses the "half" they prefer. If the valuations are non-atomic and additive, then both the divider and the chooser can act in a way that guarantees that they get a value of at least 1/2: the divider can cut the cake to two pieces that he thinks are equal, and the chooser can pick the piece that he thinks is more valuable.

There are many ways to extend this procedure to more than 2 people. Each way has its own advantages and disadvantages.


=== Simple procedures ===

'''[[Last diminisher]]''' is the earliest proportional division procedure developed for ''n'' people:
* One of the partners is asked to draw a piece which he values as at least 1/''n''.
* The other partners in turn have the option to claim that the current piece is actually worth more than 1/''n''; in that case, they are asked to diminish it such that the remaining value is 1/''n'' according to their own valuation.
* The last partner to diminish the current piece, receives it.
* The remaining cake is then divided in the same way among the remaining ''n''-1 people.
By induction, it is possible to prove that each partner following the rules is guaranteed to get a value of 1/''n'', regardless of what the other partners do. This is a discrete procedure that can be played in turns. In the worst case, <math>n\times(n-1)/2 = O(n^2)</math> actions are needed: one action per player per turn. However, most of these actions can be done on paper; only ''n''-1 cuts of the cake are actually needed. Hence, if the cake is contiguous then it is possible to guarantee that each piece is contiguous.

'''Dubins-Spanier [[Moving-knife procedure]]''' is a continuous-time version of Last Diminisher.<ref name=ds61>{{Cite doi|10.2307/2311357}}</ref>
* A knife is passed over the cake, parallel to itself, from one end to the other.
* A partner says 'stop' when they think <math>1 / n</math> of the cake is to the left of the knife. Then the cake is cut and they get that piece.
* This is repeated with the remaining cake and partners. the last partner gets the remainder of the cake.

'''Successive Pairs'''<ref>Optimization in Integers and Related Extremal Problems. T.L.Saaty. McGraw-Hill 1970</ref> is an algorithm that continues the division to successively smaller "equal" portions.
* The first partner divides the resource into what they believe are equal halves.
* The second then chooses a half, leaving the remainder for the first partner
* Each of these two partners then divide their respective portions into thirds.
* The third partner picks two of the resulting portions: one from the first partner and one from the second partner.
* If there are four partners, each of the first three partners divides their portions into fourths, and the process continues.
In contrast to Last Diminisher, this algorithm generates disconnected pieces ("crumbs"). Straightforward use of the successive pairs algorithm would generate <math>n!</math> pieces, in fact only about <math>n^3/3</math> are needed as each partner only really needs to do <math>n-1</math> cuts when the <math>n</math><sup>th</sup> partner comes along.


=== Recursive halving ===

Using a divide-and-conquer strategy, it is possible to achieve a proportional division in time O(''n'' log ''n'').<ref name=ep84>{{Cite doi|10.1016/0166-218x(84)90005-2}}</ref> For simplicity the procedure is described here for an even number of partners, but it can be easily adapted to any number of partners:

* Each partner is asked to draw a line dividing the cake to two pieces that he believes to be of equal value. The cuts are required to be non-intersecting; a simple way to guarantee this is to allow only horizontal lines or only vertical lines.
* The algorithm sorts the ''n'' lines in increasing order and cuts the cake in the median of the lines. E.g., if there are 4 partners that draw lines at ''x''=1, ''x''=3, ''x''=5 and ''x''=9, then the algorithm cuts the cake vertically at ''x''=4.
* The algorithm assigns to each of the two halves ''n''/2 partners - the partners whose line is inside that half. E.g., the partners that drew lines at ''x''=1 and ''x''=3 are assigned to the western half and the other two partners are assigned to the eastern half. Each half is divided recursively among the ''n''/2 partners assigned to it.

It is possible to prove by induction that every partner playing by the rules is guaranteed a piece with a value of at least 1/''n'', regardless of what the other partners do.

Thanks to the divide-and-conquer strategy, the number of iterations is only O(log ''n''), in contrast to O(''n'') in the Last Diminisher procedure. In each iteration, each partner is required to make a single mark. Hence, the total number of marks required is O(''n'' log ''n'').

==== Randomized version ====
It is possible to use randomization in order to reduce the number of marks. The following randomized version of the recursive halving procedure achieves a proportional division using only O(''n'') mark queries on average.<ref name=ep84/> The idea is that, in each iteration, instead of asking ''all'' partners to make a half-value mark, only ''some'' partners are asked to make such marks, while the other partners only choose which half they prefer. The partners are sent either to the west or to the east according to their preferences, until the number of partners in each side is ''n''/2. Then a cut is made, and each group of ''n''/2 partners divides its half recursively.<ref>This randomized recursive halving algorithm is similar to a well-known randomized algorithm for [[Ranking]] - finding the ''r''-ranked element in an array of numbers</ref>

In the worst case we still need ''n''-1 marks per iteration so the worst-case number of marks required is O(''n'' log ''n''). However, on average only O(log ''n'') marks are required per iteration; by solving a recurrence formula it is possible to show that the average number of marks required is O(''n'').

Note that the ''total'' number of queries is still O(''n'' log ''n''), since each partner has to select a half.


=== Selection procedures ===

A different approach to cake-cutting is to let every partner draw a certain number of pieces depending on the number of partners, ''p''(''n''), and give each partner one of his selected pieces, such that the pieces do not overlap.

As a simple example of a selection procedure, assume the cake is a 1-dimensional interval and that each partner wants to receive a single contiguous interval. Use the following protocol:
# Each partner privately partitions the cake to ''n'' intervals that he considers to be of equal value; these are called ''candidate pieces''.
# The protocol orders the ''n''^2 candidates by increasing order of their eastern (from west to east) and select the interval with the most western eastern end. This interval is called a ''final piece''.
# The protocol gives the final piece to its owner and remove all candidates intersected by it. Step #2 is then repeated with the remaining intervals of the remaining ''n''-1 partners.
The selection rule in step #2 guarantees that, at each iteration, at most one interval of every partner is removed. Hence, after each iteration the number of intervals per partners is still equal to the number of partners, and the process can proceed until every partner receives an interval.<ref>This selection procedure is similar to the [[Interval scheduling#Greedy polynomial solution]])</ref>.

This protocol requires each partner to answer ''n'' queries so the query complexity is O(''n''^2), similarly to Last Diminisher.

==== Randomized versions ====

It is possible to use randomization in order to reduce the number of queries. The idea is that each partner reports, not the entire collection of ''n'' candidates but only a constant number ''d'' of candidates, picked at random. The query complexity is O(''n''), which is obviously the best possible. In many cases, it will still be possible to give each partner a single candidate such that the candidates do not overlap. However, there are scenarios in which such an allocation will be impossible.

We can still cut a cake using O(''n'') queries if we make several compromises:
* Instead of guaranteeing full proportionality, we guarantee ''partial proportionality'', i.e. each partner receives a certain constant fraction ''f'' of the total value, where ''f''<1/''n''.
* Instead of giving each partner a single contiguous piece, we give each partner a union of one or more disjoint pieces.

The general scheme is as follows:<ref name=ep06pos>{{Cite doi|10.1109/focs.2006.17}}</ref>
# Each partner privately partitions the cake to ''an'' pieces of equal subjective value. These ''n⋅an'' pieces are called ''candidate pieces''.
# Each partner picks 2''d'' candidate pieces uniformly at random, with replacement. The candidates are grouped into ''d'' pairs, which the partner reports to the algorithm. These ''n⋅d'' pairs are called ''quarterfinal brackets''.
# From each quarterfinal bracket, the algorithm selects a single piece - the piece that intersects the fewer number of other candidate pieces. These ''n⋅d'' pieces are called ''semifinal pieces''.
# For each partner, the algorithm selects a single piece; they are called ''final pieces''. The final pieces are selected such that each point of the cake is covered by at most 2 final pieces (see below). If this succeeds, proceed to step #5. If this fails, start over at step #1.
# Each part of the cake which belongs to only a single final piece, is given to the owner of that piece. Each part of the cake which belongs to two final pieces, is divided proportionally by any deterministic proportional division algorithm.

The algorithm guarantees that, with high probability, each partner receives at least half of one of his candidate pieces, which implies (if the values are additive) a value of at least 1/2''an''. There are O(''n'') candidate pieces and O(''n'') additional divisions in step #5, each of which takes O(1) time. Hence the total run-time of the algorithm is O(''n'').

The main challenge in this scheme is selecting the final pieces in step #4:

Start by creating the '''implication graph''': a graph whose nodes are the semifinal pieces, and there is an edge from piece ''I'' of partner ''i'' to piece ''J'' of partner ''j'' if piece ''I'' intersects the ''other'' piece of partner ''j'' (hence, if we select piece ''I'' and want to avoid intersection, we ought to select piece ''J'' too).

Select an arbitrary partner ''i'' that has not received a piece yet, and select an arbitrary piece ''I'' of that partner as a final piece. Then, traverse the links in the implication graph and select as final pieces all pieces that are reachable from ''I''. There are two good scenarios: either we allocate a single final piece to each partner and we are done, or we
reach a piece with no outgoing links (which implies that it does not intersect other pieces). In the latter case we just pick another piece of one of the remaining partners and continue. The bad scenario is that our traversal leads us to two different pieces of the same partner, or equivalently to the other piece of partner ''i'' from whom we started. Such a path, leading from one piece of partner ''i'' to another piece of the same partner, is called a '''pair path'''. If the implication graph contains no pair paths, then the selection algorithm just described returns a collection of ''n'' non-overlapping final pieces and we are done. Now it remains to calculate the probability that the implication graph contains a pair path.

First, consider the special case in which all partners have ''the same'' value function (and hence the same collection of candidate pieces). In this case the probability of a pair path is easy to calculate: since the probability of each edge is 1/''an'', and all edges are independent, the probability of a specific pair path of length ''k'' is 1/(''an'')^k, and the probability of any pair path is at most:

:<math>\Sigma_{k}\frac{(2dn)!}{(2dn-k)!(an)^k} = O(\frac{1}{a^2})</math>

By selecting ''d''=1 and ''a'' sufficiently large, it is possible to make this probability as small as we want. This is true even if we omit the semi-final selection phase (#3) and just take all quarter-final pieces as semi-final.

Note that this case is analogous to the [[balls into bins]] model. It proves that, if ''d'' bins are picked randomly for each ball, then it is possible to select one bin for each ball such that the bins are all distinct (- the maximum load is 1).

In the general cake model, where the value functions are different, the probabilities of the edges in the implication graph are dependent. but thanks to the semi-final selection phase, we can prove that the probability that the implication graph contains a pair path of length at least 3 is at most <math>\frac{32 d^5}{a^2\cdot(a - 4 d^2)}</math>.

It remains to handle pair paths of length 2. Unfortunately the probability of having such pair paths in the implication graph is not negligible. However, with high probability it is possible to partition the partners to two groups, such that in each group there is no pair path of length 2. Hence, we can run the final-piece-selection algorithm twice: once for each group. Intersection can occur only between final pieces of different groups; hence the overlap in each point of the cake is at most 2. The probability that such a 2-partition is ''not'' possible is at most <math>\frac{16 d^3}{a^3}+\frac{8d^2}{a^2}</math>.

By summing the above two expressions and setting ''d''=2, we get that the probability of failure is still <math>O(\frac{1}{a^2})</math>. Recall that ''a'' is the proportionality ratio - the more value we want to guarantee each partner, the more likely it is that the division will fail and we will have to start over at step #1.

The same algorithm works also when the cuts are approximate, i.e., the partners do not know to mark pieces with exactly the same value; they might mark a piece with a value of ''p'' percent above or below the required value, where the exact error is picked at random. <ref name=ep06pos/>

It is possible to further reduce the probability of failure using the following scheme:<ref name=ep08>{{Cite doi|10.1007/978-3-540-68880-8_16}}</ref>
* Make two independent runs of the original protocol.
* In each run, remove every partner that appears in the beginning of a pair path, and allocate final pieces only to the remaining partners as in the original protocol.
* If for every partner there is at least one run in which it is not removed, then we are done since every partner now holds at least one final piece.

The probability of removing a specific partner in each run is <math>O(\frac{1}{n})</math>. The probability of removing a specific partner in both runs is <math>O(\frac{1}{n^2})</math>. Hence the probability of failure is <math>O(\frac{n}{n^2})=O(\frac{1}{n})</math>, which goes to 0 when ''n'' increases, even when the partial proportionality ratio ''a'' is kept constant.

== Hardness results ==
The hardness results are stated in terms of the "standard Robertson-Webb model", i.e., they relate to procedures employing two types of actions: "Evaluate" and "Cut".

Every deterministic proportional division procedure for ''n''≥3 partners must use at least ''n'' actions, even if all valuations are identical.<ref name=ep84/>

Moreover, every deterministic or randomized proportional division procedure assigning each person a contiguous piece must use Ω(''n'' log ''n'') actions.<ref name=ws07>{{Cite doi|10.1016/j.disopt.2006.07.003}}</ref>

Moreover, every deterministic proportional division procedure must use Ω(''n'' log ''n'') actions, even if the procedure is allowed to assign to each partner a piece that is a union of intervals, and even if the procedure is allowed to only guarantee ''approximate fairness''. The proof is based on lower bounding the complexity to find, for a single player, a piece of cake that is both rich in value, and thin in width.<ref name=ep06neg>{{Cite doi|10.1145/1109557.1109588}}, {{Cite doi|10.1145/2000807.2000819}}</ref>

These hardness results imply that [[#Recursive halving]] is the fastest possible algorithm for achieving full proportionality with contiguous pieces, and it is the fastest possible deterministic algorithm for achieving even partial proportionality and even with disconnected pieces. The only case in which it can be improved is with randomized algorithms guaranteeing partial proportionality with disconnected pieces.

If the players are able to cut with only finite precision, then the Ω(n log n) lower bound also includes randomized protocols.<ref name=ep06neg/>

The following table summarizes the known results:<ref name=ep06pos/>

{| class="wikitable sortable"
|-
! '''Proportionality'''<br/>(full/partial) !! '''Pieces'''<br/>(contiguous/disjoint) !! '''Protocol type'''<br/>(deterministic/randomized) !! '''Queries'''<br/>(exact/approximate) !! #queries

|-
| full || contiguous || det. || exact || O(''n'' log ''n'')<ref name=ep84/><br/>Ω(''n'' log ''n'')<ref name=ws07/>
|-
| full || contiguous || det. || approximate || Ω(''n'' log ''n'')<ref name=ws07/>
|-
| full || contiguous || rand. || exact || O(''n'' log ''n'')<ref name=ep84/><br/>Ω(''n'' log ''n'')<ref name=ws07/>
|-
| full || contiguous || rand. || approximate || Ω(''n'' log ''n'')<ref name=ws07/>

|-
| full || disconnected || det. || exact || O(''n'' log ''n'')<ref name=ep84/><br/>Ω(''n'' log ''n'')<ref name=ep06neg/>
|-
| full || disconnected || det. || approximate || Ω(''n'' log ''n'')<ref name=ep06neg/>
|-
| full || disconnected || rand. || exact || O(''n'' log ''n'')<ref name=ep84/>
|-
| full || disconnected || rand. || approximate || Ω(''n'' log ''n'')<ref name=ep06neg/>

|-
| partial || contiguous || det. || exact || O(''n'' log ''n'')<ref name=ep84/><br/>Ω(''n'' log ''n'')<ref name=ep06neg/>
|-
| partial || contiguous || det. || approximate || Ω(''n'' log ''n'')<ref name=ep06neg/>
|-
| partial || contiguous || rand. || exact || O(''n'' log ''n'')<ref name=ep84/>
|-
| partial || contiguous || rand. || approximate || Ω(''n'' log ''n'')<ref name=ep06neg/>

|-
| partial || disconnected || det. || exact || O(''n'' log ''n'')<ref name=ep84/><br/>Ω(''n'' log ''n'')<ref name=ep06neg/>
|-
| partial || disconnected || det. || approximate || Ω(''n'' log ''n'')<ref name=ep06neg/>
|-
| partial || disconnected || rand. || exact || O(''n'')<ref name=ep06pos/>
|-
| partial || disconnected || rand. || weakly approx. <br/>(error independent<br/>of value) || O(''n'')<ref name=ep06pos/>
|-
| partial || disconnected || rand. || approximate || Ω(''n'' log ''n'')<ref name=ep06neg/>
|}


== Variants ==
== Variants ==

=== Weighted proportional division ===

The proportionality criterion can be generalized to situations in which the [[entitlement (fair division)|entitlements]] of the partners are not equal. For example, the resource may belong to shareholders such that one of them holds 20% and the other holds 80%. This leads to the criterion of ''weighted proportionality'': there are several weights ''w<sub>i</sub>'' that sum up to 1, and every partner ''i'' receives at least a fraction ''w<sub>i</sub>'' of the resource by their own valuation.

When the value functions are additive and non-atomic, a weighted proportional division is guaranteed to exist for every set of weights.<ref name=ds1>{{Cite doi|10.2307/2311357}}, Corollary 1.1</ref>

When the entitlements are rational numbers, a weighted proportional division can be found by treating each player as a number of ''proxy players'', each entitled to the same amount. For example, if Alice is entitled to 2/5 of the cake and George is entitled to 3/5, then we can define 5 proxy players: Alice1, Alice2, George1, George2 and George3, and use any proportional division algorithm to give each proxy player a value of 1/5.

Note that this simple scheme does not preserve the geometric properties of the original algorithm. I.e., if the original division algorithm guarantees that each partner receives a contiguous piece, this is no longer guaranteed when using proxy players.

=== Exact division ===

An ''exact division'' is a division in which each partner receives exactly 1/''n'' of the resource according to the valuations of ''all n partners''. A ''weighted exact division'' is a division in which every partner ''i'' receives exactly a fraction ''w<sub>i</sub>'' of the resource according to the valuations of all n partners.

When the value functions are additive and non-atomic, a weighted exact division is guaranteed to exist for every set of weights. This is a consequence of the convexity of the space of partitions.<ref name=ds1/>



=== Super-proportional division ===
=== Super-proportional division ===
{{Main|Super-proportional division}}


A ''super-proportional division'' is a division in which each partner receives strictly more than 1/''n'' of the resource by their own subjective valuation.
A ''super-proportional division'' is a division in which each partner receives strictly more than 1/''n'' of the resource by their own subjective valuation.


Of course such a division does not always exist: when all partners have exactly the same value functions, the best we can do is give each partner exactly 1/''n''. So a necessary condition for the existence of a super-proportional division is that not all partners have the same value measure.
When the valuations are additive and non-atomic, a super-proportional division always exists.<ref name=ds2>{{Cite doi|10.2307/2311357}}, Corollary 1.2</ref>


The surprising fact is that, when the valuations are additive and non-atomic, this condition is also sufficient. I.e., when there are at least ''two'' partners whose value function is even slightly different, then there is a super-proportional division in which ''all'' partners receive more than 1/''n''. See [[super-proportional division]] for details.


== Relations to other fairness criteria ==
=== Proportional division of chores ===
{{Proportionality vs. envy-freeness}}

When the resource to divide is undesirable (like in [[chore division]]), a proportional division is defined as a division giving each person ''at most'' 1/''n'' of the resource (i.e. the sign of inequality is inversed).

Most algorithms for proportional division can be adapted to chore division in a straightforward way.

==Comparison with Envy-freeness and other criteria==

=== Implications ===

When there are only two players, a proportional division is always [[envy-free]]: 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, a proportional division might not be [[envy-free]]. For instance, the '''Successive Pairs Algorithm''' for three persons could yield to a situation where the first person thinks that the third person 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). So the first person might get a piece with value 1/3, but still prefer the third person'ss piece which has value 2/3.

If the value functions of the players are [[sigma additive]], then an envy-free division is always proportional, since a piece with a value of not less than the other pieces, must have a value of at least 1/''n''. However, when the value functions are not additive, an envy-free division might be not proportional. For example, it is possible that the cake is divided in such a way that makes both pieces useless for one of the players. Then, this player will not envy the other player because there is nothing to envy, but his value will be much less than 1/2. The following table summarizes the implications between envy-freeness (EF) and proportionality (PR):

{| class="wikitable"
|-
! Agents !! Valuations !! EF implies PR? !! PR implies EF?
|-
| 2 || additive || yes || yes
|-
| 2 || general || no || yes
|-
| 3+ || additive || yes || no
|-
| 3+ || general || no || no
|}



=== Stability to voluntary exchanges ===
=== Stability to voluntary exchanges ===
Line 243: Line 36:
One advantage of the proportionality criterion over envy-freeness and similar criteria is that it is stable with regards to voluntary exchanges.
One advantage of the proportionality criterion over envy-freeness and similar criteria is that it is stable with regards to voluntary exchanges.


As an example, assume that a certain land is divided among 3 partners: Alice, Bob and George, in a division that is both proportional and envy-free. Several months later, Alice and George decide to merge their land-plots and re-divide them in a way that is more profitable for them. From Bob's point of view, the division is still proportional, since he still holds a subjective value of at least 1/3 of the total, regardless of what Alice and George do with their plots. On the other hand, the new division might not be envy free. For example, it is possible that initially both Alice and George received a land-plot which Bob subjectively values as 1/3, but now after the re-division George got all the value (in Bob's eyes) so now Bob envies George.
As an example, assume that a certain land is divided among 3 partners: Alice, Bob and George, in a division that is both proportional and envy-free. Several months later, Alice and George decide to merge their land-plots and re-divide them in a way that is more profitable for them. From Bob's point of view, the division is still proportional, since he still holds a subjective value of at least 1/3 of the total, regardless of what Alice and George do with their plots. On the other hand, the new division might not be envy free. For example, it is possible that initially both Alice and George received a land-plot which Bob subjectively values as 1/3, but now after the re-division George got all the value (in Bob's eyes) so now Bob envies George.


Hence, using envy-freeness as the fairness criterion implies that we must constrain the right of people to voluntary exchanges after the division. Using proportionality as the fairness criterion has no such negative implications.
Hence, using envy-freeness as the fairness criterion implies that we must constrain the right of people to voluntary exchanges after the division. Using proportionality as the fairness criterion has no such negative implications.


=== Individual rationality ===
=== Individual rationality ===
An additional advantage of proportionality is that it is compatible with [[individual rationality]] in the following sense. Suppose ''n'' partners own a resource in common. In many practical scenarios (though not always), the partners have the option to sell the resource in the market and split the revenues such that each partner receives exactly 1/''n''. Hence, a rational partner will agree to participate in a division procedure, only if the procedure guarantees the he receives at least 1/''n'' of his total value.
An additional advantage of proportionality is that it is compatible with [[individual rationality]] in the following sense. Suppose ''n'' partners own a resource in common. In many practical scenarios (though not always), the partners have the option to sell the resource in the market and split the revenues such that each partner receives exactly 1/''n''. Hence, a rational partner will agree to participate in a division procedure, only if the procedure guarantees that he receives at least 1/''n'' of his total value.


Additionally, there should be at least a possibility (if not a guarantee) that the partner receives more than 1/''n''; this explains the importance of the existence theorems of [[#super-proportional division]].
Additionally, there should be at least a possibility (if not a guarantee) that the partner receives more than 1/''n''; this explains the importance of the existence theorems of [[super-proportional division]].


== See also ==
== See also ==
* [[Allocative efficiency]]
* [[Allocative efficiency]]
* [[Fair cake-cutting]]
* [[Perfect division]]
* [[Inequity aversion]]


== References ==
== References ==

{{reflist}}
{{reflist}}
* A summary of proportional and other division procedures appears in: {{Cite journal | doi = 10.2307/3616548| jstor = 3616548| title = Sharing a Cake| journal = The Mathematical Gazette| volume = 66| issue = 437| pages = 212| year = 1982| last1 = Austin | first1 = A. K.}}


[[Category:Fairness criteria]]
* 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

[[Category:Fair division]]
[[Category:Game theory]]

Latest revision as of 09:58, 16 July 2021

For the scheduling algorithm, see proportional-fair scheduling.
For the social choice rule, see proportional-fair rule.

A proportional division is a kind of fair division in which a resource is divided among n partners with subjective valuations, giving each partner at least 1/n of the resource by his/her own subjective valuation.

Proportionality was the first fairness criterion studied in the literature; hence it is sometimes called "simple fair division". It was first conceived by Steinhaus.[1]

Example

[edit]

Consider a land asset that has to be divided among 3 heirs: Alice and Bob who think that it's worth 3 million dollars, and George who thinks that it's worth $4.5M. In a proportional division, Alice receives a land-plot that she believes to be worth at least $1M, Bob receives a land-plot that he believes to be worth at least $1M (even though Alice may think it is worth less), and George receives a land-plot that he believes to be worth at least $1.5M.

Existence

[edit]

A proportional division does not always exist. For example, if the resource contains several indivisible items and the number of people is larger than the number of items, then some people will get no item at all and their value will be zero. Nevertheless, such a division exists with high probability for indivisible items under certain assumptions on the valuations of the agents.[2]

Moreover, a proportional division is guaranteed to exist if the following conditions hold:

  • The valuations of the players are non-atomic, i.e., there are no indivisible elements with positive value.
  • The valuations of the players are additive, i.e., when a piece is divided, the value of the piece is equal to the sum of its parts.

Hence, proportional division is usually studied in the context of fair cake-cutting. See proportional cake-cutting for detailed information about procedures for achieving a proportional division in the context of cake-cutting.

A more lenient fairness criterion is partial proportionality, in which each partner receives a certain fraction f(n) of the total value, where f(n) ≤ 1/n. Partially proportional divisions exist (under certain conditions) even for indivisible items.

Variants

[edit]

Super-proportional division

[edit]
Main article: Super-proportional division

A super-proportional division is a division in which each partner receives strictly more than 1/n of the resource by their own subjective valuation.

Of course such a division does not always exist: when all partners have exactly the same value functions, the best we can do is give each partner exactly 1/n. So a necessary condition for the existence of a super-proportional division is that not all partners have the same value measure.

The surprising fact is that, when the valuations are additive and non-atomic, this condition is also sufficient. I.e., when there are at least two partners whose value function is even slightly different, then there is a super-proportional division in which all partners receive more than 1/n. See super-proportional division for details.

Relations to other fairness criteria

[edit]

Implications between proportionality and envy-freeness

[edit]

Proportionality (PR) and envy-freeness (EF) are two independent properties, but in some cases one of them may imply the other.

When all valuations are additive set functions and the entire cake is divided, the following implications hold:

  • With two partners, PR and EF are equivalent;
  • With three or more partners, EF implies PR but not vice versa. For example, it is possible that each of three partners receives 1/3 in his subjective opinion, but in Alice's opinion, Bob's share is worth 2/3.

When the valuations are only subadditive, EF still implies PR, but PR no longer implies EF even with two partners: it is possible that Alice's share is worth 1/2 in her eyes, but Bob's share is worth even more. On the contrary, when the valuations are only superadditive, PR still implies EF with two partners, but EF no longer implies PR even with two partners: it is possible that Alice's share is worth 1/4 in her eyes, but Bob's is worth even less. Similarly, when not all cake is divided, EF no longer implies PR. The implications are summarized in the following table:

Valuations 2 partners 3+ partners
Additive
Subadditive
Superadditive -
General - -

Stability to voluntary exchanges

[edit]

One advantage of the proportionality criterion over envy-freeness and similar criteria is that it is stable with regards to voluntary exchanges.

As an example, assume that a certain land is divided among 3 partners: Alice, Bob and George, in a division that is both proportional and envy-free. Several months later, Alice and George decide to merge their land-plots and re-divide them in a way that is more profitable for them. From Bob's point of view, the division is still proportional, since he still holds a subjective value of at least 1/3 of the total, regardless of what Alice and George do with their plots. On the other hand, the new division might not be envy free. For example, it is possible that initially both Alice and George received a land-plot which Bob subjectively values as 1/3, but now after the re-division George got all the value (in Bob's eyes) so now Bob envies George.

Hence, using envy-freeness as the fairness criterion implies that we must constrain the right of people to voluntary exchanges after the division. Using proportionality as the fairness criterion has no such negative implications.

Individual rationality

[edit]

An additional advantage of proportionality is that it is compatible with individual rationality in the following sense. Suppose n partners own a resource in common. In many practical scenarios (though not always), the partners have the option to sell the resource in the market and split the revenues such that each partner receives exactly 1/n. Hence, a rational partner will agree to participate in a division procedure, only if the procedure guarantees that he receives at least 1/n of his total value.

Additionally, there should be at least a possibility (if not a guarantee) that the partner receives more than 1/n; this explains the importance of the existence theorems of super-proportional division.

See also

[edit]

References

[edit]
  1. ^ Steinhaus, Hugo (1948). "The problem of fair division". Econometrica. 16 (1): 101–104. JSTOR 1914289.
  2. ^ Suksompong, Warut (2016). "Asymptotic existence of proportionally fair allocations". Mathematical Social Sciences. 81: 62–65. arXiv:1806.00218. doi:10.1016/j.mathsocsci.2016.03.007.
  • A summary of proportional and other division procedures appears in: Austin, A. K. (1982). "Sharing a Cake". The Mathematical Gazette. 66 (437): 212. doi:10.2307/3616548. JSTOR 3616548.
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Proportional_division&oldid=1033866251"