It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that his allocated share is worth at least 1/n of the total.
[1] Fink protocol is an algorithm that continues the division to successively smaller "equal" portions.
Lone divider is a procedure based on an equal partition made by a single agent.
See also: [2] Using a divide-and-conquer strategy, it is possible to achieve a proportional division in time O(n log n).
Thanks to the divide-and-choose strategy, the number of iterations is only O(log n), in contrast to O(n) in the Last Diminisher procedure.
Use the following protocol: The selection rule in step #2 guarantees that, at each iteration, at most one interval of every partner is removed.
We can still cut a cake using O(n) queries if we make several compromises: The general scheme is as follows:[5] The algorithm guarantees that, with probability O(1a2), each partner receives at least half of one of his candidate pieces, which implies (if the values are additive) a value of at least 1/2an.
There are O(n) candidate pieces and O(n) additional divisions in step #5, each of which takes O(1) time.
The main challenge in this scheme is selecting the final pieces in step #4.
Every deterministic proportional division procedure for n≥3 partners must use at least n queries, even if all valuations are identical.
[3] Moreover, every deterministic or randomized proportional division procedure assigning each person a contiguous piece must use Ω(n log n) actions.
The proof is based on lower bounding the complexity to find, for a single player, a piece of cake that is both rich in value, and thin in width.
[7] These hardness results imply that recursive halving is the fastest possible algorithm for achieving full proportionality with contiguous pieces, and it is the fastest possible deterministic algorithm for achieving even partial proportionality and even with disconnected pieces.
The only case in which it can be improved is with randomized algorithms guaranteeing partial proportionality with disconnected pieces.
If the players are able to cut with only finite precision, then the Ω(n log n) lower bound also includes randomized protocols.
The proportionality criterion can be generalized to situations in which the entitlements of the partners are not equal.
So a necessary condition for the existence of a super-proportional division is that not all partners have the same value measure.
The surprising fact is that, when the valuations are additive and non-atomic, this condition is also sufficient.
A proportional division with this property always exists and can be found by combining the Last Diminisher protocol with geometric tricks involving conformal mappings.
When the "cake" to be divided is two-dimensional, such as a land-estate or an advertisement space in print or electronic media, it is often required that the pieces satisfy some geometric constraints, in addition to connectivity.
[8] In addition to being proportional, it is often required that the division be economically efficient, i.e., maximize the social welfare (defined as the sum of the utilities of all agents).
This division is proportional because each partner receives 0.5 of his total value so the normalized social welfare is 1.
This problem currently has a solution only for the very special case where the cake is a 1-dimensional interval and the utility density functions are linear (i.e. u(x) = Ax + B).
When the utility functions are not normalized (i.e. we allow each partner to have a different value for the whole cake), the problem is even NP-hard to approximate within a factor of 1/√n.
Even if all other partners make a coalition with the only intent to harm him, he will still receive his guaranteed proportion.
[10] However, most of the protocols are not strongly truthful in that some partners may have an incentive to lie in order to receive even more than the guaranteed share.