Search in Co-Wiki

Consensus splitting

game-theory 3371 tokens 7 outbound links

Consensus splitting

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). 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 <math>R\to \infty</math>, 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 (sub-intervals), and each of the n partners values only a single district. Then, a consensus division of the cake into k subsets requires <math>n\cdot (k-1)</math> 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 (an interval).

Consider first the consensus halving case: <math>k=2</math> and equal weights. The lower bound on the number of cuts is <math>n\cdot (k-1)=n</math>. 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 <math>n</math> cuts can be represented as a vector of length <math>n+1</math>, 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 homeomorphic to the sphere <math>S^n</math>. Define a function <math>V: S^n \to \mathbb{R}^n</math> in the following way: for every partition , <math>V(x)</math> 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 , <math>V(x)+V(-x)=0</math>. Hence, by the Borsuk-Ulam theorem, there exists an such that <math>V(x)=0</math>. In that partition, all partners value piece #1 (and piece #2) 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. 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. 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(n k) 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 respect to their measure, i.e. volume) with a single -dimensional hyperplane.

Stated differently: if the cake is the space <math>\mathbb{R}^n</math>, and the value measures of the partners are finite and vanish on any <math>n-1</math> 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. The other agent 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 among n=2 partners and any k>1 subsets. The number of cuts is <math>2(k-1)</math>.

As of 2015, there is no known generalization of this moving-knife procedure to n>2 agents.

Computation of near-exact divisions with unbounded number of cuts ### Crumb-and-pack procedure For any given <math>\varepsilon > 0</math>, one can give each partner a piece such that all partners believe that the values they have differ by less than <math>\varepsilon</math>, i.e., for every i and every j:

Computation of near-exact divisions with bounded number of cuts Most results for bounded number of cuts focus on the case in which the weights are equal.

Two subsets (consensus halving) An ε-approximate consensus halving can be computed by an algorithm based on Tucker's lemma, which is the discrete version of Borsuk-Ulam theorem. An adaptation of this algorithm shows that the problem is in the complexity class PPA. This holds even for arbitrary bounded and non-atomic valuations. However, the run-time of this algorithm may be exponential in the problem parameters. In fact, consensus halving is computationally hard in several respects.

First, assumed that ε is allowed to be inverse-exponential in n (that is, 1/ε is an exponential function of n). Then, finding an ε-approximate consensus-halving is PPA-hard. Hardness holds even with the following additional conditions: The agents' valuations are piecewise-uniform with only two blocks (However, when agents have piecewise-uniform valuations with a single block, the problem can be solved in parametrized-polynomial time for n cuts, and in polynomial time for 2n-d cuts for any constant d). The number of agents is a constant and at least 3 (However, with 2 agents it can be solved in polynomial time).

Next, assume that ε is a constant (does not depend on n). Then, finding an ε-approximate consensus-halving is PPAD-hard, which is theoretically weaker than PPA-hard. The proof is by reduction from the ε-approximate Generalised Circuit problem. Hardness holds even in the following conditions:

The valuations are piecewise-constant; It is allowed to use a constant number of additional cuts (that is, we search for a consensus halving for n agents using n+d cuts, for some constant d). When ε is a constant, it is open whether ε-approximate consensus-halving is PPA-hard (which is stronger than PPAD-hard). When agents' valuations are represented by algebraic circuits, ε-approximate consensus-halving is polynomial-time equivalent to computing an approximation to an exact solution of the Borsuk-Ulam search problem. This means that it is complete for the complexity class BU – a superclass of FIXP that involves solutions to problems whose existence is guaranteed by the Borsuk-Ulam theorem. When the resource to divide is not a cake but rather a set of divisible resources, the problem becomes easier: For agents with additive utilities, there is a polynomial-time algorithm for computing a consensus halving with at most n cuts, and for computing a consensus k-division with at most (k-1)n cuts It is NP-hard to compute a consensus halving with the optimal number of cuts for a given instance. Moreover, it is NP-hard to compute a consensus halving with at most OPT+n-1 cuts, where OPT is the optimal number of cuts for the instance. n cuts are almost surely necessary for consensus halving when agents' utilities are drawn from probabilistic distributions. * For agents with non-additive monotone utilities, consensus halving is still PPAD-hard, but there are polynomial-time algorithms for a fixed number of agents.

Many subsets (consensus 1/k-division) From a computational perspective, not much is known about the computation of an exact division with <math>(k-1)n</math> cuts for <math>k\geq 3</math>. Note that the problem is not necessarily harder than for <math>k\geq 2</math>, since we are allowed to use a larger number of cuts. What is currently known is: The problem is in PPA-k for any k*. The problem is PPA-hard for k=3, when 1/ε may be an exponential function of n.* Finding a partition such that each agent values each part at least 1/kn*, using <math>(k-1)n</math> cuts, in an online algorithm. It is open whether the 1/*kn* can be improved. Particularly, it is open whether there is an efficient (online or offline) algorithm such that each agent values each part at least 1/*c*(*k*), where c(k) is some function of *k* (independent of *n*), using <math>(k-1)n</math> cuts. * Finding a partition such that each agent values each part at 1/*k* ± *ε*, using <math>O(\frac{kn \log{(kn)}}{\varepsilon^2})</math> cuts in an online algorithm, or using <math>n\cdot(k-1)\cdot \lceil2+\log_2(3k/\epsilon)\rceil</math> cuts. there are n agents grouped into k families; the goal is to partition a cake into k pieces and allocate one piece per family. 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). The problem is equivalent to exact division in the following sense: For every n and k, a solution to unanimous-proportional division among n(k-1)+1 agents grouped into k families implies a solution to exact division among n agents with k pieces (and equal weights). In particular, it implies that unanimous-proportional division requires at least n*-1 cuts, and that finding an approximate unanimous-proportional division is PPA-hard. For every n and k, a solution to exact-division among n agents and k pieces implies a solution to unanimous-proportional division among n+1 agents grouped into k families. In particular, it implies that exact unanimous-proportional division can be done with (n-1)(k-1) cuts, and that finding an approximate unanimous-proportional division is in PPA. The number of cuts is tight for k=2 families but not for k>2.*

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: # Ask each partner to report his value measure. # 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. # 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.

See also: truthful-cake-cutting. ## Summary table ## See also * [[problem-of-the-nile]]

References