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 (
Contents
- Conjecture
- Existence proof
- Protocol
- Single piece of disagreement
- Two pieces of disagreement
- Super proportional division for two partners
- Super proportional division for n partners
- References
A super-proportional division is better than a proportional division, in which each partner is guaranteed to receive at least 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:
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.
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=VAlice(X) and b=VBob(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 CX (say, Z) must have a value of more than 1/q.
So now we have two pieces, Y and Z, such that:
VBob(Y)>VBob(Z) VAlice(Y)<VAlice(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:
Ask partner #1 to divide his share to
Partner #1 remains with a value of
As for the new partner, after having taken q pieces from each of the first i-1 partners, his total value is at least:
This proves that the new division is also super-proportional.