| paper | d4-conf-aaai-2013-0050 |
| 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 · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 9
statement extracted from the paper’s text layer
Given candidates \(C\), a rational background distribution \(b\) over rankings, strategic mass \(\delta>0\) with \(\sum_\rho b_\rho+\delta=1\), preferred candidate \(p\), and threshold \(q\), choose one common report \(\sigma\in\mathcal R(C)\) for the strategic mass. Is \(\max_{\sigma\in\mathcal R(C)}\Pr_{\nu^\sigma}[p\text{ wins under RV-Borda}]\ge q\), where \(\nu^\sigma_\rho=b_\rho+\delta\mathbf 1[\rho=\sigma]\) and a voter is sampled by mass before selecting their highest-ranked Borda co-winner?
Types are strict rankings \(\rho\in\mathcal R(C)\), with fixed mass \(b_\rho\) and a distinguished strategic cohort of mass \(\delta\) choosing one report \(\sigma\). The decision objective is to meet threshold \(q\) for the probability that the mass-sampled ballot ranks \(p\) highest among the Borda co-winners.
The mirror covers Theorem 9’s Borda manipulation result through homogeneous strategic blocs; it leaves the other voting rules, tie-breaking comparisons, and empirical results aside.
The strongest anchor is Theorem 9, proved in this paper: the non-deterministic manipulation problem for Borda with random-vote tie-breaking is NP-complete. The instance has \(n-1\) fixed votes, a preferred candidate \(p\), and a probability threshold \(t\); the question is whether one remaining vote can be cast so that \(p\) wins with probability at least \(t\). The paper proves this by a reduction from MINSAT.
A continuous counterpart is RV-Borda Bloc-Mass Manipulation. Let \(C\) be the candidates and \(\mathcal R(C)\) the strict rankings of \(C\). An instance gives a rational background mass distribution \(b\) over reported rankings, a rational strategic mass \(\delta>0\) with \(\sum_\rho b_\rho+\delta=1\), a preferred candidate \(p\), and a rational threshold \(q\). The strategic mass is a homogeneous cohort: its members share a sincere ranking with \(p\) first and commit to one common reported ranking \(\sigma\). The resulting society is \(\nu^\sigma_\rho=b_\rho+\delta\mathbf 1[\rho=\sigma]\). Its Borda score is \(\mathrm{sc}_{\nu^\sigma}(c)=\sum_{\rho\in\mathcal R(C)}\nu^\sigma_\rho\bigl(m-\operatorname{pos}_\rho(c)\bigr)\), and its co-winner set \(W\) consists of the candidates with maximum score. A random vote means sampling a member by mass and electing that ballot’s highest-ranked candidate in \(W\). Thus \(p\)’s winning probability is \(\sum_{\rho:\operatorname{top}_\rho(W)=p}\nu^\sigma_\rho\). The question is whether some report \(\sigma\) makes this probability at least \(q\); a solution is such a ranking.
A plausible regime is a large party or membership election where many people share each of a relatively small set of complete rankings, and a coordinated caucus shares preferences and submits one common strategic ballot. The mass of each type is its fraction of the electorate. For any rational mass instance, a sufficiently large common denominator gives a finite realization with \(N\) agents and \(N\gg\tau\), where \(\tau\) is the number of supported rankings; the strategic cohort also grows with \(N\).
The hardness connection is exact. From a Theorem 9 instance with \(n\) voters, set \(\delta=1/n\) and let \(b_\rho\) equal the number of fixed votes of ranking \(\rho\), divided by \(n\). Every report has the same co-winners as in the discrete election, since all Borda scores are scaled by \(1/n\); the random-vote probability is the same fraction of votes. Replicating the whole profile gives arbitrarily many members per type while preserving the mass instance. The continuous problem is also in NP: a report ranking is a certificate, and its Borda scores and winning probability can be computed from the listed rational masses. I therefore expect this problem to be NP-complete, a Class B mirror: the reduction’s combinatorics concern alternatives and rankings, and the discrete problem embeds directly.
This case covers Theorem 9 only. It leaves open how the complexity changes if a cohort can split its mass among several reports, or under restrictions such as bounded \(\tau\), or if the task is to find the minimum strategic mass needed to reach a threshold.
The weakest point is the move from one manipulator to a coordinated cohort that shares a report. The paper proves Theorem 9 for one voter; the bloc version is a high-multiplicity extension, and its plausibility depends on whether the authors accept coordinated homogeneous voters as the relevant strategic unit. The exact embedding and the mass-based interpretation of random-vote tie-breaking are what make this extension a credible mirror.
The only anchor raised is Theorem 9, and the strongest objection is that its manipulator is one individual while the proposed mirror gives a positive mass of voters a coordinated common report. In a nonatomic society, one person has zero mass: changing their ballot cannot change Borda scores or the random-vote distribution. Preserving the manipulator’s influence therefore means modeling a bloc, or keeping a distinguished atom in a hybrid continuum-and-atom model. Neither is literally the paper’s single-voter problem.
That objection is a real modeling caveat, but it does not defeat the mirror. A coordinated caucus with a shared interest is plausible, and the mass-transfer definition preserves both the Borda winner condition and the probability induced by sampling a voter. For rational masses, the instance also has an exact finite realization; replicating that profile gives arbitrarily many voters of each type. The programme explicitly treats such high-multiplicity formulations as supporting evidence, not as a collision or a scope violation.
Letting the strategic bloc split its mass among different reports would be a further, recognizable coalition-manipulation question. The shift from one manipulator to coordinated mass is substantial, but it does not make the computational question ill-posed or obviously unworthy. I cannot honestly defeat this anchor: the negative case against the paper is weak, and the proposed mirror survives the strongest objection available.
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.