Strongly proportional division

(Redirected from Super-proportionality)

A strongly proportional division[1] (sometimes called 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 strongly proportional division of a resource C among n partners, each partner i, with value measure Vi, receives a share Xi such that

.

Obviously, a strongly proportional division does not exist when all partners have the same value measure. The best condition that can always be guaranteed is , 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

edit

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

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.

Algorithms

edit

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

Let C be the entire cake. If the agents' valuations are different, then there must be a witness for that: a witness is a specific piece of cake, say X ⊆ C, which is valued differently by some two partners, say Alice and Bob. Let Y := C \ X. Let ax=VAlice(X) and bx=VBob(X) and ay=VAlice(Y) and by=VBob(Y), and assume w.l.o.g. that:

bx > ax, which implies: by < ay.

The idea is to partition X and Y separately: when partitioning X, we will give slightly more to Bob and slightly less to Alice; when partitioning Y, we will give slightly more to Alice and slightly less to Bob.

Woodall's protocol for two agents

edit

Find a rational number between bx and ax, say p/q such that bx > p/q > ax. This implies by < (q-p)/q < ay. Ask Bob to divide X into p equal parts, and divide Y to q-p equal parts.

By our assumptions, Bob values each piece of X at bx/p > 1/q, and each piece of Y at by/(q-p) < 1/q. But for Alice, at least one piece of X (say X0) must have value less than 1/q and at least one piece of Y (say Y0) must have value more than 1/q.

So now we have two pieces, X0 and Y0, such that:

VBob(X0)>VAlice(X0)
VBob(Y0)<VAlice(Y0)

Let Alice and Bob divide the remainder C \ X0 \ Y0 between them in a proportional manner (e.g. using divide and choose). Add Y0 to the piece of Alice and add X0 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.

Woodall's protocol for n partners

edit

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

Suppose we already have a strongly 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 strongly 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 strongly proportional, we know that d>0.

Choose a positive integer q such that:  

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

Partner #1 remains with a value of   of his previous value, which was   (by definition of d). The first element becomes   and the d becomes  ; summing them up gives that the new value is more than:   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:   of the entire cake.

This proves that the new division is strongly proportional too.

Barbanel's protocol

edit

Julius Barbanel[1] extended Woodall's algorithm to agents with different entitlements, including irrational entitlements. In this setting, the entitlement of each agent i is represented by a weight  , with  . A strongly proportional allocation is one in which, for each agent i:

 .

Janko-Joo protocol

edit

Janko and Joo[4] presented a simpler algorithm for agents with different entitlements. In fact, they showed how to reduce a problem of strongly proportional division (with equal or different entitlements) into two problems of proportional division with different entitlements:

  • For the piece X, change the entitlement of Alice to   and the entitlement of Bob to  . Since bx > ax, the sum of the new entitlements is strictly less than  , so the sum of all n entitlements (dentoed by WX) is strictly less than W.
  • For the piece Y, change the entitlement of Alice to   and the entitlement of Bob to  . Here, too, since by < ay, the new sum of all entitlements (dentoed by WY) is strictly less than W.
  • Alice's value is at least  
  • Similarly, Bob's value is at least 
  • The value of every other agent i is at least So the division is strongly proportional.
edit

An allocation is called strongly envy-free if for every two partners i,j:

 .

An allocation is called super envy-free if for every two partners i,j:

 .

Super envy-freeness implies strong envy-freeness, which implies strong proportionality.[5]

References

edit
  1. ^ a b Barbanel, Julius (1996). "Game-theoretic algorithms for fair and strongly fair cake division with entitlements". Colloquium Mathematicum. 1 (69): 59–73. doi:10.4064/cm-69-1-59-73. ISSN 0010-1354.
  2. ^ Steinhaus, Hugo (1948). "The problem of fair division". Econometrica. 16 (1): 101–4. JSTOR 1914289.
  3. ^ Woodall, D. R. (1986). "A note on the cake-division problem". Journal of Combinatorial Theory, Series A. 42 (2): 300–301. doi:10.1016/0097-3165(86)90101-9.
  4. ^ Jankó, Zsuzsanna; Joó, Attila (2022-03-11). "Cutting a Cake for Infinitely Many Guests". The Electronic Journal of Combinatorics. 29: P1.42. arXiv:2109.05269. doi:10.37236/10897. ISSN 1077-8926.
  5. ^ Barbanel, Julius B. (1996-01-01). "Super Envy-Free Cake Division and Independence of Measures". Journal of Mathematical Analysis and Applications. 197 (1): 54–60. doi:10.1006/S0022-247X(96)90006-2. ISSN 0022-247X.