| paper | d4-conf-ijcai-2016-0659 |
| 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→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), approval types \(\mathcal T\subseteq\binom{C}{6}\), and positive rational masses \(\mu_S\) summing to \(1\), is there a split \(x_S\in[0,\mu_S]\) and distinct candidates \(p,q\in C\) such that \(p\) uniquely wins the first group and \(q\) uniquely wins the second? Equivalently, can one maximize \(\delta\) subject to \(\sum_{S\ni p}x_S\ge\sum_{S\ni c}x_S+\delta\) for every \(c\ne p\), and \(\sum_{S\ni q}(\mu_S-x_S)\ge\sum_{S\ni c}(\mu_S-x_S)+\delta\) for every \(c\ne q\), with optimum \(\delta>0\)?
The society is a distribution over six-approval types with rational masses. The decision variables \(x_S\) allocate each type’s mass between two groups; the question is feasibility of distinct unique approval winners, equivalently whether the maximum common winning margin is positive. Enumerating ordered winner pairs and solving the resulting linear programs gives a polynomial-time algorithm in \(m\), \(\tau\), and the input bit length.
The reductions use many distinct set ballots and therefore do not show that the paper’s hardness arises in a large-electorate, low-support regime; this limits what the results reveal about the source of hardness.
fatal: False
The mirror covers Theorems 8 and 5. It leaves the paper’s other tractability and hardness results, including the MAXGAP, SIZED, and parameterized results, unmirrored.
The cleanest mirror is 6-Approval Two-Group Formation. Theorem 8 states: “6-APPROVAL-2-PARTITION is NP-hard.” This theorem is proved in the paper by reduction from RESTRICTED EXACT COVER BY 3-SETS, whose NP-hardness is cited to Gonzalez (1985).
For the continuous version, an instance gives a finite candidate set \(C\) and a list \(\mathcal T\subseteq\binom{C}{6}\) of the \(\tau\) approval types present, with rational masses \(\mu_S>0\) summing to \(1\). A type \(S\) is the complete approval ballot of every agent in that type; \(\mu_S\) is its fraction of the population. The question is whether the population can be divided into two groups with distinct unique approval winners. A solution specifies the winners \(p,q\in C\), \(p\ne q\), and, for each type \(S\), how much mass \(x_S\in[0,\mu_S]\) goes to the first group; the remaining mass goes to the second. The required conditions are
\[
\sum_{S\ni p}x_S>\sum_{S\ni c}x_S\quad(c\ne p),
\qquad
\sum_{S\ni q}(\mu_S-x_S)>\sum_{S\ni c}(\mu_S-x_S)\quad(c\ne q).
\]
This is the paper’s decision question in mass terms: both groups must form, and each must have a different unique approval winner. There is no extra objective. To decide it, enumerate the \(m(m-1)\) ordered pairs \(p,q\) and use an LP to maximize a common margin \(\delta\) subject to both sets of inequalities having margin at least \(\delta\). A positive optimum is exactly a valid division. Each LP has \(\tau\) allocation variables and \(O(m)\) constraints, so the mirror is solvable in time polynomial in \(m,\tau,L\).
The regime is a large electorate forming preference-based virtual districts, as in the paper’s own motivation. For example, a very large population may cast ballots from a relatively small set of six-approval types, so the number of people \(N\) is far larger than the support size \(\tau\). Agents with the same approval set are indistinguishable for this problem; in a continuum, their type mass can be split between districts. The candidate set and approval rule stay finite. Only the population becomes continuous.
A second, narrower anchor is Theorem 5, which states that “3-APPROVAL-PRESELECTED-2-PARTITION is NP-hard.” This is also a result proved in the paper; its proof is omitted in the supplied text, and Remark 1 says the Theorem 8 reduction adapts by fixing the two leaders and removing the auxiliary candidates \(x'_i\). Its continuous mirror gives the instance a finite support of three-approval types with rational masses and two distinct prescribed leaders \(p,q\). It asks for an allocation \(x_S\in[0,\mu_S]\) such that \(p\) uniquely wins the first group and \(q\) uniquely wins the second, using the same inequalities above. Here there is only one leader pair to check, so one margin-maximizing LP decides the question in polynomial time.
Both mirrors are Class A candidates: the hardness in the named finite results appears tied to assigning indivisible voters. The paper’s Theorem 8 construction starts from set-voters for an exact-cover instance; fractional mass assignment can divide a type across the two groups. Theorem 5 shows the same continuous formulation applies when the leaders are fixed and voters approve only three candidates. Theorem 8 is my lead because it mirrors the paper’s basic, non-preselected problem.
The authors have a strong reason to recognize these as their problems: the continuous versions preserve the task they define—partition voters into groups so each has a distinct unique approval winner—and follow their virtual-district motivation. The weakest point is also clear: their formal instances partition indivisible voters, while these mirrors let a type’s mass be divided. An author or referee could judge that change too consequential. It is precisely the high-multiplicity relaxation, though, and it fits the large-electorate scenario better than a small committee does.
This mirror covers Theorems 8 and 5. It does not claim to mirror every result in the paper. It raises useful next questions: how large a continuous winning margin guarantees a discrete partition after rounding allocations to whole voters, and where complexity returns when the number of groups is part of the input.
I cannot honestly defeat either anchor on the grounds available. Theorem 8 is an explicit NP-hardness result for the basic two-group problem, and Theorem 5 is an explicit NP-hardness result with leaders fixed in advance. In both cases, an approval set completely describes a voter for the question the paper asks. Dividing a large cohort with the same ballot between groups is a coherent population-level version of partitioning voters. The proposed mirrors preserve the paper’s central task.
The strongest reservation is about how closely these mirrors connect to the paper’s hardness results. Theorem 8’s exact-cover reduction gives a voter to each set, so its hard instances encode combinatorial structure across many distinct ballots; Theorem 5 uses essentially the same construction. Those instances do not show that the hardness arises in a regime with many agents per type. A continuous mirror can still be sensible in a different, large-electorate regime, but the paper’s reductions provide little evidence that this regime captures the source of its hardness.
There is also a limit issue: unique-winner margins are normalized by population size, so discrete partitions with a fixed score gap can have margins tending to zero as the electorate grows. The continuous question of whether some allocation has a *strictly positive* margin is therefore not a reliable limit test for whether every large finite instance has a discrete partition. Requiring a margin bounded away from zero would address robustness, but it would be a different, max-gap question.
Those points qualify the value of the mirrors; they do not rule them out. The type-based population scenario is plausible, the mirrors ask named computational questions, and neither is already answered by the paper’s analytic or axiomatic background. My case against is weak: the proponent’s two anchors survive, with the caveat that their connection to the paper’s hard instances is less direct than claimed.
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.