In the fair cake-cutting problem, the partners often have different entitlements.
In contrast, in the simpler proportional cake-cutting setting, the weights are equal:
Suppose all the weights are rational numbers, with common denominator
Robertson and Webb[1]: 36 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
Now there are two "good" cases - cases in which we can use these pieces to attain a weighted-proportional division respecting the different entitlements: Thre are several combinations of the pieces that give each their due share.
Hence, the above algorithm always finds a WPR allocation with the given ratios.
(The five cuts make six pieces that form up multiple proportionally-sized combinations that give each their share, so the "divide and choose" procedure can be used flexibly.)
Moreover, this is the shortest Ramsey partition in this case, so it allows us to use a small number of cuts.
It can be found using a simple variant of the Euclidean algorithm.
: Once a minimal Ramsey partition is found, it can be used to find a WPR division respecting the entitlements.
cuts are needed, since the only Ramsey partition of the pair
The general idea is similar to the Even-Paz protocol:[1]: 42–44
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
Cseh and Fleiner[3] 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.
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.
[4] The algorithm of Cseh and Fleiner can also be adapted to work with irrational entitlements in a finite number of queries.
The Shishido-Zeng algorithms yield a fair division with at most
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.
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.
[7] Segal-Halevi[8] 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.
cuts when n is a power of 2, and a similar number when n is general.
Crew, Narayanan and Spirkle[9] improved this upper bound to 3n-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.
Zeng[10] presented an algorithm for approximate envy-free cake-cutting with different entitlements.
Dall'Aglio and MacCheroni[11]: Thm.3 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.