Several common variants and special cases are known by different terms: When both n and k are finite, Consensus divisions always exist.
[1]: 127 Some special cases are: It is easy to prove the existence of an exact division when the agents have piecewise-constant valuations.
[4] An exact division exists in the more general setting in which agents have countably-additive nonatomic measures.
This is a corollary of the Dubins–Spanier convexity theorem (the existence of a consensus 1/k-division was previously noted by Jerzy Neyman[5]).
This raises the question of whether there always exists a consensus division with this exact number of cuts.
It can also be proved using the Borsuk-Ulam theorem:[8] Although the agents' preferences are modeled with measures, the proofs do not require the value functions to be positive or additive over subsets; they may be any continuous set functions defined on the Borel sigma-algebra.
Noga Alon, in his 1987 paper about the necklace splitting problem, proved the following result.
Stromquist and Woodall[9] proved that there exists an exact division of a pie (a circular cake) in which each piece contains at most n-1 intervals; hence, at most 2n-2 cuts are needed.
This theorem can be applied recursively to obtain an exact division for any k>1 and any weights, using O(n k) cuts.
[11] It is impossible to compute an exact division with a finite number of queries, even when there are only n=2 agents and k=2 pieces the weights equal 1/2.
We are going to prove that, for every k, there are situations in which at step k there is no exact subset, and hence the protocol might have to continue endlessly.
Without loss of generality, we may assume that each piece has a non-zero value to both partners.
Two agents can achieve a consensus division using Austin moving-knife procedure.
The simplest case is when the weights are 1/2, i.e. they want to cut a piece that both of them agree to be half the cake value.
By combining several such pieces, it is possible to achieve a consensus division with any ratios that are rational numbers.
A better way to achieve a consensus division is to identify the two endpoints of the cake and treat it like a circle.
One agent moves the knives cyclically around the cake, always keeping the value between them at exactly p. It is possible to prove that at some point, the value of the piece between the knives to the other partner will also be exactly p.[12] The other agent calls "stop!"
By repeatedly applying the above procedure, it is possible to achieve a consensus division among n=2 partners and any k>1 subsets.
Here is an intuitive explanation of the packing step for two partners (Alice and George) when the weights are 1/2.
[15] Most results for bounded number of cuts focus on the case in which the weights are equal.
An ε-approximate consensus halving can be computed by an algorithm based on Tucker's lemma, which is the discrete version of Borsuk-Ulam theorem.
[2] An adaptation of this algorithm shows that the problem is in the complexity class PPA.
Hardness holds even with the following additional conditions:[16] Next, assume that ε is a constant (does not depend on n).
Hardness holds even in the following conditions: When ε is a constant, two types of approximations can be computed in polynomial time.
What is currently known is: Two types of approximations can be computed using polynomial number of Robertson-Webb queries:[3] Open whether PPA-hard.
However, it is not necessarily Pareto efficient, since in many cases it is possible to take advantage of the subjective valuations and divide the resources such that all partners receive more than their fair share of
A natural fairness criterion in this setting is unanimous proportionality, which means that all members in all families value their family's share at least 1/k (for other criteria and related problems, see fair division among groups).
If the partners know how the algorithm works, they may have an incentive to lie about their value measures in order to receive more than their weight.
[4][26] The simplest truthful division mechanism is: select a single partner at random (with probabilities determined by the weights) and give him the entire cake.
A better truthful mechanism, which works for the case in which all weights are 1/n, can be built given any existing algorithm (or oracle) for finding a consensus division: Here, the expected value of each partner is still 1/n regardless of the reported value function, so the mechanism is still truthful – no partner can gain anything from lying.