| paper | d4-conf-atal-2021-0250 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete; no algorithm polynomial in \(m,\tau,L\) exists unless \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.2
Given a finite project set \(P\), supported voter types \(\Pi_1,\ldots,\Pi_\tau\) that are partitions of \(P\), positive rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\), and a rational threshold \(q\), does there exist a partition \(S\) of \(P\) such that \(\sum_{i=1}^{\tau}\mu_i\,|\{A\in\Pi_i:A\in S\}|\ge q\)? Equivalently, find a partition \(S\) maximizing this mass-weighted total complementarity utility.
Model a large participatory-budgeting population as a distribution \(\mu\) over complete voter types, each type a partition \(\Pi\) of a fixed project set \(P\). Choose an ordinary partition \(S\) of \(P\) to maximize \(\sum_{\Pi}\mu_{\Pi}\,|\{A\in\Pi:A\in S\}|\); projects remain indivisible, and the population is the continuous object.
The mirror covers the total-utility hardness results Proposition 3.2 and Theorem 4.2. It leaves the egalitarian hardness results, other substitution objectives, and the axiomatic analyses aside.
The strongest mirror is the paper’s substitution aggregation by Total-PA. A voter type is exactly one partition \(\Pi\) of the fixed project set \(P\): it records which projects that voter regards as substitutes. A large city with a fixed participatory-budgeting slate is a plausible regime if residents with similar neighborhood and service needs share a small set of recurring interaction structures. The society is a rational distribution \(\mu\) over those structures, with \(N\gg\tau\), where \(N\) is the population and \(\tau\) the number of distinct partitions represented. Mass means the fraction of residents of each type.
The decision remains an ordinary partition \(S\) of the projects. For each type \(\Pi\), let \(g(\Pi,S)\) count the project pairs on which \(\Pi\) and \(S\) agree about whether the pair belongs together. The continuous problem, Mass-Total-PA, is: given \(P\), the supported partitions \(\Pi_1,\ldots,\Pi_\tau\), their positive rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\), and a rational threshold \(q\), decide whether there is a partition \(S\) with \(\sum_{i=1}^{\tau}\mu_i g(\Pi_i,S)\ge q\). Its optimization form asks for a maximizing \(S\). The mass is only in the population; projects are not divided.
The anchor is Proposition 3.2: “Total-PA is NP-hard even for three voters.” The paper obtains this from the cited NP-hardness of Consensus Clustering with three partitions [7]; it is not a new hardness reduction in this paper. The mass version preserves the result exactly: for any discrete profile, assign each distinct partition the fraction of voters who submitted it. The continuous objective is the discrete total utility divided by the number of voters, so its maximizers are unchanged. In the hard three-voter instances, \(\tau\le3\); repeating each voter any number of times gives arbitrarily large populations with the same type masses. This is a particularly clean Class B case: the hardness already occurs with three voter types, so it comes from the project-partitioning combinatorics, not from population multiplicity. It is also my lead anchor: the paper’s own Total-PA objective transfers without changing the question.
A second, independently credible mirror is Mass-Total-COMP, for complementarity aggregation. Here a type is again a voter’s complete partition, now interpreted as the complementarity classes they believe must be funded together. For a voter type \(\Pi\), define \(h(\Pi,S)=|\{A\in\Pi:A\in S\}|\), the number of that type’s exact classes appearing in \(S\). Given the same distributional input, the problem is to find a partition \(S\) maximizing \(\sum_i\mu_i h(\Pi_i,S)\), or decide whether the value reaches a supplied rational threshold.
Its anchor is Theorem 4.2: “Total-COMP is NP-hard.” This theorem is proved in the paper by reduction from Set Packing. The same normalization of a discrete voter profile into type masses preserves its maximizing partition, so the theorem gives hardness for the continuous problem too. Replicating a profile yields large finite populations without increasing its support. This is also Class B: the underlying set-packing choices over projects carry the hardness. A concrete setting is a large regional budget in which residents share views about which facilities and connecting infrastructure form indivisible complementary packages.
For both mirrors, the type is complete for the paper’s model: its partition determines the voter’s input and utility. Weighting each type by its population share preserves the paper’s utilitarian objective as a per-capita objective. The authors should recognize these as their aggregation problems with a high-multiplicity population representation, rather than as a change to the outcome space. The scope here is specifically the two named total-utility hardness results; it does not claim to continuize the paper’s egalitarian variants or its axiomatic analysis.
My weakest point is the regime’s plausibility. The paper’s motivating procedure may ask only a small set of secretaries for partitions, and exact agreement on a full partition can be a demanding assumption when the project slate is large. The mirror is most convincing for a fixed, reasonably standardized slate and a population with recurring neighborhood or service profiles; it should not be sold as fitting every PB process. Even there, Proposition 3.2 makes the computational case unusually sturdy: its hardness survives with at most three types, so the argument does not depend on claiming that a vast population has a vast number of distinct opinions. The next questions are whether restricted project slates yield useful approximation or parameterized algorithms for either objective, and which structural restrictions on the supported partitions make exact aggregation tractable.
The strongest case against the Total-PA anchor is that its continuous version is exactly weighted consensus clustering. For each project pair \(\{x,y\}\), the distribution \(\mu\) reduces to one agreement frequency \(a_{xy}=\sum_t\mu_t\mathbf{1}[x\sim_{\Pi_t}y]\); Mass-Total-PA then maximizes
\[
\sum_{\{x,y\}}\left(a_{xy}\mathbf{1}[x\sim_S y]+(1-a_{xy})\mathbf{1}[x\not\sim_S y]\right).
\]
That is weighted pairwise clustering agreement. Gionis et al. explicitly study weighted partition aggregation and its correlation-clustering formulation, so this is hard to present as a new computational formulation ([*Clustering Aggregation*](https://www.cs.uoi.gr/~tsap/publications/p1-gionis.pdf)). The objection is limited, though: under the programme’s stated rule, existing work on weighted or repeated types is evidence that the regime is sensible. It defeats the novelty pitch more readily than it defeats the mirror.
Total-COMP compresses just as sharply. Let \(w_A=\sum_t\mu_t\mathbf{1}[A\in\Pi_t]\). Its objective is \(\sum_{A\in S}w_A\), so the optimization is maximum-weight set packing over the reported parts, with leftover projects grouped into a zero-value part. The paper’s own reduction identifies this packing structure. That makes the continuous population contribute weights, not a new kind of computational machinery. Still, the masses remain meaningful rational inputs, and a familiar formulation does not by itself make the question out of scope.
The scenario objection is also weaker than it first appears. The paper’s motivating procedure asks a small group of secretaries because elicitation is costly; exact partitions over a large slate could be an awkward survey for residents. But a fixed slate and recurring neighborhood or service profiles give a plausible large-population setting. A partition is a complete type for these objectives, neither total objective tracks individual identity, and the weighted optimum need not degenerate. The three-type hard instances for Total-PA even allow a large population with very small support.
So the honest negative case is weak. I would argue that Total-PA offers little new computational territory given weighted clustering, and that Total-COMP is a population-weighted version of a familiar packing problem. I cannot honestly defeat the proposed Mass-Total-COMP mirror: it remains a coherent continuous-population question under the programme’s rules. The stronger scenario for Total-PA also survives unless the prior weighted-clustering literature is judged to be a genuine collision with the continuous-population model.
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.