| paper | d4-conf-atal-2021-0073 |
| 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 for every fixed positional scoring rule satisfying the stated assumptions. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a fixed positional scoring rule \(r\), candidates \(C\), a target \(c^\star\), a tie-breaking order \(\tau\), an integer \(k\), and a finite support of partial-order types \(P\) with positive binary-rational masses \(\mu_P\) summing to \(1\), does there exist a completion plan \(x_{P,\pi}\geq 0\), indexed by linear extensions \(\pi\in\mathrm{LE}(P)\), such that \(\sum_{\pi\in\mathrm{LE}(P)}x_{P,\pi}=\mu_P\) for each \(P\) and \(\mathrm{rank}_x(c^\star)>k\)? Here \(S_x(c)=\sum_{P,\pi}x_{P,\pi}r(|C|,\mathrm{pos}_\pi(c))\), and rank is determined by these scores with ties resolved by \(\tau\).
A nonatomic electorate with finite support over partial-order ballot types. Each type \(P\) has rational mass \(\mu_P\), and decision variables \(x_{P,\pi}\) distribute that mass among its compatible linear extensions. Aggregate positional scores determine candidate ranks under the given tie-breaking order.
The mirror covers Theorems 2 and 3. It leaves the fixed-threshold, parameterized, and other voting-rule results unaddressed.
The strongest mirror I see is the paper’s result for the maximal possible rank, with its minimal-rank result as a close companion. A plausible setting is a large public consultation on a fixed slate of proposals. Many residents submit incomplete rankings: they express some comparisons but leave others unresolved. If the same survey interface produces recurring partial-order patterns, the number of residents \(n\) can be much larger than the number \(\tau\) of distinct patterns. The mass of a type is its share of respondents. The question “how far down the ranking could this proposal end up?” is meaningful at that scale.
Here is a precise version. An instance contains candidates \(C\), a positional scoring rule \(r\), a target \(c^\star\), a fixed tie-breaking order \(\tau\), an integer \(k\), and a finite support of partial-order types \(P\), each with rational mass \(\mu_P\), where \(\sum_P\mu_P=1\). For each type \(P\), let \(\mathrm{LE}(P)\) be its linear extensions. A completion plan chooses masses \(x_{P,\pi}\geq 0\) for \(\pi\in\mathrm{LE}(P)\), with \(\sum_{\pi\in\mathrm{LE}(P)}x_{P,\pi}=\mu_P\). Every agent still has a complete ranking consistent with their type; \(x_{P,\pi}\) records how much of that type’s mass has each ranking.
The resulting score is \(S_x(c)=\sum_{P,\pi}x_{P,\pi}r(m,\mathrm{pos}_\pi(c))\). Define \(\mathrm{rank}_x(c^\star)\) as one plus the number of candidates scoring above \(c^\star\), counting equal-scoring candidates ahead of it according to \(\tau\). The solution is a completion plan \(x\) witnessing the requested rank condition.
Lead: Continuous Maximal-Rank. Given that instance, does there exist a completion plan \(x\) with \(\mathrm{rank}_x(c^\star)>k\)?
Its anchor is Theorem 3, proved in this paper: for every positional scoring rule \(r\), \(\mathrm{Max}_r\{>\}\) is NP-complete. In the paper’s definition, the input is a partial profile, a candidate, a tie-breaking order and a threshold \(k\); the question is whether the candidate’s maximal rank over all completions exceeds \(k\). The authors prove hardness by reduction from Independent Set on regular graphs.
Continuous Minimal-Rank is the companion question: does there exist a completion plan \(x\) with \(\mathrm{rank}_x(c^\star)<k\)? Its anchor is Theorem 2, also proved here: for every positional scoring rule \(r\), \(\mathrm{Min}_r\{<\}\) is NP-complete. The paper’s input and threshold interpretation are the same, but it asks whether the candidate’s minimal rank is below \(k\). The proof reduces from Vertex Cover on regular graphs. Both theorems cover plurality and veto as well as other positional scoring rules.
These are recognizable mirrors of the authors’ problems: the types retain the paper’s partial preferences, and the rule, target, tie-break and extremal-rank questions stay intact. Only the electorate is represented by proportions, with mass of a repeated type allowed to complete in different consistent ways. That is a natural high-multiplicity version of reasoning about a large population’s incomplete preferences. It continuizes the population, not the candidates, scores, or outcome space.
My working prediction for both questions is Class B: hardness transfers, because the reductions’ main combinatorics concern choosing among candidates, while the continuous model still asks how many candidates rank ahead of the target. This is a conjecture about these mirrors, not a consequence of Theorems 2 and 3. A further question is whether the same alternative-level combinatorics can be encoded after each type’s mass is divisible; related questions include whether fixed-threshold variants become tractable and what role pricing over linear extensions plays.
The weakest point is exactly that divisibility. In the paper’s reductions, voters’ completions encode discrete graph choices. A continuum can split a type’s mass among several extensions, potentially turning those choices into fractional ones and dissolving the reductions’ hardness. A new proof would be needed to establish hardness transfer. That risk does not undermine the mirror itself: even if the fractional version turns out tractable, it answers the same population-level question about the range of a candidate’s rank under incomplete preferences. This case covers Theorems 2 and 3 only.
The negative case is weak. Neither of the paper’s main anchors can be dismissed for lack of a computational result: Theorems 2 and 3 explicitly establish NP-completeness for the minimal- and maximal-rank problems.
The best objection is that the paper reasons about uncertainty in individual ballots. A partial order describes what one voter’s ranking could be, while the proposed continuous model lets the mass of that partial-order type split across different completions. That is a real change in the completion model. But it is also a coherent nonatomic version of it: a continuum of respondents with the same incomplete ballot pattern can have different rankings consistent with that pattern. A large consultation with recurring ballot patterns—for example, from a survey interface that leaves some comparisons unresolved—makes this a plausible high-multiplicity regime. The split records how much of each pattern’s mass has each compatible ranking.
Theorem 2’s mirror asks whether some such completion puts the target above enough candidates to achieve rank below \(k\); Theorem 3’s asks whether one puts enough candidates ahead of it to achieve rank above \(k\). For any fixed set of candidates whose relative scores certify the rank condition, the completion question is a linear feasibility problem over masses on linear extensions. There may be many extensions, and the overall problem still has combinatorial choices, but that is a computational challenge in the mirror—not a reason the question is ill-posed or out of scope.
The same objection applies to both anchors, and I do not see a stronger version that defeats the survey scenario while preserving the paper’s question. The continuum could change the answer, or its difficulty could come largely from the candidate agenda; neither is a valid objection under the programme’s criteria. I find no basis in the paper for claiming the mirror is already done continuously. The honest conclusion is that the proponent’s two anchors survive the best negative case I can make.
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.