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 that sum up to 1, and every partner should receive at least a fraction of the resource by their own valuation. In contrast, in the simpler proportional cake-cutting setting, the weights are equal: for all Several algorithms can be used to find a WPR division. Cloning Suppose all the weights are rational numbers, with common denominator . So the weights are , with . For each player , create clones with the same value-measure. The total number of clones is . Find a proportional cake allocation among them. Finally, give each partner the pieces of his clones. Robertson and Webb show a simpler procedure for two partners: Alice cuts the cake into pieces equal in her eyes; George selects the most valuable pieces in his eyes, and Alice takes the remaining pieces. This simple procedure requires cuts, which may be very large. 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. The number of required queries is 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. McAvaney, Robertson and Webb generalize this idea using the concept of Ramsey partitions (named after the Ramsey theory). Formally: if and are positive integers, a partition of is called a Ramsey partition for the pair , if for any sub-list