Exact division

From Wikipedia, the free encyclopedia
Jump to: navigation, search

An exact division (also called: even division or consensus division) is a division of a heterogeneous resource ("cake") to several subsets such that each of n people with different tastes agree about the valuations of the pieces.[1]

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 to 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 a consensus division, as both Alice and George value the three pieces as 20%, 50% and 10% respectively.

As the example illustrates, a consensus division is not necessarily fair. For example, if the 20% piece is given to Alice and the 50% is given to George, this is obviously unfair to Alice. In the theory of cake, consensus divisions are often used as subroutines for creating fair divisions.

Consensus divisions always exist, but they cannot be found by discrete protocols (with a finite number of queries). In some cases, exact divisions can be found by moving-knife protocols. Near-exact divisions can be found by discrete protocols.


Let w_1, w_2, ..., w_k be k weights whose sum is 1. Assume that all n partners value the cake C as 1.

An exact division (aka consensus division) in the ratios w_1, w_2, ..., w_k is a partition of the cake to k pieces: C = X_1 \sqcup ... \sqcup X_k, such that for every partner i and every piece j:


I.e., there is a consensus among all partners that the value of piece j is exactly w_j.[1]

Near-exact division[edit]

For every \epsilon>0, An \epsilon-near-exact division in the ratios w_1, w_2, ..., w_k is a division in which:

|V_i(X_j)-w_j| < \epsilon

I.e., there is a consensus among all partners that the value of piece j is nearly-exactly w_j, where the difference is less than \epsilon.[1]

Exact division with arbitrary number of cuts[edit]

Piecewise-homogeneous cake, many partners, any weights[edit]

A cake is called piecewise-homogeneous if it can be divided to R regions, such that all partners 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 partners may value each of the toppings differently, but do not distinguish between different pieces having the same topping. This means that the value of each piece to each partner only depends on the amount they get from each region.

Saying that the cake is piecewise-homogeneous is equivalent to saying that the valuations of the partners are piecewise-constant: each piece of the cake is homogeneous if and only if it is the intersection of n pieces of the n partners.

whenever the cake is piecewise-homogeneous (and the valuations are piecewise-constant), a consensus division can be achieved in the following way:

  • Divide each region to k sub-regions, such that sub-region j contains exactly w_j of the regions.
  • Let piece j be the union of the j-th sub-regions in all R regions. This defines a consensus division with the given weights.

This algorithm can be generalized to slightly more general families of value measures, such as piecewise linear.[2]

The number of required cuts is k R, where R is the number of regions.

General cake, many partners, any weights[edit]

When the value functions are additive and non-atomic, a consensus division exists for every set of weights.

Dubins and Spanier proved the existence of such a division based on Lyapunov vector-measure theorem:[3][4]

  • Every partition of the cake to k pieces defines an n\times k matrix, in which element (i,j) is the valuation of partner i to piece j.
  • For every j, the partition in which piece j is the entire cake corresponds to a matrix in which the j-th column is all 1's and the other columns are all 0's. Call this matrix M_j.
  • The space of all partition matrices is convex.[4] (see Lyapunov vector-measure theorem).
  • Hence, for every set of weights, the space of all partition matrices contains the convex combination of the M_j matrices with the given weights.
  • Hence, there is a partition in which, for every j, the j-th column contains only the weight w_j. This partition is a consensus division with the given weights.

Woodall[5] showed that it is possible to construct such a 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 R\to \infty, this process converges to a consensus division.

Fremlin showed that it is possible to construct such a division as a finite union of intervals.

Stromquist and Woodall[6] showed that it is possible with the minimal number of intervals; see below.

Exact division with a minimal number of cuts[edit]

Suppose the cake is an interval made of n districts (sub-intervals), and each of the n partners values only a single district. Then, a consensus division of the cake to k subsets requires n\cdot (k-1) cuts, since each of the districts must be cut to k pieces which are equal in the eyes of the partner that values this district. Hence, it is an interesting question whether it is always possible to attain a consensus division with this exact number of cuts.

Interval cake, two partners, many subsets, any weights[edit]

Two partners 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. This is done as follows. One partner moves two knives over the cake from left to right, always keeping the value between the knives as exactly 1/2. It is possible to prove (by the intermediate value theorem) that at some point, the value of the piece between the knives to the other partner will also be exactly 1/2. The other partner calls "stop!" at that point and the piece is cut.

The same protocol can be used to cut a piece that both player agree that its value is exactly 1/n.

By combining several such pieces, it is possible to achieve a consensus division with any ratios that are rational numbers. But this may require a large number of cuts.

A better way to achieve a consensus division is to identify the two endpoints of the cake and treat it like a circle. I.e, when the right knife gets to the right side, it immediately goes to the left side, and the piece-between-the-knives is now actually the union of the piece to the right of the right knife and the piece to the left of the left knife. This way, it is possible to find a consensus division for every p\in[0,1]. One partner 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.[7] The other partner calls "stop!" at that point and the piece is cut. This requires only two cuts.

By repeatedly applying the above procedure, it is possible to achieve a consensus division to two partners and any number of subsets. The number of cuts is 2(k-1), where k is the number of subsets.

As of 2015, there is no known generalization of this moving-knife procedure to more than 2 partners. [8]

Interval cake, many partners, two subsets, equal weights[edit]

Suppose the cake is an interval of value 1. It should be divided to k=2 subsets, each of which has a value of exactly 1/2 to all n partners. We want to use the minimal number of cuts, which is n(k-1)=n.

A division like this always exists.[9] This is a direct corollary of the Hobby–Rice theorem. This can also be proved based on the Borsuk-Ulam theorem:[10]

  • Every partition of an interval using n cuts can be represented as a vector of length n+1, in which the elements are the lengths of the sub-intervals.
  • Every element of the vector can be either positive (if it belongs to piece #1) or negative (if it belongs to piece #2).
  • The set of all partitions is the sphere S^n.
  • Define a V: S^n \to \mathbb{R}^n in the following way: for every partition x, V(x) is a vector whose i-th element is the value of piece #1 in that partition according to partner i, minus 1/2.
  • The function V is continuous. Moreover, for all x, V(x)+V(-x)=0.
  • Hence, by the Borsuk-Ulam theorem, there exists an x such that V(x)=0. In that partition, all partners value piece #1 (and piece #2) as exactly 1/2.

A consensus division to two subsets can be found based on Tucker's lemma, which is the discrete version of Borsuk-Ulam theorem.[11]

Although the partners' preferences are modeled with measures, the proofs do not require the value measures to be additive over subsets. The value measures may as well be continuous set functions defined on the Borel sigma-algebra and satisfying all the properties of measures except countable additivity. Thus it is not required that partners' valuations over subsets of the cake be additively separable.[11]

Interval cake, many partners, many subsets, equal weights[edit]

The existence theorem of the previous subsection can be generalized from k=2 pieces to an arbitrary number of pieces. This was proved by Noga Alon in his 1987 paper about the necklace splitting problem.

Interval cake, many partners, two subsets, arbitrary weights[edit]

The existence theorem of the previous subsection can be generalized to arbitrary weights.[6] The proof is based on the Stone–Tukey theorem.

The proof is easier if we assume that the cake is a circle. Specifically, we define the cake C as the interval [0,1] in which the two endpoints are identified. Then, for every weight w \in [0,1], there is a subset C_w, which is a union of n-1 intervals, which all partners value as exactly w:

\forall i = 1,\cdots,n: \,\,\,\,\,  u_i(C_w)=w

PROOF SKETCH: Let W \subseteq [0,1] be the subset of all weights for which the theorem is true. Then:

  1. 1 \in W. Proof: take C_1 := C (recall that the value measures are normalized such that all partners value the entire cake as 1).
  2. If w\in W, then also 1-w \in W. Proof: take C_{1-w} := C\setminus C_w. If C_w is a union of n-1 intervals in a circle, then C_{1-w} is also a union of n-1 intervals.
  3. W is a closed set. This is easy to prove, since the space of unions of n-1 intervals is a compact set under a suitable topology.
  4. If w\in W, then also w/2 \in W. This is the most interesting part of the proof; see below.

From 1-4, it follows that W=[0,1]. In other words, the theorem is valid for every possible weight.


  • Assume that C_w is a union of n-1 intervals and that all n partners value it as exactly w.
  • Define the following function on the cake, f: C \to \mathbb{R}^n:
f(t) = (t, t^2, ..., t^n)\,\,\,\,\,\,t\in[0,1]
  • Define the following measures on \mathbb{R}^n:
v_i(U) = u_i(f^{-1}(U) \cap C_w)\,\,\,\,\,\,\,\,\, U\subseteq \mathbb{R}^n
  • Note that f^{-1}(\mathbb{R}^n) = C. Hence, for every partner i: v_i(\mathbb{R}^n) = w.
  • Hence, by the Stone-Tukey theorem, there is a hyper-plane that cuts \mathbb{R}^n

to two half-spaces, H, H', such that:

\forall i = 1,\cdots,n: \,\,\,\,\, v_i(H)=v_i(H')=w/2
  • Define M=f^{-1}(H)\cap C_w and M'=f^{-1}(H')\cap C_w. Then, by the definition of the v_i:
\forall i = 1,\cdots,n: \,\,\,\,\,  u_i(M)=u_i(M')=w/2
  • The set C_w has n-1 connected components (intervals). Hence, its image f(C_w) also has n-1 connected components (1-dimensional curves in \mathbb{R}^n).
  • The hyperplane that forms the boundary between H and H' intersects f(C_w) in at most n points. Hence, the total number of connected components (curves) in H\cap f(C_w) and H'\cap f(C_w) is 2n-1. Hence, one of these must have at most n-1 components.
  • Suppose it is H that has at most n-1 components (curves). Hence, M has at most n-1 components (intervals).
  • Hence, we can take C_{w/2}=M. This proves that w\in W.

Tightness proof[edit]

Stromquist and Woodall prove that the number n-1 is tight if the weight w is either irrational, or rational with a reduced fraction r/s such that s\geq n.


  • Choose (n-1)(n+1) equally-spaced points along the circle; call them P_1,...,P_{(n-1)(n+1)}.
  • Define n-1 measures in the following way. Measure i is concentrated in small neighbourhoods of the following (n+1) points: P_{i},P_{i+(n-1)},...,P_{i+n(n-1)}. So, near each point P_{i+k(n-1)}, there is a fraction 1/(n+1) of the measure u_i.
  • Define the n-th measure as proportional to the length measure.
  • Every subset whose consensus value is 1/n, must touch at least two points for each of the first n-1 measures (since the value near each single point is 1/(n+1) which is slightly less than the required 1/n). Hence, it must touch at least 2(n-1) points.
  • On the other hand, every subset whose consensus value is 1/n, must have total length 1/n (because of the n-th measure). The number of "gaps" between the points is 1/(n+1)(n-1); hence the subset can contain at most n-1 gaps.
  • The consensus subset must touch 2(n-1) points but contain at most n-1 gaps; hence it must contain at least n-1 intervals.

Multi-dimensional cake, many partners, many subsets, equal weights[edit]

The Stone-Tukey theorem states that given n measurable "objects" in n-dimensional space, it is possible to divide all of them in half (with respect to their measure, i.e. volume) with a single (n − 1)-dimensional hyperplane.

Stated differently: if the cake is the space \mathbb{R}^n, and the value measures of the partners are finite and vanish on any n-1 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.[12]

Near-Exact division procedures[edit]

Crumb-and-Pack procedure[edit]

For any given \epsilon > 0, one can give each partner a piece such that all partners believe that the values they have differ by less than \epsilon, i.e., for every i and every j:[1]

|V_i(X_j)-w_j| < \epsilon

The near-exact division procedure has two steps: crumbing and packing.

Crumbing step: the goal is to cut the cake to tiny bits ("crumbs") such that each partner assigns a sufficiently small value to each crumb. This is done in the following way. Let k be a certain constant. Ask partner #1 cut the cake to k pieces that he values as 1/k. Ask partner #2 to trim pieces as needed (using at most k-1 cuts) such that each piece has a value of at most 1/k. These new pieces of course still have a value of at most 1/k for partner #1. Continue with partners #3, #4, ..., #n. Finally all n partners value each resulting crumb as at most 1/k.

Packing step: the goal here is to partition the crumbs to n subsets, such that the sum of values in each subset j is near wj. Here is an intuitive explanation of the packing step for two partners (Alice and George) when the weights are 1/2.[13]

  1. Get an empty bowl.
  2. Insert into the bowl one of the crumbs.
  3. If the value in the bowl becomes more than 1/2 to either partner, give the bowl to that partner and give the other crumbs to the other partner.
  4. Otherwise (the value in the bowl is less than 1/2 to both partners), if the value in the bowl is larger for Alice than for George, then find a crumb whose value for George is more than its value for Alice (such a crumb must exist because the sum of values of all crumbs is 1 both for Alice and for George). Add this crumb to the bowl and return to step 2.

It is possible to prove by induction, that the difference in the valuation of the bowl between Alice and George is always at most 1/k. Hence, when one of the partners receives the bowl, its value for both partners is between than 1/2-1/k and 1/2+1/k.

Formally, each piece can be represented as a vector of values, one per partner. The length of each vector is bounded, i.e. for each such vector v: ||v||\leq \sqrt{n}/k. Our goal is to create, for each partner j, a vector all whose elements are near wj. To do this, we have to divide the vectors to subsets, such that the sum of vectors in each subset j is sufficiently close to a vector all whose elements are wj. This is possible thanks to a theorem by V.Bergström,[14][15]

The Crumb-and-Pack procedure is a subroutine in the Robertson-Webb protocol. The latter protocol generates a division which is both near-exact and envy-free cake-cutting.

A different explanation of the crumb-and-pack procedure is provided by Brams and Taylor.[16]

Truthful mechanisms[edit]

Any algorithm for consensus division relies on the value measures reported by the partners. 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. In order to prevent this, incentive compatible (truthful) mechanisms can be used.[2][17]

The simplest truthful division mechanism is: select a single partner at random (with probabilities determined by the weights) and give him the entire cake. This mechanism is trivially truthful because it asks no questions. Moreover, it is consensus in expectation: the expected value of each partner is exactly its weight, and this is true according to all value measures. However, the resulting division is of course not a consensus division.

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:

  1. Ask each partner to report his value measure.
  2. Use the existing algorithm/oracle to generate a partition in which all n pieces are exactly 1/n according to the value functions reported by the partners.
  3. Perform a random permutation on the consensus partition and give each partner one of the pieces.

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. Moreover, a truthful partner is guaranteed a value of exactly 1/n with probability 1 (not only in expectation). Hence the partners have an incentive to reveal their true value functions.


It is impossible to achieve an exact division with a finite number of queries, even if there are only 2 partners and the weights are exactly 1/2.[18] 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 (say, Alice) 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 (for example) 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 (e.g. if a certain subset containing piece X had a value of 3/4, George can cut X such that X1 has a value of 1/4 in his opinion, so that the new subset has a value of exactly 1/2). 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.

Comparison with other criteria[edit]

An exact division with equal weights (1/n) is, in particular, also proportional, envy-free and equitable.

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 1/n.

Exact divisions are much easier if the participants cooperate in establishing entitlements rather than competing as in fair division. Some authors refer to this as consensus division or consensus halving.[19]

Summary table[edit]

Name Type Cake Valuations[20] #partners (n) #subsets (k) #cuts weights
Austin Moving-knife procedure Interval Con 2 Many 2(k-1) (optimal) Any
Piecewise-homogeneous Discrete procedure Piecewise-homogeneous Con+Add+Pwl Many Many Num. of districts Any
Dubins–Spanier Existence proof Any Con+Add Many Many Unbounded Any
Consensus-halving Infinite procedure Interval Con Many 2 n (optimal) Equal
Necklace-splitting Existence proof Interval Con(+Add?) Many Many n(k-1) (optimal) Equal
Stromquist-Woodall Existence proof Circle Con+Add Many 2 2n-2 (optimal for some weights) Any
Stone–Tukey Existence proof n-dimensional Con(+Add?) n 2 1 half-plane Equal
Crumb-and-pack Near-exact procedure Any Con+Add Many Many Unbounded Any


  1. ^ a b c d Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. p. 127. ISBN 1568810768. 
  2. ^ a b Chen, Yiling; Lai, John K.; Parkes, David C.; Procaccia, Ariel D. (2013). "Truth, justice, and cake cutting". Games and Economic Behavior 77 (1): 284–297. doi:10.1016/j.geb.2012.10.009. 
  3. ^ Neyman, J (1946). "Un théorèm dʼexistence". C. R. Acad. Sci. 222: 843–845. 
  4. ^ a b Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly 68: 1. doi:10.2307/2311357. JSTOR 2311357. , Corollary 1.1.
  5. ^ . doi:10.1016/0022-247x(80)90225-5.  Missing or empty |title= (help)
  6. ^ a b . doi:10.1016/0022-247x(85)90021-6.  Missing or empty |title= (help)
  7. ^ Fischer, Daniel. "Consensus division of a cake to two people in arbitrary ratios". Math.SE. Retrieved 23 June 2015. 
  8. ^ There is a generalization which gives each of n partners, a piece worth exactly 1/n for him. But this is not a consensus division, because the partners may not agree on the value of the other pieces besides the piece allocated to them. See Austin moving-knife procedures#Many partners.
  9. ^ . doi:10.1137/0606010.  Missing or empty |title= (help)
  10. ^ . doi:10.1090/s0002-9939-1986-0861764-9.  Missing or empty |title= (help)
  11. ^ a b Simmons, Forest W.; Su, Francis Edward (2003). "Consensus-halving via theorems of Borsuk-Ulam and Tucker". Mathematical Social Sciences 45: 15–25. doi:10.1016/S0165-4896(02)00087-2. 
  12. ^ B. Grünbaum (1960). "Partitions of mass–distributions and convex bodies by hyperplanes". Pacific J. Math 10: 1257–1261. 
  13. ^ Adapted from Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. pp. 68–71. ISBN 1568810768. 
  14. ^ V. Bergström (1930). "Zwei Sätze über ebene Vectorpolygone". Hamburgische Abhandlungen 8: 205–219. 
  15. ^ Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. pp. 126–128. ISBN 1568810768. 
  16. ^ Brams, Steven J.; Taylor, Alan D. Fair Division [From cake-cutting to dispute resolution]. pp. 131–133. ISBN 0521556449. 
  17. ^ Mossel, Elchanan; Tamuz, Omer (2010). "Truthful Fair Division". Lecture Notes in Computer Science: 288–299. doi:10.1007/978-3-642-16170-4_25. 
  18. ^ Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. pp. 103–104. ISBN 1568810768. 
  19. ^ de Longueville, Mark; Živaljević, Rade T. (2008). "Splitting multidimensional necklaces". Advances in Mathematics 218: 926–939. doi:10.1016/j.aim.2008.02.003. 
  20. ^ Pre-requisites on the value functions of the partners. Less pre-requisites mean that the result is more general. Con=Continuous is the most general; Con+Add=Additive is less general; Con+Add+Pwl=Piecewise-linear is the least general.

See also[edit]