| paper | d4-conf-aaai-2014-0163 |
| 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: \(\mathrm P\), with running time \(\operatorname{poly}(m,\tau,L)\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.10
Given \(m\) candidates, a scoring rule \(f\), a target \(p\), and a finite support of rankings \(\pi\) with binary-rational registered and eligible masses \(r_\pi,u_\pi\), normalized so that \(\sum_\pi(r_\pi+u_\pi)=1\), decide whether there are rational mobilized masses \(x_\pi\) and a budget \(\kappa\) such that \(0\le x_\pi\le u_\pi\), \(\sum_\pi x_\pi\le\kappa\), and \(\sum_\pi(r_\pi+x_\pi)(\alpha^{f,m}_{\operatorname{pos}_\pi(p)}-\alpha^{f,m}_{\operatorname{pos}_\pi(c)})\ge0\) for every candidate \(c\).
A continuous population whose types are complete rankings paired with registered or eligible status, with rational masses for each type. The chair chooses \(x_\pi\) from each eligible type, subject to its available mass; minimize \(\sum_\pi x_\pi\), or ask whether that minimum is at most \(\kappa\), while enforcing that \(p\) is a scoring-rule winner. This is an LP over the supported eligible rankings.
The mirror covers the CCAV hardness cases in Theorem 4.10, including Borda; it does not claim to continue the paper’s descriptive-richness results or its other CCAV cases.
The strongest honest case is a narrow mirror of constructive control by adding voters. The paper’s best anchor is Theorem 4.10, proved in this paper by reduction from 3DM. It says: for every FP-uniform pure rational scoring generator \(f\), if at some candidate count \(m\) its fourth score is strictly greater than its \((m-2)\)nd score, \(\alpha^{f,m}_4>\alpha^{f,m}_{m-2}\), then \(f\)-CCAV is NP-complete. Here \(f\) generates nonincreasing rational scoring vectors in polynomial time, with each vector obtained from the preceding one by inserting a coefficient. In CCAV, given registered voters \(R\), eligible unregistered voters \(U\), a preferred candidate \(p\), and a limit \(k\), the question is whether adding at most \(k\) whole voters from \(U\) makes \(p\) a winner. Borda is a concrete case covered by the theorem: for \(m\ge7\), its scores satisfy \(\alpha_4=m-4>2=\alpha_{m-2}\).
My proposed mirror is Mass-CCAV(\(f\)). For \(m\) candidates, let a type be a complete ranking \(\pi\) together with its status: already registered or eligible to be added. The instance lists each supported ranking with registered mass \(r_\pi\) and eligible unregistered mass \(u_\pi\), both binary rationals, along with \(p\) and a rational mass budget \(\kappa\). Normalize the total listed population to one. The decision variable is \(x_\pi\), the mass of eligible people with ranking \(\pi\) who are mobilized. Ask whether there is a rational vector \(x\) such that
\[ 0\le x_\pi\le u_\pi,\qquad \sum_\pi x_\pi\le\kappa, \]
and, for every candidate \(c\),
\[ \sum_\pi (r_\pi+x_\pi) \left( \alpha^{f,m}_{\operatorname{pos}_\pi(p)} - \alpha^{f,m}_{\operatorname{pos}_\pi(c)} \right)\ge0. \]
A feasible \(x\) is the solution; equivalently, one can minimize total mobilized mass and compare the optimum with \(\kappa\). The winner condition, including ties, is exactly the paper’s scoring-rule condition.
This is a credible population regime for the theorem’s unweighted model: a large election or membership vote with many eligible people, but relatively few distinct full rankings among the registered and mobilizable groups. For example, a contest with a modest number of candidates may have millions of people but at most hundreds of ranking types. People share a type when they have the same ranking and the same eligibility status; under unweighted CCAV, their cost and other problem-relevant attributes are also the same. The action is naturally described as mobilizing a fraction of each preference cohort. In a finite election of size \(N\), the corresponding masses are voter counts divided by \(N\), and selectable masses lie on the \(1/N\) grid. Mass-CCAV removes that grid.
For every \(f\) covered by Theorem 4.10, Mass-CCAV is in polynomial time: the displayed constraints form a linear program with one variable per supported eligible ranking and one winner constraint per candidate. Its size is polynomial in \(m\), the support size \(\tau\), and the mass bit length \(L\). I would expect this mirror to be Class A. The point is that the paper’s 3DM reduction needs the chair to choose whole ballots in a coordinated, all-or-nothing way. The continuous problem asks whether that hardness survives when control is measured in mass; here it appears to dissolve into LP feasibility.
The authors should recognize the question as theirs: it keeps the same chair, eligible pool, target candidate, scoring rule, and winner condition, and changes the unit of control from people to population share. It covers Theorem 4.10’s CCAV hardness cases, including Borda; it does not claim to continue the paper’s results on the descriptive richness of scoring rules. Further questions include how the continuous optimum relates to finite CCAV when only \(1/N\)-sized additions are allowed, and how large a score margin is needed to round a fractional solution into a successful finite one.
The weakest point is also the source of the tractability: allowing fractional mobilization changes the chair’s feasible actions. If the authors regard adding voters as intrinsically selecting named, indivisible people, they may see this as a different problem. The reply is that the continuous-population formulation makes a mobilized percentage of each ballot type the decision, while preserving the original electoral objective. The mirror is strongest precisely as a test of whether the paper’s discrete hardness depends on voter granularity.
I can’t honestly defeat the anchor. Theorem 4.10 is a named computational result: it establishes NP-completeness of CCAV for a broad class of pure scoring rules, including Borda. Its natural population mirror is to describe registered and eligible voters by ballot type, then let the chair mobilize a share of each eligible type.
The strongest objection is that CCAV’s action is choosing whole voters, while the proposed mirror lets the chair choose fractional shares. But that is exactly the population-level question the programme permits: can a chair mobilize, say, \(0.5\%\) of an eligible preference cohort? The distinction does not make the model incoherent. In a large election or membership vote, voters with the same ranking and eligibility status can be treated as one type, and the chair’s decision can be expressed as a mobilization rate for each type. Individual identity is immaterial to this paper’s unweighted scoring rule.
Nor does the mirror collapse to a vacuous limit. With binary-rational registered and eligible masses, it asks whether there is a feasible vector \(x\) satisfying the mass bounds, budget, and score inequalities. That is a rational linear program with size polynomial in the number of candidates, supported types, and input bit length. Its tractability may be immediate, but that is a genuine Class A outcome: it shows what happens to the discrete hardness when control is measured in population shares. The finite-to-continuous comparison and the consequences for finite elections with a moderate number of ballot types remain natural questions.
So the best negative point is about priority: the LP may be a short baseline result rather than a deep new algorithm. But the brief explicitly counts tractable continuous formulations as worthwhile, and this mirror has a credible high-multiplicity scenario. I do not see an honest fundamental objection that defeats it, let alone one supporting the claim that no worthwhile continuous mirror exists.
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.