Super-proportional division

A super-proportional division is a kind of a fair division. It is a division of resources among n partners, in which the value received by each partner is strictly more than his/her due share of 1/n of the total value. Formally, in a super-proportional division of a resource C among n partners, each partner i, with value measure V_i, receives a share X_i such that

$V_{i}(X_{i})>V_{i}(C)/n$ .

Obviously, a super-proportional division does not exist when all partners have the same value measure. The best condition that can always be guaranteed is $V_{i}(X_{i})\geq V_{i}(C)/n$ , which is the condition for a plain proportional division. However, one may hope that, when different agents have different valuations, it may be possible to use this fact for the benefit of all players, and give each of them strictly more than their due share.

Existence

In 1948, Hugo Steinhaus conjectured the existence of a super-proportional division of a cake:[1]

It may be stated incidentally that if there are two (or more) partners with different estimations, there exists a division giving to everybody more than his due part (Knaster); this fact disproves the common opinion that differences estimations make fair division difficult.

In 1961, Dubins and Spanier proved that the necessary condition for existence is also sufficient. That is, whenever the partners' valuations are additive and non-atomic, and 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.

The proof was a corollary to the Dubins–Spanier convexity theorem. This was a purely existential proof based on convexity arguments.

Protocol

In 1986, Douglas R. Woodall published a protocol for finding a super-proportional division.[2]

Single piece of disagreement

Let C be the entire cake. The protocol starts with a specific piece of cake, say X ⊆ C, which is valued differently by two partners. Call these partners Alice and Bob.

Let a=V_Alice(X) and b=V_Bob(X) and assume w.l.o.g. that b>a.

Two pieces of disagreement

Find a rational number between b and a, say p/q such that b > p/q > a. Ask Bob to divide X to p equal parts and divide C \ X to q-p equal parts.

By our assumptions, Bob values each piece of X as more than 1/q and each piece of C \ X as less than 1/q. But for Alice, at least one piece of X (say, Y) must have a value of less than 1/q and at least one piece of C\X (say, Z) must have a value of more than 1/q.

So now we have two pieces, Y and Z, such that:

V_Bob(Y)>V_Bob(Z)

V_Alice(Y)<V_Alice(Z)

Super-proportional division for two partners

Let Alice and Bob divide the remainder C \ Y \ Z between them in a proportional manner (e.g. using divide and choose). Add Z to the piece of Alice and add Y to the piece of Bob.

Now each partner thinks that his/her allocation is strictly better than the other allocation, so its value is strictly more than 1/2.

Super-proportional division for n partners

The extension of this protocol to n partners is based on Fink's "Lone Chooser" protocol.

Suppose we already have a super-proportional division to i-1 partners (for i≥3). Now partner #i enters the party and we should give him a small piece from each of the first i-1 partners, such that the new division is still super-proportional.

Consider e.g. partner #1. Let d be the difference between partner #1's current value and (1/(i-1)). Because the current division is super-proportional, we know that d>0.

Choose a positive integer q such that: $d>{\frac {1}{(i-1)i(q(i-1)-1)}}$

Ask partner #1 to divide his share to $qi-1$ pieces which he considers of equal value and let the new partner choose the $q$ pieces which he considers to be the most valuable.

Partner #1 remains with a value of ${\frac {(qi-1)-q}{qi-1}}={\frac {q(i-1)-1}{qi-1}}$ of his previous value, which was ${\frac {1}{i-1}}+d$ (by definition of d). The first element becomes ${\frac {q(i-1)-1}{(i-1)(qi-1)}}$ and the d becomes ${\frac {1}{i(i-1)(qi-1)}}$ ; summing them up gives that the new value is more than: ${\frac {(qi-1)(i-1)}{(i-1)i(qi-1)}}={\frac {1}{i}}$ of the entire cake.

As for the new partner, after having taken q pieces from each of the first i-1 partners, his total value is at least: ${\frac {q}{qi-1}}>{\frac {1}{i}}$ of the entire cake.

This proves that the new division is also super-proportional.

References

Steinhaus, Hugo (1948). "The problem of fair division". Econometrica. 16 (1): 101–4. JSTOR 1914289.
Woodall, D. R. (1986). "A note on the cake-division problem". Journal of Combinatorial Theory, Series A. 42 (2): 300. doi:10.1016/0097-3165(86)90101-9.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[steinhaus48-1] Steinhaus, Hugo (1948). "The problem of fair division". Econometrica. 16 (1): 101–4. JSTOR 1914289.

[Woodall1986-2] Woodall, D. R. (1986). "A note on the cake-division problem". Journal of Combinatorial Theory, Series A. 42 (2): 300. doi:10.1016/0097-3165(86)90101-9.