| paper | d4-conf-atal-2021-0202 |
| 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: For both \(\mathrm{Borda}\) and \(2\text{-approval}\), feasibility is decidable in \(\operatorname{poly}(m,\tau,L)\) time. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given candidates \(C\), a target \(c\), a scoring rule \(r\in\{\mathrm{Borda},2\text{-approval}\}\), and partial-chain types \(P_1,\ldots,P_\tau\) with positive rational masses \(\mu_t\) summing to \(1\), let \(\operatorname{Ext}(P_t)\) be the total rankings extending \(P_t\). Does there exist a nonnegative real allocation \(x_{t,\pi}\) satisfying \(\sum_{\pi\in\operatorname{Ext}(P_t)}x_{t,\pi}=\mu_t\) for each \(t\), such that \(\sum_{t,\pi}x_{t,\pi}s_r(\pi,c)\ge\sum_{t,\pi}x_{t,\pi}s_r(\pi,d)\) for every \(d\ne c\)?
An atomless population grouped by exact observed partial-chain type, with rational mass \(\mu_t\) for type \(P_t\). Decision variables \(x_{t,\pi}\) allocate each type’s mass among its compatible complete rankings; population scores are the resulting mass-weighted scores, and the target must tie or beat every other candidate.
The mirror covers the hardness results for Borda in Theorem 6 and 2-approval in Theorem 3. It leaves the rest of the classification, including other scoring rules and the uniform partial-chain results, unaddressed.
The strongest mirror I see is a continuous possible-winner problem on partial chains. The society is a population of viewers, each of whom has ranked the movies they have seen but has not ranked the rest. A type is one exact partial chain: the same ordered subset of candidates. Its mass is the fraction of the population with that partial ranking.
This fits the paper’s question directly. Each unit of mass still receives one complete ranking extending its partial chain; only the type’s mass can be divided among different completions. The division represents different viewers with the same observed ranking having different preferences over the unseen candidates. It is a population model, not a lottery over election outcomes.
Here is the problem I would hand to a prover, for either scoring rule in my anchors. The input is a candidate set \(C\), a target \(c\), partial chains \(P_1,\ldots,P_\tau\), and positive rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\). Write \(\operatorname{Ext}(P_t)\) for the total rankings extending type \(P_t\). Choose nonnegative masses \(x_{t,\pi}\) for \(\pi\in\operatorname{Ext}(P_t)\), subject to
\[
\sum_{\pi\in\operatorname{Ext}(P_t)}x_{t,\pi}=\mu_t
\quad\text{for every }t.
\]
For scoring rule \(r\), define candidate \(d\)’s population score as
\[
\mathrm{Sc}(d)=\sum_{t=1}^{\tau}\sum_{\pi\in\operatorname{Ext}(P_t)}
x_{t,\pi}s_r(\pi,d).
\]
The optimization objective is to maximize the target’s worst score margin:
\[
\max_x\ \min_{d\ne c}\bigl(\mathrm{Sc}(c)-\mathrm{Sc}(d)\bigr).
\]
The decision question is whether the optimum is at least \(0\), so ties count as wins just as they do in the paper. A solution is a mass allocation across compatible complete rankings.
My lead anchor is Theorem 6, proved in this paper: Possible Winner on partial chains with the Borda count is NP-complete. The paper reduces from 3-Dimensional Matching. The continuous question is the problem above with \(s_B(\pi,d)=m-\operatorname{pos}_{\pi}(d)\). I expect this mirror to be tractable. Its LP has exponentially many completion variables, but its pricing problem has a simple structure: in a partial chain, the ranked candidates must stay in their given order, while all candidates outside the chain are unconstrained. For a dual objective \(\sum_d a_d s_B(\pi,d)\), sort the unconstrained candidates by decreasing \(a_d\), then use dynamic programming to find the best interleaving of that list with the fixed chain. This takes polynomial time. Thus the usual separation machinery for an exponential-variable LP appears to give an exact algorithm polynomial in \(m\), \(\tau\), and the input bit length \(L\).
The second anchor is Theorem 3, also proved here: Possible Winner on partial chains under 2-approval is NP-complete. Its reduction from 3-Dimensional Matching encodes a discrete choice of triple-associated votes. The continuous question is the same mass-allocation problem with \(s_{2\mathrm{Ap}}(\pi,d)=1\) for a candidate in one of the first two positions and \(0\) otherwise. I also expect this version to be tractable: pricing only needs to find the best feasible top two positions for each type, which can be done in polynomial time. Here the reduction’s requirement to select whole votes looks especially likely to relax to a fractional matching or packing problem.
The authors should recognize both as their possible-winner question: can compatible complete rankings make the target a winner? The rule, candidates, partial chains, and winner condition all remain. The change is exactly the population continuization: a finite profile with \(n_t\) voters of type \(t\) restricts each \(x_{t,\pi}\) to multiples of \(1/n\), where \(n\) is the total number of voters; the continuum removes that one-person grid. A feasible \(x\) does not give any voter a fractional ranking. It partitions each type’s mass among full rankings.
A plausible regime is a large movie platform evaluating a shared catalog, where many viewers have ranked the same recurring slate of watched movies. One can imagine millions of viewers but far fewer distinct ordered slates in a repetitive or templated-review setting. This is deliberately a regime claim, not a claim about all elections or all recommendation platforms. The paper’s movie example supplies a natural story, and a large platform supplies the high-multiplicity setting. The exact type is the complete partial chain, since that determines exactly which completions the problem allows.
The weaker point is whether that regime has moderate support in real data: exact ordered slates can proliferate quickly, so the \(m,\tau,L\) parameters matter. The other likely objection is that Possible Winner assigns one completion to each named voter. In an atomless population, assigning mass \(x_{t,\pi}\) to an extension means that a subset of viewers of that type, of mass \(x_{t,\pi}\), has that full ranking. Each individual still has an integral ranking; the continuum simply allows every fraction of a type to be represented.
This case covers the partial-chain hardness results for 2-approval and Borda, not the paper’s entire classification or its other incomplete-vote problems. For both anchors, the predicted outcome is tractability: the discrete hardness may dissolve because the 3-Dimensional Matching gadgets rely on indivisible vote choices, while the continuous LP pricing remains manageable. The main follow-up is to quantify the gap back to finite elections: when does a continuous feasible allocation round to a discrete possible-winner completion, and what margin or population-size bounds make that approximation useful?
I can’t make a strong case that defeats both anchors. Theorem 3 and Theorem 6 are named computational results, and their possible-winner questions survive the basic population-model test.
The strongest objection is a quantifier shift. In the finite problem, each named voter gets one completion; the continuous formulation lets a type’s mass split across completions. That changes the feasible set and can turn a “no” into a “yes.” But for an atomless population, each such split can be realized by assigning different subsets of the type to different complete rankings. Every person still gets one integral ranking. The shift is precisely the high-multiplicity relaxation, not a change from voters to lottery outcomes.
The stronger versions of both mirrors also look computationally promising. For Borda, a pricing query asks for the best ranking extending a fixed chain under a linear score objective. Sort the unconstrained candidates by their dual coefficients, then use dynamic programming to interleave that order with the fixed chain. For 2-approval, pricing only needs to optimize the top two positions subject to the chain. These are polynomial-time queries; with the rational mass constraints and winner inequalities, the exponential-variable LP appears amenable to exact separation-based solution. That would make the continuous questions meaningful even if the discrete reductions’ indivisibility disappears.
The best practical concern is support size. On a large movie catalog, exact ordered partial chains may be so varied that \(\tau\) approaches the number of viewers, weakening the high-multiplicity regime. Finite-population rounding near a zero margin is another real issue. But repeated slates, templated rankings, or late-candidate settings can provide plausible moderate-support populations, and rounding is a follow-up question rather than a defect in the continuous problem.
So the negative case is weak where it must be strongest: neither the semantics nor the likely algorithmic structure gives a sound reason to reject the mirrors. The proponent’s anchors survive; I would not recommend a negative verdict.
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.