Hardness Results for Consensus-Halving

Introduction

Suppose that two families want to split a piece of land into two regions such that every member of each family believes that the land is equally divided, or suppose that a conference organizer wants to assign the conference presentations to the morning and the afternoon sessions, so that every participant thinks that the two sessions are equally interesting. Is it possible to achieve these objectives? If yes, how can it be done and how efficiently? What if we aim for “almost equal” instead of “equal”?

These real-life problems can be modeled as the Consensus-halving problem . More formally, there are $n$ agents and an object to be divided; each agent may have a different opinion as to which part of the object is more valuable. The problem is to divide the object into two portions such that each of the $n$ agents believes that the two portions have equal value, according to her personal opinion. The division may need to cut the object into pieces and then label each piece appropriately to include it in one of the two portions.

The importance of the Consensus-halving problem - or to be precise, of its approximate version, where there is an associated precision parameter $\epsilon$ - other than the fact that it models real-life problems like the ones described above, lies in in the following fact: It is the first “natural” problem that is complete for the complexity class PPA, where “natural” here means that its does not contain a circuit explicitly in its definition; this was proven quite recently by Filos-Ratsikas and Goldberg . PPA is a class of total search problems defined in , and is a superclass of the class PPAD, which precisely captures the complexity of computing a Nash equilibrium . Therefore, generally speaking, a PPA-hardness result is stronger than a PPAD-hardness result.

Crucially however, the hardness result in requires the precision parameter to be inverse-exponential in the number of agents and does not even provably preclude the possibility of efficient algorithms, if we allow larger discrepancies in the values for the two portions. In this paper, we prove that this is actually not possibleUnder usual computational complexity assumptions, here that PPAD-hard problems do not admit polynomial-time algorithms., by showing that even when the allowed discrepancy is independent of the number of agents, the problem is PPAD-hard. Understanding the problem for increasing values of the discrepancy parameter is quite important in terms of capturing precisely its complexity and resembles closely the series of results establishing hardness of computing a mixed $\epsilon$-Nash equilibrium, from $\epsilon$ being inverse-polynomial in to being constant in , as well as several other problems (see ). Additionally, one could imagine that solutions where constant discrepancies are acceptable are the ones arising in several real-life scenarios, such as splitting land.

We are interested in the computational complexity of computing an $\epsilon$-approximate solution to the Consensus-halving problem where $\epsilon$ is a constant function of the number of agents, as well as the complexity of deciding whether given an input instance, $n-1$ cuts are sufficient to achieve an $\epsilon$-approximate solution. We discuss our main results below.

We prove that the problem of finding an $\epsilon$-approximate solution to the Consensus-halving problem for $n$ agents using $n$ cuts is PPAD-hard. Moreover, the problem remains PPAD-hard even if we allow a constant number of additional cuts. The result is established via a reduction from the approximate Generalized Circuit problem .

We prove that it is NP-hard to decide whether or not an $\epsilon$-approximate solution to the Consensus-halving problem for $n$ agents using $n-1$ cuts exists. We establish the result via a reduction from 3SAT.

We prove that the problem of finding an $\epsilon$-approximate solution to the Consensus-halving problem for $n$ agents using $n$ cuts is in the computational class PPA; we obtain the result via a reduction to the computational version of Tucker’s Lemma .

We remark here that an earlier version of this paper actually predated and some of the results in are established by referencing the results in the present paper. Specifically:

While the authors of provide a rather elaborate reduction to establish PPA-hardness of the problem, the containment in the class PPA is established with reference to the present paper. In turn, the containment result follows from a formalization of the ideas of the algorithms by and and Fan’s version of Tucker’s Lemma .

In , the authors obtain a computational equivalence between the Necklace Splitting problem and $\epsilon$-Consensus Halving, for $\epsilon$ being at least inverse-polynomial. The inverse-polynomial dependence on $\epsilon$ implies that PPA-hardness of the former problem does not follow from their hardness result, but PPAD-hardness does follow from their reduction and our main result here.

2 Related work

The Consensus-Halving problem was explicitly formalized and studied firstly by Simmons and Su , who proved that a solution with $n$ cuts always exists and constructed a protocol that finds an approximate solution, which allows for a small discrepancy on the values of the two portions. Their proofs are based on one of the most applied theorems in topology, the Borsuk-Ulam Theorem and its combinatorial analogue, known as Tucker’s Lemma . The existence of solutions to the problem was already known since but the algorithm in is constructive, in the sense that it actually finds such a solution and furthermore, it does not require the valuations of the players to be additively separable over subintervals, like some of the previous papers do. Actually, for the case of valuations which are probability measures, the existence of a solution with $n$ cuts was known since as early as the 1940s and can also be obtained as an application of the Hobby-Rice Theorem (also see ). Despite proposing an explicit protocol however, the authors in do not answer the question of “efficiency”, i.e. how fast can a protocol find an (approximate) solution and the running time of their protocol is worst-case exponential-time.The protocol exhaustively iterates through all the vertices of triangulated geometric object, which, to achieve a small discrepancy, has to be exponentially large.

To this end, Filos-Ratsikas and Golberg recently proved that the problem is PPA-complete, but as we explained in the introduction, the hardness holds only when the precision parameter is exponentially-small and therefore does not subsume our results. The computational classes PPA (Polynomial Parity Arguments) and PPAD (Polynomial Parity Arguments on Directed graphs) were introduced by Papadimitriou in an attempt to capture the precise complexity of several interesting problems of a topological nature such as computational analogues of Sperner’s Lemma and Brouwer’s and Kakutani’s fixed point theorems , which are all known to be in PPAD . Interestingly, Aisenberg et al. recently proved that the search problems associated with the Borsuk-Ulam Theorem and Tucker’s Lemma are PPA-complete; this is the starting point for the reduction in , but it will also be used for our “in-PPA” result, which complements the hardness result of .

Our PPAD-hardness reduction goes via the Generalized Circuit problem. Generalized circuits differ from usual circuits in the sense that they can contain cycles, a fact which basically induces a continuous function on the gates, and the solution is guaranteed to exist by Brouwer’s fixed point theorem. The $\epsilon$-approximate Generalized Circuit problem was implicitly proven to be PPAD-complete for exponentially small $\epsilon$ in and explicitly for polynomial small $\epsilon$ , en route to proving that perhaps the most interesting problem in PPAD, that of computing a mixed-Nash equilibrium, is also complete for the class. The same problem was also used in to prove that finding an approximate market equilibrium for the Arrow-Debreu market with linear and non-monotone utilities is PPAD-complete and in to prove that finding an approximate solution of the Competitive Equilibrium with Equal Incomes (CEEI) for indivisible items is PPAD-complete. More recently, Rubinstein showed that computing an $\epsilon$-approximate solution for the Generalized Circuit problem is PPAD-complete for a constant $\epsilon$, which implies that finding an $\epsilon$-approximate Nash equilibrium is PPAD-complete for constant $\epsilon$, in the context of graphical games; we reduce from that version of the problem. This improvement should also lead to stronger hardness results in and , as well as other problems that rely on the Generalized Circuit problem.

The Consensus-Halving problem is a typical fair division problem that studies how to divide a set of resources between a set of agents who have valuations on the resources, such that some fairness properties are fulfilled. The fair division literature, which dates back to the late 1940s , has studied a plethora of such problems, with chore-division , rent-partitioning and the perhaps the most well-known one, cake-cutting being notable examples. Note that Consensus-halving is inherently different from (envy-free or proportional) cake-cutting, since the objective is that all participants are (approximately) equally satisfied with the solution, and they do not have “ownership” over the resulting pieces.

Preliminaries

We represent the object $O$ as a line segment $$. Each agent in the set of agents$N=\{1,\ldots,n\}$has its own valuation over any subset of interval$$. These valuations are:

non-negative and bounded, i.e. there exists $M>0$, such that for any subinterval $X\subseteq$, it holds that $0\leq u_{i}(X)\leq M$.

non-atomic, i.e. agents have no value on any single point on the interval.

The Consensus-halving problem is to divide the object $O$ into two portions $O_{+}$ and $O_{-}$, such that every agent derives equal valuation from the two portions, i.e., $u_{i}(O_{+})=u_{i}(O_{-}),\forall i\in N$. The $\epsilon$-approximate Consensus-halving problem allows that each agent has a small discrepancy on the values of the two partitions, i.e., $|u_{i}(O_{+})-u_{i}(O_{-})|<\epsilon$. As discussed in the Introduction, such as solution always exists. .

We define the following search problem, called $(n,k,\epsilon)$-ConHalving.

Input: The value density functions (valuation functions) $v_{i}:O->R_{+},i=1,\cdots,n$.

Output: A partition $(O_{+},O_{-})$ with $k$ cuts such that $|u_{i}(O_{+})-u_{i}(O_{-})|\leq\epsilon$.

We will also consider the following decision problem, called $(n,n-1,\epsilon)$-ConHalving. Note that for $n$ agents and $n-1$ cuts, a solution to $\epsilon$-approximate Consensus-halving problem is not guaranteed to exist.

Input: The value density functions $v_{i}:O->R_{+},i=1,\cdots,n$.

Output: Yes, if a partition $(O_{+},O_{-})$ with $n-1$ cuts such that $|u_{i}(O_{+})-u_{i}(O_{-})|\leq\epsilon$ for all agents $i\in N$ exists, and No otherwise.

TFNP, PPA and PPAD: Most of the problems that we will consider in this paper belong to the class of total search problems, i.e. search problems for which a solution is guaranteed to exist, regardless of the input. In particular, we will be interested in problems in the class TFNP, i.e. total search problems for which a solution is verifiable in polynomial time . An important subclass of TFNP is the class PPAD, defined by Papadimitriou in . PPAD stands for “Polynomial Parity Argument on a Directed graph” and is defined formally in terms of the problem End-Of-Line . The class PPAD is defined in terms of an exponentially large digraph $G=(V,E)$ consisting of $2^{n}$ vertices with indegree and outdegree at most $1$. An edge between vertices $v_{1}$ and $v_{2}$ is present in $E$ if and only if the successor $S(v_{1})$ of node $v_{1}$ is $v_{2}$ and the predecessor $P(v_{2})$ of node $v_{2}$ is $v_{1}$. By construction, the point $0^{n}$ has indegree and we are looking for a point with outdegree , which is guaranteed to exist. Note that the graph is given implicitly to the input, through a function that given any vertex $v$, returns its set of neighbours (predecessor and successor) in polynomial time. PPAD is a subclass of the class PPA (“Polynomial Parity Argument”) which is defined similarly, but in terms of an undirected graph in which every vertex has degree at most $2$, and given a vertex of degree $1$, we are asked to find another vertex of degree $1$; the computational problem associated with the class is called Leaf and a problem is the class PPA if it is polynomial-time reducible to Leaf.

For clarity of exposition, we postpone the formal definitions of End-Of-Line and Leaf until Section 5, where they are being used for the “in-PPA” result.

A generalized circuit $S=(V,\mathcal{T})$ consists of a set of nodes $V$ and a set of gates $\mathcal{T}$ and let $N=|V|$ and $M=|\mathcal{T}|$. Every gate $T\in\mathcal{T}$ is a 5-tuple $T=(G,v_{in_{1}},v_{in_{2}},v_{out},\alpha)$ where

$G\in\{G_{\zeta},G_{\times\zeta},G_{=},G_{+},G_{-},G_{<},G_{\vee},G_{\wedge},G_{\neg}\}$ is the type of the gate,

$v_{in_{1}},v_{in_{2}}\in V\cup\{nil\}$ are the first and second input nodes of the gate or $nil$ if not applicable,

$v_{out}\in V$ is the output node, and $\alpha\in\cup\{nil\}$ is a parameter if applicable,

for any two gates $T=(G,v_{in_{1}},v_{in_{2}},v_{out},\alpha)$ and $T^{\prime}=(G^{\prime},v_{in_{1}}^{\prime},v_{in_{2}}^{\prime},v_{out}^{\prime},\alpha^{\prime})$ in $\mathcal{T}$ where $T\neq T^{\prime}$, they must satisfy $v_{out}\neq v_{out}^{\prime}$.

Note that generalized circuits extend the standard boolean or arithmetic circuits in the sense that generalized circuits allow cycles in the directed graph defined by the nodes and gates. We define the search problem $\epsilon$-Gcircuit :

Input: A generalized circuit $S=(V,\mathcal{T})$.

Output: A vector $\mathbf{x}\in^{N}$ of values for the nodes, satisfying the conditions from Table 1.

Note that a solution to $\epsilon$-Gcircuit always exists and hence the problem is well-defined. Also, notice that for the logic gates $G_{\vee},G_{\wedge}$ and $G_{\neg}$, if the input conditions are not fulfilled, the output is unconstrained, and for the multiplication gate, it holds that $\alpha\in(0,1]$. $\epsilon$-Gcircuit was proven to be PPAD-complete implicitly or explicitly in for inversely polynomial error $\epsilon$ and in for constant $\epsilon$. We state the latter theorem here as a lemma:

There exists a constant $\epsilon>0$ such that $\epsilon$-Gcircuit is PPAD-complete.

(n,n+k,ϵ)𝑛𝑛𝑘italic-ϵ(n,n+k,\epsilon)-ConHalving is PPAD-hard

𝑛𝑘italic-ϵ(n,n+k,\epsilon)-ConHalving is PPAD-hard In this section, we will prove that finding an approximate partition for Consensus-halving using $n$ cuts is PPAD-hard, even if the allowed discrepancy between the two portions is a constant. We describe the reduction from $\epsilon$-Gcircuit that we will be using for the PPAD-hardness proof. Given an instance $S=(V,\mathcal{T})$ of $\epsilon$-Gcircuit, we will construct an instance of $(n,n,\epsilon^{\prime})$-ConHalving with $n=2N$ agents, in which each node $v_{i}\in V$ of the circuit will correspond to two agents $var_{i}$ and $copy_{i}$ and where $\epsilon^{\prime}$ will be defined later. As a matter of convenience in the reduction, we will assume that for every gate $(G,v_{in_{1}},v_{in_{2}},v_{out},\alpha)$ in $\mathcal{T}$, $v_{in_{1}},v_{in_{2}}$ and $v_{out}$ are distinct. This does not affect the hardness of the problem as any $\epsilon$-generalized circuit can be converted to this form by use of at most $2N$ additional equality-gates and nodes, and also since an $(\epsilon/2)$-approximate solution to the converted problem can clearly be converted to a solution in the original circuit.

For ease of notation we consider a ConHalving instance on the interval $[0,6N]$. Let $d_{i}:=6(i-1)$; the two agents $var_{i}$ and $copy_{i}$ that we construct for every node $v_{i}$ have valuations {ceqn}

Given the construction of a $(n,n,\epsilon^{\prime})$-ConHalving instance above, for $\epsilon^{\prime}<\min\{\epsilon/11,1/40\}$, a partition with $n$ cuts corresponds to a solution to $\epsilon$-Gcircuit.

First observe that since all of the agents $var_{i}$ and $copy_{i}$ are constructed to have at least $3/4$ of their valuation on $[d_{i},d_{i}+3]$ and $[d_{i}+3,d_{i}+6]$ respectively, there must be at least one cut in each one of those intervals in any $\epsilon^{\prime}$-approximate solution to Consensus-halving (with $\epsilon^{\prime}<1/4$) and therefore any $\epsilon^{\prime}$-approximate solution to Consensus-halving with $2N$ cuts must have exactly one cut in each interval. Furthermore, since the constructed instance consists of $2N$ agents, by , such a partition with $2N$ cuts is guaranteed to exist.

Now consider such a solution $\mathcal{C}$ to $(n,n,\epsilon^{\prime})$-ConHalving with $2N$ cuts. For each agent $var_{i}$ (and associated gate $G^{\tau}$, if any), since her valuation in $v_{i}^{-}$ is at least the same as her valuation outside the interval $[d_{i},d_{i}+3]$, the cut from $\mathcal{C}$ in $[d_{i},d_{i}+3]$ must be in $[d_{i}+1-\epsilon^{\prime},d_{i}+2+\epsilon^{\prime}]$, since $\mathcal{C}$ is a solution to $(n,n,\epsilon^{\prime})$-ConHalving. We will assume without loss of generality that the leftmost piece of the partition $\mathcal{C}$ is in $O_{-}$. Notice then that for each node $v_{i}$, the piece on the left-hand side of the cut in $v_{i}^{-}$ is always in $O_{-}$ and the piece on the left-hand side of the cut in $v_{i}^{+}$ is always in $O_{+}$. Let the location of the cut be $d_{i}+1+t_{i}^{-}$ where $t_{i}^{-}\in[-\epsilon^{\prime},1+\epsilon^{\prime}]$. Analogously, the same argument holds for agent $copy_{i}$ and the interval $[d_{i}+3-\epsilon^{\prime},d_{i}+4+\epsilon^{\prime}]$, and define $t_{i}^{+}\in[-\epsilon^{\prime},1+\epsilon^{\prime}]$ similarly.

Now consider the agent $copy_{i}$ and the cut at location $d_{i}+1+t_{i}^{-}$. If $t_{i}^{-}\in$, then since agent $copy_{i}$ has valuation $1$ on interval $v_{i}^{-}$, $t_{i}^{-}$ of her valuation will be on a piece in $O_{-}$ and $1-t_{i}^{-}$ of her valuation will be on a piece in $O_{+}$. Then, since $\mathcal{C}$ is a solution to $(n,n,\epsilon^{\prime})$-ConHalving, the cut in $d_{i}+3+t_{i}^{+}$ must be placed so that $|t_{i}^{-}-t_{i}^{+}|\leq\epsilon^{\prime}/2$; similarly for the cases where $t_{i}^{-}\notin$. In other words, $copy_{i}$ ensures that the cut at $d_{i}+1+t_{i}^{-}$ is “copied” $\epsilon^{\prime}$-approximately.

We will interpret the solution $\mathcal{C}$ as a solution to $\epsilon$-Gcircuit in the following way. For each node $v_{i}$ and each associated cut at $d_{i}+1+t_{i}^{-}$ let {ceqn}

To complete the proof, we just need to argue that these variables satisfy the constraints of the gates of the circuit.

Constant gate $\tau=(G_{\zeta},nil,nil,v_{out},\alpha)$: The valuation of agent $var_{out}$ for the intervals $[d_{i},d_{i}+1+\alpha]$ and $[d_{i}+1+\alpha,d_{i}+3]$ is the same and since the height of the agent’s value density function is at least 1 in $[d_{i},d_{i}+3]$,Notice that the constant gate is the only gate where $border_{i}$ and $G^{\tau}$ overlap. it holds that $t_{out}^{-}\in[\alpha-\epsilon^{\prime},\alpha+\epsilon^{\prime}]$. Then, by Equation 2, it holds that $x_{out}\in[\alpha-3\epsilon^{\prime},\alpha+3\epsilon^{\prime}]$, so for $\epsilon^{\prime}<\epsilon/3$ the gate constraint is satisfied.

Multiplication-by-scalar gate $\tau=(G_{\times\zeta},v_{in},nil,v_{out},\alpha)$. Notice that for any given cut $t_{in}^{+}$ and $1-\alpha\geq\epsilon$, it holds that $t_{out}^{-}\in[\alpha t_{in}^{+}+\epsilon/2-\epsilon^{\prime},\alpha t_{in}^{+}+\epsilon/2+\epsilon^{\prime}]$ as the height of $G^{\tau}$ in $v_{out}^{-}$ is at least 1. Similarly, for the case $1-\alpha<\epsilon$ and any given cut $t_{in}^{+}$, it holds that $t_{out}^{-}\in[\alpha t_{in}^{+}+(1-\alpha)/2-\epsilon^{\prime},\alpha t_{in}^{+}+(1-\alpha)/2+\epsilon^{\prime}]$ as the height of $G^{\tau}$ in $v_{out}^{-}$ is at least 1. In particular, since $1-\alpha<\epsilon$, it also holds that $t_{out}^{-}\in[\alpha t_{in}^{+}+\epsilon/2-\epsilon^{\prime},\alpha t_{in}^{+}+\epsilon/2+\epsilon^{\prime}]$ for this case as well. Then, by Equation 2, it holds that $x_{out}\in[\alpha t_{in}^{+}+\epsilon/2-3\epsilon^{\prime},\alpha t_{in}^{+}+\epsilon/2+3\epsilon^{\prime}]$ and since $\alpha\leq 1$ it also holds that $x_{out}\in[\alpha x_{in}+\epsilon/2-5\epsilon^{\prime},\alpha x_{in}+\epsilon/2+5\epsilon^{\prime}]$, again by Equation 2. Then the gate constraint is satisfied whenever $\epsilon^{\prime}<\epsilon/10$.

Addition gate $\tau=(G_{{+}},v_{in_{1}},v_{in_{2}},v_{out},nil)$. If for the cuts $t_{in_{1}}^{+}$ and $t_{in_{2}}^{+}$ it holds that $t_{in_{1}}^{+}+t_{in_{2}}^{+}<1-\epsilon+4\epsilon^{\prime}$ then $t_{out}^{-}\in[t_{in_{1}}^{+}+t_{in_{2}}^{+}-5\epsilon^{\prime},t_{in_{1}}^{+}+t_{in_{2}}^{+}+5\epsilon^{\prime}]$ as the height of $G^{\tau}$ in $v_{out}^{-}$ is at least 1. This then implies that $x_{out}\in[x_{in_{1}}^{+}+x_{in_{2}}^{+}-11\epsilon^{\prime},x_{in_{1}}^{+}+x_{in_{2}}^{+}+11\epsilon^{\prime}]$, by Inequality 2. On the other hand, when $t_{in_{1}}^{+}+t_{in_{2}}^{+}\geq 1-\epsilon+4\epsilon^{\prime}$, then by Definition 1, it holds that $x_{in_{1}}+x_{in_{2}}\in[1-\epsilon,1]$ and clearly $t_{out}^{-}\in[1-\epsilon,1+\epsilon^{\prime}]$ which by Definition 1 implies that $x_{out}\in[1-\epsilon,1]$. The gate constraints are satisfied for $\epsilon^{\prime}<\epsilon/11$ for each of the cases.

Subtraction gate $\tau=(G_{{-}},v_{in_{1}},v_{in_{2}},v_{out},nil)$. Analogously to the addition gate described above, when for the cuts $t_{in_{1}}^{+}$ and $t_{in_{1}}^{+}$ it holds that $t_{in_{1}}^{+}-t_{in_{2}}^{+}>\epsilon-4\epsilon^{\prime}$ then $t_{out}^{-}\in[t_{in_{1}}^{+}-t_{in_{2}}^{+}-5\epsilon^{\prime},t_{in_{1}}^{+}-t_{in_{2}}^{-}+5\epsilon^{\prime}]$ as the height of $G^{\tau}$ in $v_{out}^{-}$ is at least 1. This implies that $x_{out}\in[x_{in_{1}}^{+}-x_{in_{2}}^{-}-11\epsilon^{\prime},x_{in_{1}}^{+}-x_{in_{2}}^{-}+11\epsilon^{\prime}]$ by Inequality 2. On the other hand when $t_{in_{1}}^{+}-t_{in_{2}}^{-}\leq\epsilon-\epsilon^{\prime}$, which implies that $x_{in_{1}}+x_{in_{2}}\in[0,\epsilon]$ by Definition 1, it clearly holds that $t_{out}^{-}\in[-\epsilon^{\prime},\epsilon]$ and hence by Definition 1, we have $x_{out}\in[0,\epsilon]$. The gate constraints are satisfied for $\epsilon^{\prime}<\epsilon/11$ for each of the cases.

Less-than-equal gate $\tau=(G_{{<}},v_{in_{1}},v_{in_{2}},v_{out},nil)$. We will consider three cases, depending on the positions of the cuts $t_{in_{1}}^{+}$ and $t_{in_{2}}^{-}$. First, when $|t_{in_{1}}^{+}-t_{in_{2}}^{-}|<\epsilon-4\epsilon^{\prime}$, by Inequality 2 it holds that $|x_{in_{1}}-x_{in_{2}}|<\epsilon$ and the output of the gate is unconstrained. When $t_{in_{1}}^{+}-t_{in_{2}}^{-}\geq\epsilon-4\epsilon^{\prime}$ then by Inequality 2 it holds that $x_{in_{1}}\geq x_{in_{2}}+\epsilon$. Additionally, since the height of $G^{\tau}$ in $[v_{out,r}^{-}-\epsilon,v_{out,r}^{-}]$ is at least 1, it holds that $t_{out}^{-}\in[1-\epsilon,1+\epsilon^{\prime}]$, which by Definition 1 implies that $x_{out}^{-}\in[1-\epsilon,1]$ and the gate constraint is satisfied. The argument for the case when $t_{in_{2}}^{-}>t_{in_{1}}^{+}-2\epsilon^{\prime}$ is completely symmetrical.

Logic OR gate $\tau=(G_{{\vee}},v_{in_{1}},v_{in_{2}},v_{out},nil)$. We will consider three cases depending on the position of the cuts $t_{in_{1}}^{+}$ and $t_{in_{2}}^{+}$. First, when $t_{in_{1}}^{+}+t_{in_{2}}^{+}<0.4$ it holds that $t_{out}^{-}\in[-\epsilon^{\prime},\epsilon]$ and hence by Definition 1, it holds that $x_{out}\in[0,\epsilon$]. Furthermore, by Inequality 2 it holds that $x_{in_{1}}+x_{in_{2}}<0.4+4\epsilon^{\prime}$ and for $\epsilon^{\prime}<1/40$, it also holds that $x_{in_{1}},x_{in_{2}}<0.5$ and the gate constraint is satisfied. Next, when $t_{in_{1}}^{+}+t_{in_{2}}^{+}\in[0.4,0.8]$ then by Inequality 2, it holds that $x_{in_{1}},x_{in_{2}}\in[0.4-\epsilon^{\prime},0.8+4\epsilon^{\prime}]$ and in particular, when $\epsilon^{\prime}<1/40$ then it also holds that $x_{in_{1}}+x_{in_{2}}\in[0.3,0.9]$ and the output of the gate in unconstrained. Finally when $t_{in_{1}}^{+}+t_{in_{2}}^{+}>0.8$, it holds that $t_{out}^{-}\in[1-\epsilon,1+\epsilon^{\prime}]$ and hence by Definition 1, we have that $x_{out}\in[1-\epsilon,1]$. Furthermore, by Inequality 2 we have that $x_{in_{1}}+x_{in_{2}}>0.8+4\epsilon^{\prime}$ which is greater than $0.9$ when $\epsilon^{\prime}<1/40$ which implies that at least one of the two inputs is greater than $\epsilon$. In particular, the gate’s output lies in $[1-\epsilon,\epsilon]$ when the inputs are smaller than $\epsilon$ or greater than $1-\epsilon$ and at least one of them is greater than $1-\epsilon$. This shows that the gate constraint is satisfied.

Logic AND gate $\tau=(G_{{\wedge}},v_{in_{1}},v_{in_{2}},v_{out},nil)$. Analogously to the Logical OR gate, we will consider three cases, depending on the position of the cuts $t_{in_{1}}^{+}$ and $t_{in_{2}}^{+}$. First, when $t_{in_{1}}^{+}+t_{in_{2}}^{+}<1.4$, it holds that $t_{out}^{-}\in[-\epsilon^{\prime},\epsilon]$ and by Inequality 1, we have that $x_{out}\in[0,\epsilon]$. On the other hand, by Inequality 2, we have that $x_{in_{1}}+x_{in_{2}}<1.4+4\epsilon^{\prime}$ which is at most $1.5$ for $\epsilon^{\prime}<1/40$ and the gate constraint is satisfied for the same reason as in the third case of the Logic OR gate above (using the argument symmetrically, for values smaller than $\epsilon$ instead of at larger than $1-\epsilon$). Next, when $1.4\leq t_{in_{1}}^{+}+t_{in_{2}}^{+}\leq 1.8$, by Inequality 2 and for $\epsilon^{\prime}<1/40$, it holds that $x_{in_{1}}+x_{in_{2}}\in[1.3,1.9]$ and the output of the gate is unconstrained. Finally, when $t_{in_{1}}^{+}+t_{in_{2}}^{+}>1.8$, by Inequality 2 and for $\epsilon^{\prime}<1/40$, it holds that $x_{in_{1}}+x_{in_{2}}>1.7$. Furthermore, it holds that $t_{out}^{-}\in[1-\epsilon,1+\epsilon^{\prime}]$ and hence by Definition 1, we have that $x_{out}\in[1-\epsilon,1]$ and the gate constraint is satisfied.

Logic NOT gate $\tau=(G_{{\neg}},v_{in},v_{in_{2}},v_{out},nil)$. We will consider three cases, depending on the location of the cut $t_{in}^{-}$. First, if $t_{in}^{-}<0.4$, it holds that $t_{out}^{-}\in[-\epsilon^{\prime},\epsilon]$ and hence by Definition 1, we have that $x_{out}\in[0,\epsilon]$. Furthermore, by Inequality 2, it holds that $x_{in}<0.4+4\epsilon^{\prime}$ which is at most $0.5$ when $\epsilon^{\prime}<1/40$ and the gate constraint is satisfied because for any value of the input smaller than $\epsilon$, the output is in $[0,\epsilon]$. Next, when $t_{in}^{-}\in[0.4,0.8]$ and for $\epsilon<1/40$, by Inequality 2 it holds that $x_{in}\in[0.3,0.7]$ and the output of the gate in unconstrained. Finally, when $t_{in}^{-}>0.8$, it holds that $t_{out}^{-}\in[1-\epsilon,1+\epsilon^{\prime}]$ and by Definition 1, we have that $x_{out}\in[1-\epsilon,1]$. Furthermore, by Inequality 2 and for $\epsilon^{\prime}<1/40$, it holds that $x_{in}>0.9$ and the gate constraint is satisfied for a reason analogous to the one described above.

Given the discussion above, by setting $\epsilon^{\prime}<\min\{\epsilon/11,1/40\}$We can in fact assume some $\epsilon\leq 11/40$, as the smaller the $\epsilon$, the harder the problem is, since we are interested in establishing hardness for some constant $\epsilon$., the gate constraints are satisfied, and the vector $(x_{i})$ obtained from $\mathcal{C}$ is a solution to $\epsilon$-Gcircuit. ∎

Now from Lemma 2, we obtain the following result.

There exists a constant $\epsilon^{\prime}>0$ such that $(n,n,\epsilon^{\prime})$-ConHalving is PPAD-hard.

Recall that in the proof of Lemma 2, $\epsilon^{\prime}$ was constrained to be at most $\min\{1/40,\epsilon/11\}$ and in particular by Lemma 1, there exists a constant $\epsilon^{\prime}$ that would make the reduction work. Recall however that we “expanded” the instance of $(n,\epsilon^{\prime})$-Chalving from the interval $[a,b]$ to $[0,6N]$ for convenience, which implies that after rescaling the instance to a constant interval $[a,b]$, the allowed error $\epsilon^{\prime}$ goes down to $O(1/n)$. To get a constant error $\epsilon^{\prime}$, we simply multiply all valuations by $N$. ∎

Theorem 1 implies that although a solution with $n$ cuts is generally desirable, it might be hard to compute, even for a relatively simple class of valuations like those used in the reduction. In fact, we can extend our results to the more general case of finding a partition with $n+k$ cuts where $k$ is a constant.

Let $k$ be any constant. Then there exists a constant $\epsilon^{\prime}$ such that $(n,n+k,\epsilon^{\prime})$-Chalving is PPAD-hard.

Let $S=(V,\mathcal{T})$ be an instance of $\epsilon$-Gcircuit with $N$ nodes, consisting of smaller identical sub-circuits $S_{i}=(V_{i},\mathcal{T}_{i})$, for $i=1,2,\ldots,k+1$, with with $N/(k+1)$ nodes each such that for all $i,j\in[k+1]$ such that $i\neq j$, it holds that $V_{i}\cap V_{j}=\emptyset$. and $\mathcal{T}_{i}\cap\mathcal{T}_{j}=\emptyset$. In other words, the circuit $S$ consists of $k+1$ copies of a smaller circuit $S_{i}$ that do not have any common nodes or gates. Furthermore, for convenience, assume without loss of generality that for two nodes $l$ and $m$ such that $u_{l}\in V_{i}$ and $u_{m}\in V_{j}$, with $i<j$, it holds that $l<m$. In other words, the labeling of the nodes is such that nodes in circuits with smaller indices have smaller indices.

(n,n−1,ϵ)𝑛𝑛1italic-ϵ(n,n-1,\epsilon)-Chalving is NP-hard

In the previous section, we proved that the problem of finding an approximate solution with $n$ players and $n$ cuts is PPAD-complete. Recall that for that case, we know that a solution exists . For $n$ players and $n-1$ cuts however, we don’t have the same guarantee. We prove that deciding whether this is the case or not is NP-hard.

There exists a constant $\epsilon^{\prime}>0$ such that $(n,n-1,\epsilon^{\prime})$-ConHalving is NP-hard.

We will first describe the construction that we will use in the reduction. For consistency with the previous section, we will denote the error of the Consensus-halving problem by $\epsilon^{\prime}$ and the error of the (implict) generalized circuits by functions of $\epsilon$. Let $R_{\epsilon}(S)$ be the construction for the reduction of Section 3 that encodes an $\epsilon$-generalized circuit $S$ into an $(n,n-1,\epsilon^{\prime})$-ConHalving halving instance when $\epsilon^{\prime}<\epsilon/11$. We will reduce from 3-SAT, which is known to be NP-complete.

Let $\phi$ be any 3-SAT formula with $m$ clauses, $k\leq 3m$ variables $x_{1},\ldots,x_{k}$, and let $\epsilon>0$ be given. For convenience of notation, let $\delta=\epsilon/11$. We will (implicitly) create a generalized circuit $S$ with the following building blocks:

$k$ input nodes $x_{1},\ldots,x_{k}$ corresponding to the variables $x_{1},\ldots,x_{k}$.

$k$ sub-circuits $\text{Bool}(x_{i})$ for $i=1,2,\ldots,k$ that input the real value $x_{i}\in$ and output a boolean value $x_{i}^{bool}\in\left[0,4\delta\right]\cup\left[1-4\delta,1\right]$ (see the lower stage of Figure 2). The allowed error for these circuits will be $\delta$. The implementation of the circuit in terms of the gates of the generalized circuit can be seen in Algorithm 1. Note that the sub-circuit containing all the $\text{Bool}(x_{i})$ sub-circuits has at most $4k$ nodes as each $\text{Bool}(x_{i})$ sub-circuit could be implemented with one constant gate, one subtraction gate, one addition gate and one equality gate; the latter is to maintain the convention that all inputs to each gate are distinct.

A sub-circuit $\Phi(x_{1}^{bool},\ldots,x_{k}^{bool})$ that implements the formula $\phi$, inputing the boolean variables $x_{i}^{bool}$ and outputting a value $x_{out}$ corresponding to the value of the assignment plus the error introduced by the approximate gates. The allowed error for this circuit will be $4\delta$. A pictorial representation of such a circuit can be seen in Figure 2; note that the circuits $\text{Bool}(x_{i})$ are also shown in the picture. This circuit has at most $k+3m$ nodes. First, there might be $k$ possible negation gates to negate the input variables. Secondly, for each clause, in order to implement an $OR$ gate of fan-in $3$, we need $2$ $OR$ gates of fan-in $2$, for a total of $2m$ gates for all clauses. Finally, in order to simulate the $AND$ gate with fan-in $m$, we need $m$ $AND$ gates of fan-in $2$. Overall, since $k\leq 3m$, we need at most $6m$ nodes to implement this sub-circuit, using elements of the generalized circuit.

A sub-circuit $\text{Rebool}(x_{1},\ldots,x_{k},x_{out})$ that inputs the variables $x_{i}$, for $i=1,2,\ldots,k$ and the variable $x_{out}$ and computes the function {ceqn}

The function can be computed using the gates of the generalized circuit as shown in Algorithm 2. Let $x_{out}^{bool}$ be the output of that sub-circuit with allowed error $4\delta$. Note that this circuit has at most $16k$ nodes. Each min and max operation requires $8$ nodes and we need to do $2k$ such computations overall; $k$ for the $k$ $\max$ operations and $k$ to implement the $\min$ operation of fan-in $k$ with $\min$ operations of fan-in $2$. Again, since $k\leq 3m$, this sub-circuit requires at most $48m$ nodes in total.

Following the notation introduced above, let $R_{\delta}(\text{Bool})$, $R_{4\delta}(\Phi)$ and $R_{4\delta}(\text{Rebool})$ denote the valuations of the agents in the instance of Consensus-halving corresponding to those sub-circuits, according to the reduction described in Section 3. In other words, based on the circuit described above, we create an instance $H$ of Consensus-halving where we have:

$2k$ agents (as each node corresponds to two agents, $var_{i}$ and $copy_{i}$) that correspond to the input variables $x_{1},\ldots,x_{k}$, who are not the output of any gate,

at most $2(4k+k+3m+16k)$ nodes corresponding to the internal nodes and the output node of the circuit,

an additional agent with valuation {ceqn}

where $[a,b]$ is the interval where the value of $x_{out}^{bool}$ is “read” in the instance of Consensus-halving, i.e. the interval where the cut $t_{out}^{bool}{-}$ will be placed in the Consensus-halving solution.

Recall Definition 1 from Section 3 and note that as far as agent $n$ is concerned, any cut $t_{out}^{bool}{-}$ such that $1-18m\epsilon\leq x_{out}^{bool}\leq 1$ is a Consensus-halving solution.

We will now argue about the correctness of the reduction. Let $n$ be the number of agents and notice that there are $n-1$ agents that correspond to the nodes of the circuit and a single agent constraining the value of $x_{out}^{bool}$. Notice that since the allowed error for the sub-circuit $\text{Rebool}(x_{1},\ldots,x_{k},x_{out})$ is $4\delta$, the total additive error of the agents of $R_{4\delta}(\text{Rebool})$ will be at most $4\delta\cdot 48m\leq 18m\epsilon^{\prime}$.

First, assume that there exists a a solution to $\epsilon^{\prime}$-approximate Consensus-halving with $n-1$ cuts. By the correctness of the construction of Section 3 and the fact that $\epsilon^{\prime}<\epsilon/11=\delta$, the solution encodes a valid assignment to the variables of the generalized circuit $S$. Due to the valuation of agent $n$, the output of $C$ must satisfy

otherwise the corresponding cut $t_{out}^{bool}{-}$ could not be a part of a valid solution. Since the total additive error for the circuit $\text{Rebool}(x_{1},\ldots,x_{k},x_{out})$ is at most $18m\epsilon^{\prime}$, if we choose $\epsilon^{\prime}<1/90m$, it holds that

by the function implemented by the circuit $\text{Rebool}(x_{1},\ldots,x_{k},x_{out})$. For the same reason, for each $i=1,\ldots,k$ it holds that

and hence the output of $\text{Bool}(x_{i})$ will lie in $[0,4\delta]\cup[1-4\delta,1]$, which means that the inputs $x_{1}^{bool},\ldots,x_{k}^{bool}$ to the gates of the sub-circuit $\Phi(x_{1}^{bool},\ldots,x_{k}^{bool})$ will be treated correctly as boolean values by the gates of the circuit (since the allowed error of the sub-circuit is $4\delta$). Since the circuit $\Phi(x_{1}^{bool},\ldots,x_{k}^{bool})$ computes the boolean operations correctly and $x_{out}\geq 3/4$, the formula $\phi$ is satisfiable.

Again, we remark here that by using similar arguments as in the proof of Corollary LABEL:col:PPADprob, we can prove that the result holds even when the valuations are probability measures.

(n,n,ϵ)𝑛𝑛italic-ϵ(n,n,\epsilon)-ConHalving is in PPA

In this section, we prove that $(n,n,\epsilon)$-ConHalving is in PPA. As we discussed in the introduction, this result of ours was referenced in to complement the PPA-hardness reduction of the inverse-exponential precision version and obtain PPA-completeness. For establishing this result, we construct a reduction from $(n,n,\epsilon)$-ConHalving to the PPA-complete problem Leaf which goes via $(n,T)$-Tucker, the computational version of Tucker’s Lemma.

The result is a corollary of Lemma 4 and Lemma 5, which will be proved in the remainder of the section. ∎

Before we proceed, we provide some intuition. In , Simmons and Su designed an algorithm for finding an approximate solution to the Consensus-Halving problem given access to an algorithm that solves Tucker on a triangulated cross-polytope (the formal definitions are given below). In the proof of Lemma 4 we use this algorithm directly to reduce the computational version of Consensus Halving, $(n,n,\epsilon)$-ConHalving, to the computational version of Tucker, $(n,T)$-Tucker, defined below.

Then, the inclusion of $(n,n,\epsilon)$-ConHalving in PPA will follow from the the fact that $(n,T)$-Tucker is in PPA. This was proven in where the computational version of the problem is defined on a subdivision of the hypercube, rather than the triangulation of the cross-polytope, as required for the Simmons-Su algorithm . For the latter problem, a proof was sketched in , where the idea was to map a triangulated hemisphere continuously and symmetrically to the hypercube. We provide a formal proof here, but following a different approach;A map between the two topological spaces or the corresponding solutions seems like the most natural approach, but formalizing the intuition seems like it could result in significant technical clutter. Our approach “moves” the technical difficulty to the definition of the “aligned with hemispheres” triangulation, which can rather be easily understood intuitively. Then, the two lemmas that establish the result are basically adaptations of the known algorithms of (Lemma 4) and (Lemma 5). we use an algorithm proposed by Prescott and Su (for proving a generalization of Tucker’s Lemma due to Fan ) and prove that it can be used to recover a solution to $(n,T)$-Tucker from a solution to Leaf. The algorithm requires $(n,T)$-Tucker to be defined on a specific type of triangulation $T$, which we also define below.

and its surface is the $n$-dimensional sphere

The $(n+1)$-dimensional cross-polytope is

i.e., unit ball in the $l_{1}$-norm. Denote the surface of $P^{n+1}$ by

The Borsuk-Ulam theorem is the following:

Note that although the theorem is originally stated on domain $S^{n}$, it is also true when the domain of $f$ is the surface of the cross-polytope $C^{n}$.

In general, a subdivision or simplicization is a partition of a geometric object into small objects such that any two such small objects either share a common facet or do not intersect. In particular, we have the following definitions:

A triangulation $T$ of a geometric object $X$ is a collection of (distinct) $n$-simplices $\sigma_{1},\ldots,\sigma_{m}$ whose union is $X$ such that for all $i$ and $j$, $\sigma_{i}\cap\sigma_{j}$ either contains a common facet of $\sigma_{i}$ and $\sigma_{j}$ or a lower dimension face, or is empty.

The mesh size $\tau$ of a triangulation $T$ is the maximum distance between any two vertices of $T$.

A triangulation $T$ of $S^{n}$ is centrally symmetric if given simplex $\sigma\in T\cap S^{n}$, then $-\sigma\in T\cap S^{n}$, where $-\sigma$ is the simplex obtained by negating each vertices of $\sigma$. The notion can also be defined on other centrally symmetric objects, e.g., on $C^{n}$. The $d$-skeleton of a triangulation $T$ is the collection of simplices of $T$ of dimension at most $d$, i.e. $\{\sigma\in T:\text{dim}(\sigma)\leq d\}$.

Tucker’s Lemma can be formulated in a number of different ways; one is the following.

Let $T$ be an centrally symmetric triangulation of $C^{n}$ whose vertices are assigned labels from $\{+1,-1,+2,-2,\ldots,+n,-n\}$. The labels of antipodal vertices sum to zero, i.e., the labelling function $\lambda$ satisfies $\lambda(-{\bf x})=\lambda({\bf x})$ for any vertex ${\bf x}\in C^{n}$. Then there must exist a 1-simplex (which is referred to as a complementary edge) such that its two vertices have labels that sum to zero.

As pointed out in the literature , the lemma is often stated for a triangulation of a ball, but for it also holds for a triangulation of a sphere (obtained by gluing two $n$-balls along their boundaries, see or for more details). We are interested in triangulations that satisfy the following property.

A flag of hemispheres in $S^{n}$ is a sequence $H_{0}\subset\dots\subset H_{n}$ where each $H_{d}$ is homeomorphic to a $d$-ball, and for $1\leq d\leq n$, $\partial H_{d}=\partial(-H_{d})=H_{d}\cap(-H_{d})=H_{d-1}\cup(-H_{d-1})\approxeq S^{d-1}$, $H_{n}\cap(-H_{n})=S^{n}$, and $H_{0},-H_{0}$ are antipodal points. A symmetric triangulation $T$ of $S^{n}$ is said to be aligned with hemispheres if we can find a flag of hemispheres such that $H_{d}$ is contained in the $d$-skeleton of the triangulation.

Note that the same definition can be adapted to our context by converting $l_{2}$-norm to $l_{1}$-norm. We can now define the computational version of the Tucker problem.

$(n,T)$-Tucker. Let $T$ be a fixed centrally symmetric triangulation of mesh size $\tau$ (that is aligned with hemispheres). Given an integer $n$ and a polynomial-size circuit $\lambda$ that computes for each vertex $x$ on $T$ a label $\lambda:T\rightarrow\{+1,-1,\cdots,+n,-n\}$ such that $\lambda(-{\bf x})+\lambda({\bf x})=0$, find two adjacent vertices ${\bf z}$, ${\bf z}^{\prime}$ of $T$, with $\lambda({\bf z})+\lambda({\bf z}^{\prime})=0$.

By “fixed” here we mean that the circuit $\lambda$ knows how the vertices of the triangulation are represented as inputs and can produce a label for them. Such a triangulation can be constructed, e.g. see . Note that the triangulation $T$ is not given explicitly as input to the problem, but it is rather accessed via the labelling circuit, therefore solutions that exhaustively search over the vertices of $T$ for complementary edges are not efficient.

2 From Consensus-halving to Tucker

First, we establish the reduction from Consensus-Halving to Tucker.

$(n,n,\epsilon)$-ConHalving reduces to $(n,T)$-Tucker in polynomial time, where $T$ is a symmetric triangulation $T$ of $C^{n}$ with mesh size at most $\epsilon/2M$ and $M$ is the upper bound on the valuation functions of $(n,n,\epsilon)$-ConHalving.

Given any instance of $(n,n,\epsilon)$-ConHalving, we construct an instance of $(n,T)$-Tucker based on the construction in . We note that the coordinates of any vertex ${\mathbf{x}}\in C^{n}$ naturally correspond to a partition that uses $n$ cuts on the $$interval.The use of the$$ interval is for convenience and without loss of generality; for any choice of the interval we could use a cross-polytope corresponding to a sphere of a different radius. This is because the coordinates of any vertex ${\mathbf{x}}\in C^{n}$ satisfy $\sum_{i=1}^{n+1}|x_{i}|=1$, and a partition with $n$ cuts on $$can be interpreted as partitioning the interval into$n+1$pieces such that the length of each piece is equal to$|x_{i}|,i=1,\ldots,n+1$. Furthermore, if the sign of the$i$-th coordinate$x_{i}$is “+”, piece$|x_{i}|$is assigned to portion$O_{+}$; otherwise it is assigned to portion$O_{-}$. This interpertation is the basic bulding block of the Simmons-Su algorithm .