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 {\displaystyle w_{i}} that sum up to 1, and every partner i {\displaystyle i} should receive at least a fraction w i {\displaystyle 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 {\displaystyle w_{i}=1/n} for all i {\displaystyle i}
Several algorithms can be used to find a WPR division.
Cloning Suppose all the weights are rational numbers, with common denominator D {\displaystyle D} . So the weights are p 1 / D , … , p n / D {\displaystyle p_{1}/D,\dots ,p_{n}/D} , with p 1 + ⋯ + p n = D {\displaystyle p_{1}+\cdots +p_{n}=D} . For each player i {\displaystyle i} , create p i {\displaystyle p_{i}} clones with the same value-measure. The total number of clones is D {\displaystyle D} . Find a proportional cake allocation among them. Finally, give each partner i {\displaystyle i} the pieces of his p i {\displaystyle p_{i}} clones. Robertson and Webb show a simpler procedure for two partners: Alice cuts the cake into D {\displaystyle D} pieces equal in her eyes; George selects the p G {\displaystyle p_{G}} most valuable pieces in his eyes, and Alice takes the remaining p A {\displaystyle p_{A}} pieces. (This is an application of the Divide and choose procedure.) This simple procedure requires D pieces so D − 1 {\displaystyle D-1} cuts, which may be very many. 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 D ⌈ log 2 ( D ) ⌉ . {\displaystyle D\lceil \log _{2}(D)\rceil .}
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.
… excerpt ends here. Continue reading the full article.
