| paper | d4-conf-ijcai-2019-0622 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\), by exact rational linear programming. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.1(i)
Given a finite support \(T\) of equal-sized district patterns with rational masses \(\mu_t\) summing to \(1\), true and reported vote-share vectors \(q_t,\tilde q_t\in\Delta_m\), a recount budget \(\beta\), target \(a\), tie-breaking order, and reported-profile winner \(b\ne a\), decide whether there are masses \(x_t\in[0,\mu_t]\) with \(\sum_t x_t\le\beta\) such that \(S_c(x)=\sum_t((\mu_t-x_t)\tilde q_{tc}+x_tq_{tc})\) makes \(a\) the winner under that order.
A continuum limit of equal-sized districts, represented by a distribution over complete district-record types. Each type carries its true and reported vote shares; the defender chooses a mass \(x_t\) of each type to recount, subject to the total budget, and asks whether the resulting Plurality winner is the target candidate.
The mirror covers the \({\sc PV}\)-Rec hardness result in Theorem 3.1(i), for \(m=3\). It leaves the other \({\sc PV}\)-Rec results, all attacker results, the \({\sc PD}\) results, and the regular-manipulation results aside.
The strongest mirror is the defender’s Plurality over Voters recount problem. Picture a very large election with many equally sized polling districts and a small number of recurring district patterns. A type is a district pattern, fully described by its true vote shares and its reported, possibly manipulated, vote shares. Its mass is the fraction of all districts—and, because districts are equally sized, the fraction of voters—with that pattern. The defender still recounts whole districts; in the continuum, she can select any mass of identical districts. That follows the paper’s choice to make districts the units of action.
Call the resulting problem Continuous PV Recount. An instance has a finite support \(T\), rational masses \(\mu_t>0\) summing to one, true and distorted vote-share vectors \(q_t,\tilde q_t\in\Delta_m\) for every \(t\in T\), a target candidate \(a\), a recount budget \(\beta\in[0,1]\), and the paper’s tie-breaking order. The distorted profile has a winner \(b\ne a\). A solution is a vector \(x\) with \(0\le x_t\le\mu_t\) and \(\sum_t x_t\le\beta\), where \(x_t\) is the mass of type \(t\) recounted. The resulting score share for candidate \(c\) is
\(\displaystyle S_c(x)=\sum_{t\in T}\big((\mu_t-x_t)\tilde q_{tc}+x_tq_{tc}\big).\)
The question is whether some such \(x\) makes \(a\) the winner under the given tie-breaking order. For a discrete election with \(k\) districts, the corresponding inputs have \(\mu_t=k_t/k\) and \(\beta=B_{\cal D}/k\).
My anchor is Theorem 3.1(i), proved in this paper: \({\sc PV}\)-Rec is NP-complete even with \(m=3\) candidates. Its reduction from Subset Sum encodes the choice of which districts remain unrecounted. In the continuous mirror, the same question is linear feasibility, with \(\tau=|T|\) variables and score constraints for the candidates. It is solvable in polynomial time in \(m,\tau\), and the input bit length \(L\), so I expect this mirror to be tractable (Class A).
The relaxation changes the answer in a way the programme is meant to investigate. In the reduction, districts left unrecounted encode a nonempty zero-sum subset. In the continuous problem, their masses can be fractional: for example, values \(1\) and \(-2\) can balance using masses \(2/3\) and \(1/3\), even though no nonempty subset sums to zero. Thus the mirror removes the subset-selection constraint that drives this anchor’s hardness; it does not claim that the original finite election has the same answer. Further questions include when a continuous solution can be rounded to actual districts, what additive guarantees hold when \(k\) is large relative to \(\tau\), and how close score margins must be for rounding to preserve the winner.
The scope here is specifically the three-candidate PV recount result in Theorem 3.1(i). I am not claiming a mirror for the attacker’s problem, Plurality over Districts, or the paper’s other results.
The soft spot is the regime: repeated, equally sized precincts with the same true and distorted vote-share pattern are a plausible model for a large standardized election, but they are a stronger assumption than merely having many voters. The reduction behind Theorem 3.1(i) also uses heterogeneous district data, with each item represented by its own district. So this is a credible mirror of the authors’ district-level recourse question in a high-multiplicity setting, while the hardness result alone does not show that the same hardness arises within that setting.
The strongest objection to Theorem 3.1(i) is a mismatch in what becomes continuous. The theorem’s choices are indivisible districts. If the society remains a population of voters and district membership remains part of the model, recounting a district still acts on a whole block; taking the number of voters large does not by itself make those district choices divisible. The proposed variables \(x_t\) become valid only when districts with the same true and reported vote-share pattern are treated as replicable units and any mass of them may be recounted. That is a continuous population of district records, including the attack’s report as part of each record, rather than the paper’s original population of voters.
This objection reaches the best version of the mirror, but it does not rule it out. A regime with many equal-sized, recurring district patterns and a recount budget proportional to the number of districts is coherent. There, selecting a fraction of a pattern’s mass is the limit of recounting whole districts, and the vote-share constraints preserve the PV objective. The programme also allows population scaling to require related changes to resources and actions. So the level shift may be a legitimate co-modification, and the authors could recognize it as their question.
The paper’s reduction uses distinct district data to encode Subset Sum, which gives no evidence that its hard instances lie in a fixed-support regime. But that does not disqualify a mirror: the continuous question remains well-posed, and the discrete-to-continuous gap is precisely what the programme investigates. I therefore cannot make a convincing case that every worthwhile mirror fails. The level-of-population objection is the best negative argument I see, but under the stated scope it is too weak to defeat this anchor.
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.