Super-proportional division

In the context of fair cake-cutting, 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 ( $V>1/n$ ).

A super-proportional division is better than a proportional division, in which each partner is guaranteed to receive at least 1/n ( $V\geq 1/n$ ). However, in contrast to proportional division, a super-proportional 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.

A necessary condition for the existence of a super-proportional division is, therefore, that not all partners have the same value measure.

A 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.

Conjecture

The existence of a super-proportional division was first conjectured as early as 1948:[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.

Existence proof

The first published proof to the existence of super-proportional division was as a corollary to the Dubins–Spanier convexity theorem. This was a purely existential proof based on convexity arguments.

Protocol

A protocol for finding a super-proportional division was presented in 1986.[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.

gollark: Fortunately, our systems extend into all hypothetical scenarios and preemptively neutralize the portions of features of devices anywhere capable of damaging them.

gollark: No.

gollark: How quaint.

gollark: I can just do it every few milliseconds.

gollark: So I can remotely convert any of your webservers into a teapot?

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.