Proportional cake-cutting with different entitlements

In the fair cake-cutting problem, the partners often have different entitlements. For example, the resource may belong to two shareholders such that Alice holds 8/13 and George holds 5/13. This leads to the criterion of weighted proportionality (WPR): there are several weights $w_{i}$ that sum up to 1, and every partner $i$ should receive at least a fraction $w_{i}$ of the resource by their own valuation.

In contrast, in the simpler proportional cake-cutting setting, the weights are equal: $w_{i}=1/n$ for all $i$

Several algorithms can be used to find a WPR division.

Cloning

Suppose all the weights are rational numbers, with common denominator $q$ . So the weights are $p_{1}/q,\dots ,p_{n}/q$ , with $p_{1}+\cdots +p_{n}=q$ . For each player $i$ , create $p_{i}$ clones with the same value-measure. The total number of clones is $q$ . Find a proportional cake allocation among them. Finally, give each partner $i$ the pieces of his $p_{i}$ clones.

If there are only two partners, then the above procedure can be simplified:^[1]^:36 let Alice cut the cake to $q$ pieces equal in her eyes; let George select the $p_{G}$ most valuable pieces in his eyes, and let Alice take the remaining $p_{A}$ pieces.

This simple reduction requires a large number of cuts - $q-1$ cuts. For example, if Alice is entitled to 8/13 and George is entitled to 5/13, then 13-1=12 cuts are needed in the initial partition.

Ramsey partitions

Suppose a cake has to be divided among Alice and George, Alice is entitled to 8/13 and George is entitled to 5/13. The cake can be divided as follows.

Alice cuts the cake to 6 pieces with valuation-ratios 5:3:2:1:1:1.
George marks the pieces that have for him at least the value mentioned by Alice.

Now there are two "good" cases - cases in which we can use these pieces to attain a weighted-proportional division respecting the different entitlements:

Case 1: There is a subset of the marked pieces whose sum is 5. E.g., if George marks the 3-piece and the three 1-pieces. Then, this subset is given to George and the remainder is given to Alice. George now has at least 5/13 and Alice has exactly 8/13.

Case 2: There is a subset of the unmarked pieces whose sum is 8. E.g., if George marks the 3-piece and only one 1-piece. Then, this subset is given to Alice and the remainder is given to George. Alice now has exactly 8 and George has given up a sum of less than 8, so he has at least 5/13.

It is possible to prove that the good cases are the only possible cases. I.e, every subset of 5:3:2:1:1:1, EITHER has a subset that sums to 5, OR its complement has a subset that sums to 8. Hence, the above algorithm always finds a WPR allocation with the given ratios. The number of cuts used is only 5.

This example can be generalized using the concept of Ramsey partitions (named after the Ramsey theory).^[1]^:36–41 ^[2]

Formally: if $k_{1}$ and $k_{2}$ are positive integers, a partition $P$ of $k_{1}+k_{2}$ is called a Ramsey partition for the pair $k_{1},k_{2}$ , if for any sub-list $L\subseteq P$ , either there is a sublist of $L$ which sums to $k_{1}$ , or there is a sublist of $P\setminus L$ which sums to $k_{2}$ .

In the example above, $k_{1}=8$ and $k_{2}=5$ and the partition is 5:3:2:1:1:1, which is a Ramsey partition. Moreover, this is the shortest Ramsey partition in this case, so it allows us to use a small number of cuts.

Ramsey partitions always exist. Moreover, there is always a unique shortest Ramsey partition. It can be found using a simple variant of the Euclidean algorithm. The algorithm is based on the following lemma:^[1]^:143–144

p_{1}<a<b

, and

P=(p_{1},\dots ,p_{n})

is a partition of

b

, and

P'=(b,p_{1},\dots ,p_{n})

, then

P'

is a partition of

a+b

. Moreover,

P'

is a minimal Ramsey partition for the pair

a,b

if-and-only-if

P

is a minimal Ramsey partition for the pair

a,b-a

This lemma leads to the following recursive algorithm.

$FindMinimalRamsey(a,b)$ :

Order the inputs such that $a<b$ .
Push $a$ .
If $a=b-a=1$ , then push $1,1,1$ and finish.
If $b-a\neq 1$ , then $FindMinimalRamsey(a,b-a)$ .

Once a minimal Ramsey partition is found, it can be used to find a WPR division respecting the entitlements.

The algorithm needs at least $\log _{\phi }\min(a,b)$ cuts, where $\phi =(1+{\sqrt {5}})/2$ is the golden ratio. In most cases, this number is better than making $a+b-1$ cuts. But if $a=1$ , then $b=a+b-1$ cuts are needed, since the only Ramsey partition of the pair $b,1$ is a sequence with $b+1$ ones.

Cut-near-halves

Suppose again that Alice is entitled to 8/13 and George is entitled to 5/13. The cake can be divided as follows.

George cuts the cake to two pieces in ratios 7:6.
Alice chooses one of the pieces, which is worth for her at least its declared value. Consider two cases:
- Alice chooses the 7. Then, Alice is entitled to 1 more, and the remaining piece should be divided in ratio 5:1.
- Alice chooses the 6. Then, Alice is entitled to 2 more, and the remaining piece should be divided in ratio 5:2.
In both cases, the remaining piece is smaller and the ratio is smaller. Eventually, the ratio becomes 1:1 and the remaining cake can be divided using cut and choose.

The general idea is similar to the Even-Paz protocol:^[1]^:42–44 $CutNearHalves(a,b)$ :

Order the inputs such that $a<b$ . Suppose Alice is entitled to $b/(a+b)$ and George is entitled to $a/(a+b)$ .
Ask George to cut the cake to near-halves, i.e.:
- if $a+b$ is even then George cuts the cake to two pieces equal in his eyes;
- if $a+b$ is odd then George cuts the cake to two pieces whose valuation-ratio is $(a+b-1)/2:(a+b+1)/2$ in his eyes.
At least one of the pieces is worth for Alice at least the value declared by George; give this piece to Alice.
Suppose the piece taken by Alice is the piece with value $c/(a+b)$ , where $c\in \{(a+b-1)/2,(a+b)/2,(a+b+1)/2)$ . Call $CutNearHalves(b,a-c)$ .

The cut-near-halves algorithm needs at most $\log _{2}\min(a,b)$ cuts, so it is always more efficient than the Ramsey-partitions algorithm.

The cut-near-halves algorithm is not always optimal. For example, suppose the ratio is 7:3.

Cut-near-halves may need at least four cuts: first, George cuts in the ratio 5:5, and Alice gets 5. Then, Alice cuts in the ratio 3:2; suppose George chooses the 2. Then, George cuts in the ratio 2:1; suppose Alice chooses the 1. Finally, they do cut-and-choose on the remainder.
We can do better by letting George cut in the ratio 6:4. If Alice chooses the 4, then the ratio becomes 3:3 and we can use cut-and-choose immediately. If Alice chooses the 6, then the ratio becomes 3:1. Alice cuts in ratio 2:2, George chooses the 2, and we need one more step of cut-and-choose. All in all, at most three cuts are needed.

It is an open question how to find the best initial cut for each entitlement ratio.

Exact divisions

A special case of a WPR division is an exact division, in which the value of piece i is exactly w_i according to all partners. Since an exact division exists for every set of weights, a WPR division is also guaranteed to exist for every set of weights. However, it may require a large number of cuts.

The Stromquist-Woodall theorem implies that dividing the cake to two exact subsets requires $2(n-1)$ cuts. By applying this theorem recursively, it is possible to get a WPR division using $2(n-1)\lceil \log _{2}(n)\rceil$ cuts.

Impossibility result

The above division algorithms do not preserve the geometric properties of the proportional algorithms. I.e., if the original division algorithm guarantees that each partner receives a contiguous piece, this is no longer guaranteed when using cloned players.

If the pieces must be connected, then a WPR division might not exist. Here is an example.^[3] A cake made of four consecutive parts has to be divided between Alice and George, whose valuations are as follows:

Alice's value	2	2	2	2
George's value	1	3	3	1

Note that the total cake value is 8 for both partners. If $w_{A}\geq 0.75$ , then Alice is entitled to a value of at least 6. To give Alice her due share in a connected piece, we must give her either the three leftmost slices or the three rightmost slices. In both cases George receives a piece with a value of only 1, which is less than his due share of 2. To achieve a WPR division in this case, we must give George his due share in the center of the cake, where his value is relatively large, but then Alice will get two disconnected pieces.^[4]

Interestingly, if the cake is circular (i.e. the two endpoints are identified) then a WPR division for two people is always possible; see fair pie-cutting#Weighted proportional division.

References

1 2 3 4 Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. ISBN 1-568-81076-8.
↑ McAvaney, Kevin; Robertson, Jack; Webb, William (1992). "Ramsey partitions of integers and pair divisions". Combinatorica. 12 (2): 193. doi:10.1007/bf01204722.
↑ Brams, S. J.; Jones, M. A.; Klamler, C. (2007). "Proportional pie-cutting". International Journal of Game Theory. 36 (3–4): 353. doi:10.1007/s00182-007-0108-z.
↑ Note that there exists a connected division in which the ratios between the values of the partners are 3:1 – give Alice the two leftmost slices and 8/11 of the third slice (value 4+16/11=60/11) and give George the remaining 3/11 and the rightmost slice (value 1+9/11=20/11). However, this partition is not WPR since no partner receives his due share.

This article is issued from Wikipedia - version of the 7/25/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.