| paper | d4-conf-aaai-2011-0313 |
| 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: \(\mathrm{P}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.
statement extracted from the paper’s text layer
Given \(C=\{a,b,c,p\}\), rational nonmanipulator masses \(\mu_{w,\pi}\) over weight-and-ranking types \((w,\pi)\), and rational manipulator masses \(\lambda_w\) for each strength class on the same population scale, does there exist \(x_{w,\pi}\geq 0\) with \(\sum_{\pi\in L(C)}x_{w,\pi}=\lambda_w\) for every \(w\), such that \(p\) wins under Nanson's rule? In each round, compute weighted Borda scores on the remaining candidates using contributions \(w(\mu_{w,\pi}+x_{w,\pi})\), then eliminate candidates below the average score.
Types are voting strength \(w\) and ranking \(\pi\); the society is given by rational nonmanipulator masses \(\mu_{w,\pi}\) and strategic mass \(\lambda_w\) for each strength class. The decision variables \(x_{w,\pi}\) allocate each class's mass among reported rankings, and the objective is feasibility: make \(p\) the Nanson winner.
The mirror covers weighted Nanson manipulation with four candidates (Theorem 3). It leaves the unweighted results for Nanson and Baldwin, Nanson's three-candidate result, Baldwin's results, and the approximation and experimental results untouched.
I would lead with Theorem 3, proved in this paper: for Nanson’s rule with weighted votes, deciding whether a coalition can make its preferred candidate win is NP-complete even with exactly four candidates. The input gives the non-manipulators’ weighted votes, the target candidate, and the manipulators’ weights; the question is whether they can choose ballots that make the target win. The paper proves this by reduction from PARTITION.
A natural regime for its continuous mirror is a large federation whose members vote under Nanson’s rule and whose voting strengths fall into a modest number of classes. A non-manipulator type is a pair \((w,\pi)\): per-member voting strength \(w\) and ranking \(\pi\). Its mass records how much of the electorate has that type. The manipulating bloc shares a target \(p\); within each strength class its members are interchangeable. There may be many members but relatively few types. This is a population-mass model of weighted votes, not a model of fractional outcomes.
Call the problem Four-Candidate Continuous Nanson Manipulation. Its input is \(C=\{a,b,c,p\}\), a rational non-manipulator distribution \(\mu\) over types \((w,\pi)\), and rational masses \(\lambda_w\) for the manipulating bloc’s strength classes. The action is to choose \(x_{w,\pi}\geq 0\), the mass of strength class \(w\) reporting ranking \(\pi\), with \(\sum_{\pi\in L(C)}x_{w,\pi}=\lambda_w\) for each \(w\). Ask whether some such allocation makes \(p\) the Nanson winner. At each round, calculate the weighted Borda scores on the remaining candidates, using contributions \(w(\mu_{w,\pi}+x_{w,\pi})\), and eliminate candidates below the average score, with the paper’s tie-breaking convention. A solution is a feasible allocation \(x\); this is a feasibility question, not a cost-minimization problem.
I expect this mirror to be tractable, in Class A. With four candidates there are only 24 possible reported rankings and a constant number of possible elimination sequences. For any proposed sequence, every score and every condition for an elimination round is linear in \(x\). Testing the resulting rational linear constraints gives a polynomial-time algorithm in the input size and number of types. The PARTITION reduction relies on assigning each manipulator’s whole weight to a ballot; the continuous variables can split mass across ballots, so that indivisibility disappears.
The weakest point is also the key modeling change: Theorem 3’s manipulators are atomic, and the PARTITION construction may give each one a distinct weight. The mirror lets mass within a strength class divide among reports, so it does not preserve the reduction’s exact instances. It is most convincing when voting weights represent population share or a genuinely large cohort, rather than a list of indivisible delegates. That seems like a defensible continuous version of the authors’ weighted manipulation problem, but it is not a claim that the theorem’s hardness instances themselves are high-multiplicity instances.
This case covers Theorem 3 only; I would not stretch it to the unweighted single-manipulator results or the paper’s approximation experiments. It also raises two useful follow-up questions: does the continuous Nanson problem remain tractable when the candidate count is part of the input, and can solutions to the continuous problem be rounded to discrete weighted coalitions with a useful guarantee?
Theorem 3 is a valid computational anchor: it proves NP-completeness for weighted Nanson manipulation with four candidates. The strongest objection is that its hardness comes from assigning each manipulator’s whole, individually specified weight to a ballot. In the exact-cover-free high multiplicity regime—many manipulators sharing a small number of strength classes—the continuous model instead lets each class divide its mass among ballots. The reduction’s PARTITION structure is then absent. Since weight is legitimately part of a type, this is not a complaint that the model forgot identities; it means the theorem’s hard instances do not supply the motivating high multiplicity regime.
That weakens the connection, but it does not invalidate the proposed mirror. A large federation with many members of each voting-strength class is a plausible population model, and its members can report different ballots. With four candidates there are only 24 ballots and a constant number of elimination sequences. For any fixed sequence, the Nanson round conditions are linear in the ballot masses, so the proponent’s feasibility problem reduces to finitely many rational linear programs. That is a direct, well-posed continuous question.
The stronger research version would let the number of candidates grow, or ask for the minimum share of a bloc needed to make its target win. Those are meaningful extensions, but they move beyond Theorem 3’s fixed-four-candidate result; with the candidate count variable, the ballot and elimination-sequence spaces grow sharply. That raises the possibility of a richer algorithmic problem, without establishing that it is worth pursuing.
So the negative case is weak. The four-candidate mirror may be routine, and it does not explain the PARTITION hardness, but the federation scenario is sensible under the programme’s definition. I cannot honestly rule out every worthwhile mirror: this anchor appears to survive as a plausible, likely tractable continuous problem, though its research value is modest unless a broader version yields new structure.
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.