| paper | d4-conf-aaai-2021-1852 |
| 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: The continuous budget decision problem is in \(\mathrm{P}\) for every fixed \(q\ge 3\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given candidates \(C\), preferred candidate \(p\), fixed \(q\ge3\), and rational masses \(\mu_r\) on a support \(R\) of \(\tau\) rankings, choose \(y_{r,S}\ge0\), the mass of ranking type \(r\) assigned to final top-\(q\) set \(S\in\binom{C}{q}\), to minimize \(\sum_{r\in R,S\in\binom{C}{q}}\kappa_r(S)y_{r,S}\), subject to \(\sum_{S\in\binom{C}{q}}y_{r,S}=\mu_r\) for every \(r\), and \(\sum_{r,S:p\in S}y_{r,S}\ge\sum_{r,S:c\in S}y_{r,S}\) for every \(c\ne p\). Here \(\kappa_r(S)=|\{c\notin S:\operatorname{rank}_r(c)<\max_{s\in S}\operatorname{rank}_r(s)\}|\), the minimum number of demotion operations per unit of mass needed to make \(S\) the approved set. Each unit of mass receives an ordinary integral ranking after its demotions, and \(p\) must be a co-winner.
A society is a rational distribution \(\mu\) over complete rankings; the decision allocates each type's mass among legal demotion plans, with cost measured in operations per capita. For fixed \(q\), the resulting linear program has \(\tau\binom{m}{q}\) variables and is solvable in polynomial time in \(m\), \(\tau\), and the input bit length.
The mirror covers Theorem 3's unpriced constructive \(q\)-approval hardness result for fixed \(q\ge3\). It does not cover the approximation results, Borda results, priced inapproximability result, or destructive variant.
The strongest mirror I believe is for the paper’s fixed-\(q\) approval hardness result. It asks whether the paper’s constructive campaign problem becomes tractable when voters are represented by masses of identical preference types.
A natural regime is a large election with a fixed candidate slate and many voters sharing one of a relatively small number of strict rankings. For this unpriced result, a type is just a complete ranking: the paper’s problem assigns no other relevant attributes to voters. The campaign can target any fraction of a ranking cohort. Each person in that fraction still receives an ordinary, integral ranking after a sequence of legal demotions; only the population is divisible. Measure campaign cost in operations per capita, so a discrete strategy using \(k\) operations among \(n\) voters has cost \(k/n\).
My anchor is Theorem 3, proved by the authors. It states that, for every fixed \(q\ge3\), deciding whether at most \(k\) demotion operations can make a preferred candidate win under \(q\)-approval is NP-hard. The paper sketches the reduction for \(q=3\), from 3-Set Cover, and says the other fixed-\(q\) cases are similar; the complete proof is deferred to the full version.
Here is the continuous question. Given candidates \(C\), a preferred candidate \(p\), a fixed \(q\ge3\), and a rational distribution \(\mu\) over \(\tau\) rankings, find a minimum-cost allocation of each type’s mass among legal demotion plans so that \(p\) is a co-winner under \(q\)-approval. A solution specifies how much mass of each ranking receives each plan; its cost is the total mass of operations, and its output is the resulting distribution of rankings. Equivalently, for each ranking \(r\) and each \(q\)-candidate set \(S\), let \(y_{r,S}\) be the mass of type \(r\) whose final top \(q\) candidates are exactly \(S\). Define
\[
\kappa_r(S)=\left|\left\{c\notin S:\operatorname{rank}_r(c)<\max_{s\in S}\operatorname{rank}_r(s)\right\}\right|.
\]
This is the minimum number of operations needed to make \(S\) the top \(q\): every nonmember ranked above the lowest-ranked member of \(S\) must be demoted, and demoting each such candidate below \(S\) once suffices. The continuous problem is the linear program
\[
\min \sum_{r,S}\kappa_r(S)y_{r,S}
\]
subject to
\[
\sum_S y_{r,S}=\mu_r \quad\text{for every }r,
\qquad
\sum_{r,S:p\in S}y_{r,S}\ge \sum_{r,S:c\in S}y_{r,S}\quad\text{for every }c\ne p,
\qquad y_{r,S}\ge0.
\]
The solution can be handed to a campaign as cohort masses and legal demotion plans, not merely as an encoding.
For fixed \(q\), this has \(\tau\binom{m}{q}\) variables and a polynomial number of constraints. Thus the mirror is in Class A: it is exactly solvable in time polynomial in \(m,\tau,L\), for fixed \(q\). The discrete hardness need not survive. The reduction’s selection of indivisible voters resembles Set Cover; in the mirror, cohort mass can be divided among plans, so that selection becomes fractional. This is a concrete case where population continuization changes the computational question in the intended way.
I think the authors would recognize this as their problem: the rule, target, allowed demotions, and co-winner condition are unchanged. The change is to represent repeated, indistinguishable voters by a distribution and allow a cohort to be split among campaigns. In a large electorate, targeting a proportion of a preference cohort is a natural quantity, and the model never gives an individual a fractional ballot.
The mirror covers Theorem 3’s constructive, unpriced \(q\)-approval result. Two follow-up questions are whether the LP solution can be rounded to a finite electorate with controlled cost and score error, and whether a comparable algorithm exists when \(q\) is part of the input rather than fixed.
Its weakest point is that a finite campaign reaches whole people: a continuous allocation may divide a type’s mass in proportions the actual electorate cannot realize. That matters for transferring solutions back to finite elections, especially when the winner has little score margin. It does not undermine the continuous question itself; it identifies the rounding guarantee the high-multiplicity bridge still needs.
I can’t make a credible case against the Theorem 3 mirror. For this paper, the high multiplicity regime is especially natural: voters are described by rankings, and large elections can have many voters sharing each ranking. The unpriced model adds no individual attribute that would make those voters distinct.
The proposed LP also appears to model the campaign correctly. For a ranking \(r\), the least number of operations needed to make a \(q\)-set \(S\) the approved set is exactly the number of nonmembers ranked above the lowest-ranked member of \(S\): each such candidate must be demoted, and one operation per candidate suffices. That cost scales linearly with the mass assigned to the plan. The co-winner constraints are linear in the resulting approval masses. With fixed \(q\), the \(\tau\binom{m}{q}\) variables are polynomial in the input parameters.
The best objection is that fractional cohort plans may not be executable in a particular finite electorate, especially near a close tie. But that limits how directly the continuous optimum transfers back to that electorate; it does not make the continuous question ill-posed. A sufficiently large electorate can approximate the plan, and the programme explicitly treats rounding as part of the bridge rather than a prerequisite for studying the continuous problem.
Nor does the paper’s discrete \(t\)-factor approximation settle this mirror: it works on individual voters and does not give an exact algorithm for rational masses encoded by type. The paper’s flow construction even uses the same approval-set cost structure, which supports the mirror’s fit rather than displacing it.
So the negative case is weak here. The anchor survives: this is a clear continuous-population computational question, and its LP gives a concrete tractability result for a problem the paper proves NP-hard in the discrete setting.
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.