| paper | Consensus Halving for Sets of Items |
| authors | P. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, Warut Suksompong |
| venue | WINE 2020 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.1
statement extracted from the paper’s text layer
Given \(m\) items, a rational distribution \(\mu\) over \(\tau\) positive-mass symmetric-threshold utility types with values \(u_t(j)\) and caps \(c_{tj}\), and the fixed constant \(\varepsilon\), find \(x\in[0,1]^m\) with \(\kappa(x)=|\{j:0<x_j<1\}|\leq\tau\) such that every type \(t\) satisfies \(\left|\sum_j f_{tj}(x_j)u_t(j)-\sum_j f_{tj}(1-x_j)u_t(j)\right|\leq\varepsilon\sum_j u_t(j)\).
A finite item catalogue with complete symmetric-threshold utility types \(t\), population distribution \(\mu\), and item-fraction decision vector \(x\); find a feasible division with at most \(\tau\) cut items satisfying every positive-mass type, with no objective beyond feasibility under the cut budget.
The reduction uses one bespoke utility type per circuit constraint, so the mirror is a support-compressed high-multiplicity formulation rather than a mass-sensitive aggregate model.
fatal: False
The mirror covers Theorems 2.2, 2.4, and 3.1, including additive consensus halving, minimum-cut approximation, and symmetric-threshold hardness; it leaves agreeable sets, consensus \(k\)-splitting, and line-ordered variants aside.
The strongest positive case is a genuine high-multiplicity version of the paper’s consensus-halving problem. I would not average agents’ utilities: that would weaken the paper’s question. Instead, a type is a complete utility description, and every positive-mass type must be treated fairly.
Let \(M=[m]\) be the item set and let \(\mathcal T=[\tau]\) be the set of utility types. The society is a rational distribution \(\mu\in\mathbb Q^\tau\), where \(\mu_t\) is the fraction of the population with type \(t\). A finite population with \(R\mu_t\) agents of type \(t\) is the denominator-cleared realization. Thus \(R\) may be enormous while \(\tau\) remains moderate.
A candidate division is \(x\in[0,1]^m\): item \(j\) contributes fraction \(x_j\) to the first part and \(1-x_j\) to the second. For additive type \(t\), write \(U_t(x)=\sum_j u_t(j)x_j\). The division is a continuous-population consensus halving if \(U_t(x)=U_t(\mathbf 1-x)\) for every \(t\) with \(\mu_t>0\). Its number of cuts is \(\kappa(x)=|\{j:0<x_j<1\}|\). The fractional \(x\) is retained because fractional item ownership is already the paper’s underlying resource model; the new continuous object is the population distribution \(\mu\), not the outcome space.
My lead anchor is Theorem 3.1, proved in this paper. It states that there is a constant \(\varepsilon>0\) such that finding an \(\varepsilon\)-approximate consensus halving for \(n\) agents with monotonic utilities, using at most \(n\) cuts, is PPAD-hard, even when every utility is symmetric-threshold. These utilities are additive over items, but each item has a lower cap \(c_{ij}\), contributes nothing below that cap, grows linearly between \(c_{ij}\) and \(1-c_{ij}\), and saturates above \(1-c_{ij}\).
The corresponding continuous problem is:
\[ \textsc{Symmetric-Threshold-Consensus-Halving}_{\infty} \]
Given \(m\) items, a rational distribution \(\mu\) over \(\tau\) symmetric-threshold utility types, and the fixed constant \(\varepsilon\), find \(x\in[0,1]^m\) such that \(\kappa(x)\leq\tau\) and, for every positive-mass type \(t\),
\[ \left| \sum_j f_{tj}(x_j)u_t(j) - \sum_j f_{tj}(1-x_j)u_t(j) \right| \leq \varepsilon\sum_j u_t(j). \]
A solution is the vector \(x\), or equivalently the two fractional parts it defines. This is recognisably the paper’s problem: the same items, the same cuts, the same symmetric-threshold utilities, the same approximation guarantee, and the same requirement that every agent—or, in the continuum, every positive-mass type—be satisfied.
The regime is plausible for large organizations or populations repeatedly evaluating a common catalogue of facilities, assets, or public resources. There may be millions of people, but only \(\tau\) recurring preference-and-cap profiles: for example, many members of each organizational role share the same valuation and the same minimum usable share of each facility. The type includes the entire vector of values and caps, so this is genuine high multiplicity rather than pretending idiosyncratic agents are identical.
I expect this problem to be Class B: PPAD-hardness transfers. Take the paper’s hard instance, make each distinct agent utility a type, and assign every type positive mass, say \(\mu_t=1/\tau\). Alternatively, replicate every type \(R\) times, making the finite population \(R\tau\) while preserving exactly the same continuous input. Any solution to the continuous problem solves the paper’s hard instance. The circuit’s combinatorics live in the utility types and item coordinates, not in the fact that agents have distinct names. The paper’s Theorem 3.1 is proved here, although its Lemma 3.4 ultimately uses the cited hardness of generalized circuits.
This anchor generates worthwhile questions rather than merely restating a theorem: is the problem PPA-complete, as the paper asks? Is it PPAD-complete? Does hardness persist under a much smaller number of utility types, or under a restricted common catalogue of caps? What happens if one asks for a specified mass of agents to be approximately satisfied rather than requiring every positive-mass type to be satisfied?
A second strong anchor is Theorem 2.4, also proved here. It states that, for \(n\) agents with additive utilities, it is NP-hard to compute a consensus halving using at most \(n-1\) cuts more than the minimum possible. The proof reduces from Partition: agent \(i\) values only its own disjoint block of items, with item values \(w_1,\ldots,w_r\). If the weights partition equally, zero cuts suffice; otherwise every agent must cut at least one item, so at least \(n\) cuts are necessary.
The continuous analogue is:
\[ \textsc{Minimum-Cut-Consensus-Halving}_{\infty} \]
Given \(m\) items, a rational distribution \(\mu\) over \(\tau\) additive utility types, and their rational utility vectors, find an exact support-wise consensus halving minimizing \(\kappa(x)\). The theorem-shaped approximation version asks for a solution satisfying
\[ \kappa(x)\leq \operatorname{OPT}+\tau-1, \]
where \(\operatorname{OPT}\) is the minimum number of cuts for the instance.
This is again a faithful question. The population consists of many repeated members of each valuation cohort, the action is still the paper’s division of items, and the objective is exactly its shared-item overhead. The expected classification is Class B. Use the theorem’s construction with \(\tau=n\) types and, if desired, replicate each type arbitrarily many times. In a yes-instance, \(\operatorname{OPT}=0\), so the \(\tau-1\)-additive guarantee must return a zero-cut solution. In a no-instance, every type’s disjoint block requires a cut, so at least \(\tau\) cuts are necessary. Thus Partition hardness survives the population continuation.
The cleanest algorithmic boundary is Theorem 2.2, also proved here: for \(n\) additive agents, a polynomial-time algorithm computes a consensus halving with at most \(\min\{n,m\}\) cuts. Its continuous version replaces the \(n\) agents by \(\tau\) positive-mass utility types and asks for an exact halving with at most \(\min\{\tau,m\}\) cuts. The same Gaussian-elimination/vertex argument gives a polynomial-time algorithm in \(m\), \(\tau\), and the encoding length. This is Class A, while minimum-cut optimization remains Class B. Together these results give the continuous mirror a meaningful tractability boundary rather than a single contrived formulation.
The scope is deliberately limited to Sections 2 and 3: additive consensus halving, minimum-cut consensus halving, and symmetric-threshold consensus halving. I am not claiming that the agreeable-set or consensus-\(k\)-splitting results automatically continue; those would require separate mirrors.
The weakest point is that exact support-wise consensus halving depends on which types have positive mass, not on the numerical values of their masses. A sceptic can therefore call this a type-compressed high-multiplicity reformulation rather than a mass-sensitive new theory. I concede that limitation. But it is precisely the high-multiplicity regime the programme asks us to test: millions of indistinguishable agents collapse to a finite distribution of complete types, while the paper’s item-level computational structure remains intact. The resulting questions are mathematically faithful, scenically plausible, and—on the hardness side—show that continuization need not dissolve discrete difficulty.
The strongest negative case is that consensus halving is not an aggregate population problem. It is a system of universal constraints imposed by agents on one common division. If \(d_t(x)\) denotes the utility imbalance of type \(t\), the proposed continuous condition is simply
\[ |d_t(x)|\leq \varepsilon \qquad\text{for every }t\in\operatorname{supp}(\mu). \]
Consequently, two distributions with the same support but completely different masses induce exactly the same feasible divisions, optimum number of cuts, and complexity. Replicating every type \(R\) times changes nothing. The distribution is only a compressed encoding of a list of constraints; it is not an operative part of the problem. That is fundamentally different from voting, bribery, or matching, where masses enter scores, supplies, costs, or feasibility.
This defeats the proposed reading of Theorem 3.1 as a continuous-population hardness result. The PPAD reduction creates a bespoke agent for each circuit constraint. The agent’s values and thresholds encode a wire or gate. Replacing each such agent by a type and giving it positive mass preserves the reduction, but only because the support still contains one distinct type per gate. Cloning those types to create millions of people contributes no computational or mathematical content. The hardness is inherited unchanged from the finite constraint system.
A stronger proposed mirror would seek a small, fixed catalogue of types, or a genuinely continuous family of cap/value profiles. But the reduction gives no support for that: it needs separate utility descriptions to enforce the separate circuit constraints. A parametric continuum of profiles would instead be a new semi-infinite constraint problem requiring its own representation and separation theory. It would not be a continuization of the theorem as stated.
Theorem 2.4 is even less suitable as a population anchor. Its hardness already exists with one agent. Taking \(n=1\), the claimed \(n-1\)-additive guarantee is an exact minimum-cut solution, and the proof reduces Partition to deciding whether zero cuts suffice. Thus the continuous version can have
\[ \tau=1,\qquad \mu_1=1, \]
while retaining the full hardness. This is not an objection that the answer remains hard; hardness is perfectly acceptable. It shows instead that the hardness has no population dimension whatsoever. It is caused by the item values and the requirement to avoid fractional items.
The proponent’s \(n\)-type construction does not improve matters. The types have disjoint private item blocks, and Partition is encoded inside each block. Repeating each type merely duplicates the same constraint. The high-multiplicity scenario may be narratively plausible, but the population is computationally irrelevant.
Theorem 2.2 supplies an algorithmic boundary, but not a continuous-population one. Its Gaussian-elimination argument already operates on the matrix of utility rows. If identical agents are grouped, one simply removes duplicate rows and replaces \(n\) by the number of distinct constraints, or more sharply by their rank. This is routine preprocessing of the finite problem. The masses \(\mu_t\) are never read by the algorithm. Calling the resulting bound \(\min\{\tau,m\}\) is a useful compressed formulation, but not a new continuous optimization phenomenon.
One could make the masses matter by changing the fairness requirement. For example, one might require only a \(q\)-fraction of the population to be satisfied, or minimize a mass-weighted imbalance. But that no longer mirrors consensus halving, whose defining requirement is that every agent value the two parts equally. In the additive case, replacing individual constraints by the single weighted condition
\[ \sum_t \mu_t\bigl(U_t(x)-U_t(\mathbf 1-x)\bigr)=0 \]
collapses all types into one average valuation. It is then just one linear equation; a basic feasible solution has at most one fractional item. The paper’s individual-fairness structure, and hence its reductions, disappear.
A quota version could certainly be an interesting new partial-fairness problem. But it would need an independent motivation and complexity theory. It cannot rescue these three anchors as mirrors of the paper: the gate types in the PPAD reduction could be ignored if they carry insufficient mass, while the one-type Partition reduction loses its population content entirely.
The honest weakness of this negative case is that the proposed support-wise model is a legitimate high-multiplicity encoding. A society with many repeated valuation profiles is not nonsensical, and the resulting questions are formally well posed. What fails is the claim that they are worthwhile continuous-population mirrors: in every faithful version of the paper’s universal consensus requirement, \(\mu\) is a dead parameter, and all three anchored results reduce to the original item-level problem after deduplicating agents. If the programme accepts any such support-compressed high-multiplicity formulation, the paper should pass; under a stricter requirement that the population distribution actually affect the computational question, none of the proposed anchors survives.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.