| paper | d4-conf-ijcai-2016-0305 |
| 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}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given binary issues \(X_1,\ldots,X_p\), an explicit finite support of complete conditional approval ballot types \(B\) with acyclic dependency graphs of maximum indegree \(1\), rational masses \(\mu_B>0\) summing to \(1\), and a rational threshold \(q\), does there exist an outcome \(d\in\{0,1\}^p\) such that \(\sum_B \mu_B\delta(d,B)\le q\)?
A normalized high-multiplicity conditional minisum problem: each type is a complete conditional approval ballot, the society is an explicitly listed distribution over those types, and an outcome’s cost is its expected number of disagreements per capita.
The opponent’s best point is that the mirror largely recasts the paper’s existing MAXSAT objective in normalized units, so it may add little algorithmic novelty.
fatal: False
The mirror covers Proposition 1’s hardness for conditional minisum winner determination with binary issues and acyclic, indegree-one dependency graphs. It leaves the paper’s sequential conditional approval results, approximation bounds, and axiomatic properties outside the mirror.
The strongest mirror is a normalized version of conditional minisum winner determination. A type is a complete conditional approval ballot \(B\): its dependency graph and every conditional set of approved values. A continuous society is an explicit support of \(\tau\) such types, each with positive rational mass \(\mu_B\), summing to \(1\). For a feasible outcome \(d\), its per-capita dissatisfaction is
\[
\sum_B \mu_B\,\delta(d,B),
\]
where \(\delta(d,B)\) is the number of variables on which \(d\) disagrees with ballot \(B\).
Continuous Conditional Minisum Winner Determination takes binary issues \(X_1,\ldots,X_p\), such a distribution over ballot types, and a rational threshold \(q\). It asks whether there is an outcome \(d\in\{0,1\}^p\) with \(\sum_B\mu_B\delta(d,B)\le q\); a solution is such an outcome. The lead version restricts each type’s dependency graph to be acyclic with maximum indegree \(1\), matching the hard case in the paper.
The anchor is Proposition 1, proved in this paper by reduction from MAX2SAT. It says that, given a conditional approval profile \(P=(B_1,\ldots,B_n)\) and an integer \(k\), deciding whether some \(d\in D\) has \(\sum_i\delta(d,B_i)\le k\) is NP-complete, even with binary variables and each voter’s dependency graph acyclic with maximum indegree \(1\). The continuous problem preserves that question exactly: assign each distinct ballot \(B\) mass \(\mu_B=|\{i:B_i=B\}|/n\), and set \(q=k/n\). Then the continuous objective is the discrete total disagreement divided by \(n\). The continuous decision problem is also in NP, since a proposed \(d\) can be checked using rational arithmetic. Thus this restriction remains NP-complete.
A plausible high-multiplicity regime is a large membership organization deciding a bundle of linked policies, or a large electorate choosing a combination of public facilities. Many members may share the same complete conditional ballot because they use recurring preference patterns across the same agenda. Here \(N\) is large while \(\tau\), the number of distinct full ballots, can be much smaller. That is a regime for this problem, rather than a claim that all combinatorial voting is high-multiplicity. The authors should recognize the mirror: their rule already evaluates outcomes by summing per-voter disagreements, so replacing voter counts by fractions changes the scale of that same objective, not its meaning.
I expect hardness transfers (Class B). The reduction’s combinatorics lie in the agenda and its clauses, and the discrete instances embed in the distribution model. The result therefore does not show that a continuum dissolves this hardness or creates new hardness for continuum-specific reasons. Further questions include whether the problem is fixed-parameter tractable for parameters such as \(p\), \(\tau\), or dependency-graph width; what approximation guarantees hold for weighted type distributions; and whether useful restricted ballot languages admit efficient algorithms.
The mirror covers Proposition 1’s conditional minisum winner-determination result only. Its weakest point is the population regime: two people share a type only if their entire conditional ballot matches. A story based merely on shared demographics or similar preferences would not suffice, and large electorates may have many distinct ballots. The case is credible where repeated full ballots are plausible, but it does not establish that regime for every application in the paper.
The strongest case against is that Proposition 1 may yield a very small *new* algorithmic story. It is about conditional minisum winner determination, and the paper already translates that problem into MAXSAT. Replacing voter counts with rational weights gives weighted MAXSAT: for a ballot type \(B\) with mass \(\mu_B\), outcome \(d\) has cost \(\sum_B \mu_B\delta(d,B)\). The continuum model seems to expose an existing aggregate objective in normalized units, without bringing the paper’s other results—such as SCAV’s polynomial winner determination—into scope.
That is a concern about the payoff, though, not a sound reason to reject the mirror. Proposition 1 is an explicit computational result. The exact mirror takes a type to be the complete conditional approval ballot, including its dependency graph and approvals, and asks for an outcome minimizing per-capita disagreement. Any discrete profile becomes a distribution by assigning each ballot its count divided by the number of voters; conversely, a rational distribution can be scaled by a common denominator into a discrete profile. The decision versions correspond under the threshold change \(k \mapsto k/n\). No identity-dependent information is lost.
The support-size caveat also does not defeat it. Hard instances may have many ballot types, but duplicating every voter \(M\) times leaves the support size unchanged while making the population arbitrarily large. And exact repetition is plausible in large consultations over a shared agenda where participants use recurring ballot patterns. The requirement that a type capture the full ballot rules out grouping people merely by demographics or similar preferences, but it does not rule out such a regime.
So I cannot honestly make the universal negative case. The mirror appears to be Class B: a useful high-multiplicity question whose hardness survives, even if its first answer follows directly from the paper’s reduction and the continuous version may add little computational novelty. Under the stated standard, neither the apparent rescaling nor the agenda-based source of hardness is enough to dismiss it.
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.