Consensus splitting


Consensus splitting, also called exact division, is a partition of a continuous resource into some k pieces, such that each of n people with different tastes agree on the value of each of the pieces. For example, consider a cake which is half chocolate and half vanilla. Alice values only the chocolate and George values only the vanilla. The cake is divided into three pieces: one piece contains 20% of the chocolate and 20% of the vanilla, the second contains 50% of the chocolate and 50% of the vanilla, and the third contains the rest of the cake. This is an exact division, as both Alice and George value the three pieces as 20%, 50% and 30% respectively. Several common variants and special cases are known by different terms:
  • Consensus halving – the cake should be partitioned into two pieces, and all agents agree that the pieces have equal values.
  • Consensus 1/k-division, for any constant k > 1 – the cake should be partitioned into k pieces, and all agents agree that the pieces have equal values. Another term is consensus splitting.
  • Perfect division – the number of pieces equals the number of agents: the cake should be partitioned into n pieces, and all agents agrees that all pieces have equal values.
  • -near-exact division, for any constant, the agents may disagree on the pieces values, but the difference between the values should be at most. Similarly, the approximate variants of the above-mentioned problems are called -consensus-halving, -consensus 1/k-division or -consensus-splitting, and -perfect-division.
  • Problem of the Nile – there are infinitely many agents.
  • Necklace splitting – the resource to divide is made of a finite number of indivisible objects.
When both n and k are finite, Consensus divisions always exist. However, they cannot be found by discrete protocols. In some cases, exact divisions can be found by moving-knife protocols. Near-exact divisions can be found by discrete protocols.

Definitions

Let be k weights whose sum is 1. Assume there are n agents, all of whom value the cake C as 1. The value measure of agent i is denoted by. It is assumed to be a nonatomic measure on C. An exact division in the ratios is a partition of the cake into k pieces:, such that for every agent i and every piece j:
It is also called a consensus division, since there is a consensus among all agents that the value of piece j is exactly. Some special cases are:
  • Consensus 1/k division – the special case in which.
  • Consensus halving – the special case in which and.
  • Perfect division – the special case in which and.

    Near-exact division

For every, An -near-exact division in the ratios is a division in which:
That is, there is a consensus among all partners that the value of piece j is nearly-exactly, where the difference is less than. Some special cases are:
  • -consensus 1/k division – the special case in which.
  • -consensus halving – the special case in which and.
  • -perfect division – the special case in which and.

    Existence

Unbounded number of cuts

It is easy to prove the existence of an exact division when the agents have piecewise-constant valuations. This means that the cake can be partitioned into R regions, such that all agents agree that the value-density in each region is uniform. For example, consider a circular cake in which each of its 4 quarters has a different topping. The agents may value each of the toppings differently, but do not distinguish between different pieces having the same topping: the value of each piece to each agent only depends on the amount they get from each region. An exact division can be achieved in the following way:
  • Divide each region into k sub-regions, such that sub-region j contains exactly of the regions.
  • Let piece j be the union of the j-th sub-regions in all R regions.
The number of required cuts is, where R is the number of regions. This algorithm can be generalized to piecewise-linear valuations.
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. However, this theorem says nothing about the number of required cuts.
Woodall showed that it is possible to construct an exact division of an interval cake as a countable union of intervals. Intuition: consider the division procedure for piecewise-homogeneous cakes described above. In general, the cake is not piecewise-homogeneous. However, because the value measures are continuous, it is possible to divide the cake to smaller and smaller regions such that the regions become more and more homogeneous. When, this process converges to a consensus division. However, the number of required cuts in the limit is infinite. Fremlin later showed that it is possible to construct such a division as a finite union of intervals.

Bounded number of cuts

Suppose the cake is an interval made of n districts, and each of the n partners values only a single district. Then, a consensus division of the cake into k subsets requires cuts, since each of the districts must be cut into k pieces which are equal in the eyes of the partner that values this district. This raises the question of whether there always exists a consensus division with this exact number of cuts. This question was studied extensively, focusing mainly on a one-dimensional cake.
Consider first the consensus halving case: and equal weights. The lower bound on the number of cuts is . Indeed, a consensus halving with at most n cuts always exists. This is a direct corollary of the Hobby–Rice theorem. It can also be proved using the Borsuk-Ulam theorem:
  • Every partition of an interval using cuts can be represented as a vector of length, in which the elements are the lengths of the sub-intervals.
  • Every element of the vector can be either positive or negative.
  • The set of all partitions is homeomorphic to the sphere.
  • Define a function in the following way: for every partition, is a vector whose -th element is the value of piece #1 in that partition according to partner, minus 1/2.
  • The function is continuous. Moreover, for all,.
  • Hence, by the Borsuk-Ulam theorem, there exists an such that. In that partition, all partners value piece #1 at exactly 1/2.
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. Thus it is not required that partners' valuations over subsets of the cake be additively separable.
Consider now the consensus 1/k-division case: any k>1 and equal weights. Noga Alon, in his 1987 paper about the necklace splitting problem, proved the following result. There are different measures on the interval, all absolutely continuous with respect to length. The measure of the entire necklace, according to measure, is. Then it is possible to partition the interval into parts, such that the measure of each part, according to measure, is exactly. At most cuts are needed, and this is optimal.
Consider now the case k=2 and arbitrary weights. Stromquist and Woodall proved that there exists an exact division of a pie in which each piece contains at most n-1 intervals; hence, at most 2n-2 cuts are needed. See Stromquist–Woodall theorem. The number of cuts is essentially optimal for general weights. This theorem can be applied recursively to obtain an exact division for any k>1 and any weights, using O cuts.

Multi-dimensional cake, many partners, many subsets, equal weights

The Stone–Tukey theorem states that given measurable "objects" in -dimensional space, it is possible to divide all of them in half with a single -dimensional hyperplane.
Stated differently: if the cake is the space, and the value measures of the partners are finite and vanish on any dimensional hyperplane, then there is a half-space whose value is exactly 1/2 to each partner. Hence there exists a consensus division using a single cut.
The original version of this theorem works only if the number of dimensions of the cake is equal to the number of partners. E.g, it is not possible to use this theorem to divide a 3-dimensional sandwich to 4 or more partners.
However, there are generalizations that enable such a division. They do not use a hyperplane knife but rather a more complicated polynomial surface.
There are also discrete adaptations of these multi-dimensional results.

Computation of exact divisions

Impossibility using discrete procedures

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. This means that the best we can achieve using a discrete algorithm is a near-exact division.
Proof: When the protocol is at step k, it has a collection of at most k pieces. To provide an exact division, the protocol must find an exact subset – a subset of the pieces which both partners value as exactly 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.
Initially, there is only one piece which both partners value as 1, so there is obviously no exact subset. After one step, at most one partner has had an option to cut the cake. Even if Alice cuts the cake to two pieces that are equal in her opinion, they may be different in George's opinion, so again there is no exact subset.
Suppose now that we are at step k and there are k pieces. Without loss of generality, we may assume that each piece has a non-zero value to both partners. This is because, if Alice cuts a piece which she values as 0, it is possible that George also values the same piece as 0, so we can discard this piece and continue with the other pieces.
The total number of different subsets now is 2k, and by the induction assumption none of them is exact. At step k, the protocol can ask either Alice or George to cut a certain piece to two pieces. Suppose w.l.o.g. that the cutter is George and that he cuts piece X to two sub-pieces: X1 and X2. Now, the total number of subsets is 2k+1: half of them already existed and by assumption they are not exact, so the protocol's only chance of finding an exact subset is to look at the new subsets. Each new subset is made of an old subset in which the piece X has been replaced with either X1 or X2. Since George is the cutter, he can cut in a way which makes one of these subsets an exact subset for him. But, George does not know Alice's valuation and cannot take it into account when cutting. Therefore, there is an uncountable infinity of different values that the pieces X1 and X2 can have for Alice. Since the number of new subsets is finite, there is an infinite number of cases in which no new subset has a value of 1/2 for Alice, hence no new subset is exact.