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 formula_1 that sum up to 1, and every partner formula_2 should receive at least a fraction formula_1 of the resource by their own valuation. In contrast, in the simpler proportional cake-cutting setting, the weights are equal: formula_4 for all formula_2 Several algorithms can be used to find a WPR division . Cloning. Suppose all the weights are rational numbers, with common denominator formula_6. So the weights are formula_7, with formula_8. For each player formula_2, create formula_10 clones with the same value-measure. The total number of clones is formula_6. Find a proportional cake allocation among them. Finally, give each partner formula_2 the pieces of his formula_10 clones. Robertson and Webb show a simpler procedure for two partners: Alice cuts the cake into formula_6 pieces equal in her eyes; George selects the formula_15 most valuable pieces in his eyes, and Alice takes the remaining formula_16 pieces. This simple procedure requires formula_17 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 formula_18 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. 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 formula_19 and formula_20 are positive integers, a partition formula_21 of formula_22 is called a "Ramsey partition" for the  pair formula_23, if for any sub-list formula_24, either there is a sublist of formula_25 which sums to formula_19, or there is a sublist of formula_27 which sums to formula_20. In the example above, formula_29 and formula_30 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: This lemma leads to the following recursive algorithm. formula_40: Once a minimal Ramsey partition is found, it can be used to find a WPR division respecting the entitlements. The algorithm needs at least formula_46 cuts, where formula_47 is the golden ratio. In most cases, this number is better than making formula_48 cuts. But if formula_49, then formula_50 cuts are needed, since the only Ramsey partition of the pair formula_51 is a sequence with formula_52 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 . The general idea is similar to the Even-Paz protocol: formula_53: The cut-near-halves algorithm needs at most formula_62 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. It is an open question how to find the best initial cut for each entitlement ratio. The algorithm can be generalized to "n" agents; the number of required queries is formula_63 Cseh and Fleiner presented an algorithm for dividing a multi-dimensional cake among any number of agents with any entitlements (including  irrational entitlements), in a finite number of queries. Their algorithm requires formula_64 queries in the Robertson–Webb query model; thus it is more efficient than agent-cloning and cut-near-halves. They prove that this runtime complexity is optimal. Algorithms for irrational entitlements. When the entitlements are not rational numbers, methods based on cloning cannot be used since the denominator is infinite. Shishido and Zeng presented an algorithm called "mark-cut-choose", that can also handle irrational entitlements, but with an unbounded number of cuts. The algorithm of Cseh and Fleiner can also be adapted to work with irrational  entitlements in a finite number of queries. Number of required cuts. Besides the number of required queries, it is also interesting to minimize the number of required cuts, so that the division is not too much fractioned. The Shishido-Zeng algorithms yield a fair division with at most formula_65cuts, and a strongly-fair division with at most formula_66cuts. In the worst case, at least formula_67 cuts might be required. Brams, Jones and Klamler show an example for "n"=2. A cake made of four consecutive regions has to be divided between Alice and George, whose valuations are as follows: Note that  the total cake value is 8 for both partners. If formula_68, 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. Segal-Halevi shows that, if the cake is circular (i.e. the two endpoints are identified) then a connected WPR division for two people is always possible; this follows from the Stromquist–Woodall theorem. By recursively applying this theorem to find exact divisions, it is possible to get a WPR division using at most formula_69 cuts when "n" is a power of 2, and a similar number when "n" is general. Crew, Narayanan and Spirkle improved this upper bound to 3"n"-4 using the following protocol: The exact number of required cuts remains an open question. The simplest open  case is when there are 3 agents and the weights are 1/7, 2/7, 4/7. It is not known if the number of required cuts is 4 (as in the lower bound) or 5 (as in the upper bound). See also. Zeng presented an algorithm for approximate envy-free cake-cutting with different entitlements. Dall'Aglio and MacCheroni proved the existence of proportional cake-cutting with different entitlements even when agents' preferences are described by non-additive preference relations, as long as they satisfy certain axioms.