| paper | d4-conf-aaai-2017-0355 |
| 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, with running time \(O(\tau L^2+m(\tau+m)L)\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given candidates \(C\), a tie-breaking order, a designated candidate \(c^\star\), and a support \(T\subseteq\mathrm{Lin}(C)\) with positive binary-rational masses \(\mu_t\) summing to \(1\), determine whether \(c^\star\) wins STV. In each round, assign each type’s mass to its highest-ranked remaining candidate, eliminate a candidate with minimum assigned mass using the given tie-breaking order, and repeat until one candidate remains.
A population is represented by its distribution \(\mu\) over complete ranking types. Each type’s mass contributes to the current first-choice tally as a whole; the decision is the last remaining candidate under STV elimination with the specified tie-breaking order.
The mirrors cover STV-WINNER and Schwartz-set determination. They leave the scoring-rule, Smith-set, Copeland-set, experimental, and other MapReduce results unaddressed.
The strongest mirror is Continuous STV-WINNER. A plausible regime is a national association with a fixed slate of candidates and millions of members submitting complete rankings online. A voter’s type is their ranking; its mass is the fraction of members with that ranking. When the slate is modest and ballots repeat, the number \(n\) of members can greatly exceed the number \(\tau\) of distinct ranking types.
The anchor is Theorem 6, proved in this paper: STV-WINNER is P-complete. The paper reduces BOOLEAN CIRCUIT EVALUATION to STV by making the first \(m\) elimination rounds retain \(c_i\) exactly when gate \(g_i\) evaluates to true; later eliminations leave \(c_m\) as winner exactly when the circuit output is true. Thus the result shows P-completeness even though the paper’s next result identifies the number of candidates as the source of that complexity.
The continuous problem is precise. An instance consists of candidates \(C\), a tie-breaking order, a designated candidate \(c^\star\), and a support \(T\subseteq \mathrm{Lin}(C)\) of \(\tau\) complete rankings with positive binary-rational masses \(\mu_t\) summing to \(1\). In each round, each type assigns its mass to its highest-ranked remaining candidate. Eliminate a candidate with minimum assigned mass, resolving ties by the given order. The question is whether \(c^\star\) is the last remaining candidate; a solution may include the elimination sequence as a certificate. There is no optimization objective: this mirrors the paper’s winner-determination decision problem.
I expect this problem to be P-complete by hardness transfer, specifically in the paper’s sense of inherent sequentiality, not NP-hardness. Given any discrete election with \(n_t\) voters of ranking \(t\), set \(\mu_t=n_t/n\). In every round, each candidate’s mass is its discrete vote count divided by \(n\), so the eliminations and winner are identical. This gives an exact embedding of the discrete problem. The continuous problem is also in P: recompute the remaining first-choice masses over the \(\tau\) types in each of at most \(m-1\) rounds, using exact rational arithmetic. The natural follow-up is to characterize its parallel depth in \(m,\tau,L\), and identify restrictions on the candidate slate or rankings that avoid the sequential elimination chain.
A second, independently useful mirror is Mass-Schwartz Determination. Its scenario can use the same kind of large electorate. The type is again a complete ranking and \(\mu_t\) its population fraction. Define \(a\succ_\mu b\) when
\[
\sum_{t:\,a\succ_t b}\mu_t >
\sum_{t:\,b\succ_t a}\mu_t.
\]
The resulting strict-dominance graph has candidates as vertices and edges \(a\to b\) when \(a\succ_\mu b\). The problem is to output the Schwartz set: the union of the minimal sets not dominated by outside candidates, equivalently the source strongly connected components of this graph. There is no separate optimization objective.
The anchor is Proposition 3, proved here: the paper’s MapReduce algorithm computes the Schwartz set from the strict-dominance graph with replication rate at most \(2m+1\), \(\lceil\log_2 m\rceil+1\) rounds, \(m\) keys, wall-clock time \((2m^2+3m)(\lceil\log_2 m\rceil+1)\), and total communication cost at most \(2m^3+3m^2(\lceil\log_2 m\rceil+1)\). These bounds concern the graph as input. For the continuous mirror, first aggregate the \(\tau\) type masses into pairwise margins, then apply the paper’s reachability computation. I expect the result to be tractable in \(\mathrm{poly}(m,\tau,L)\); after margin aggregation, the graph computation retains the paper’s logarithmic number of MapReduce rounds. The further question is how the exact arithmetic on binary-rational masses affects communication and bit complexity.
Theorem 6 is my lead because its embedding cleanly tests the programme’s boundary: the population can be compressed into types, while complexity driven by the candidate dimension remains. Proposition 3 adds a tractable mirror of the paper’s parallel winner-set computation. Together, these mirrors cover STV-WINNER and Schwartz-set determination, not the paper’s scoring, Smith, or Copeland results.
The weakest point is that the STV mirror’s result transfers exactly: the continuous formulation may look like a compact weighted encoding of the discrete problem, rather than a new computational phenomenon. I think it still qualifies. The population is explicitly the continuous object, the high-multiplicity regime is plausible for large electorates with repeated ballots, and the exact transfer is the informative answer: multiplicity is not what causes this anchor’s sequentiality.
The strongest case against these anchors is that they offer little new population-dependent structure. It is strongest against Proposition 3. That proposition starts from a dominance graph, not a society. Given a distribution \(\mu\), one can compute each pairwise margin
\[
M_{ab}=\sum_{t:\,a\succ_t b}\mu_t-\sum_{t:\,b\succ_t a}\mu_t
\]
by scanning the \(\tau\) supported rankings, then run the paper’s graph algorithm on the signs of those margins. The population is compressed into an \(m\times m\) matrix before the proposition’s computation begins. An end-to-end continuous version is well-posed, but its extra step is straightforward aggregation; the MapReduce bounds in Proposition 3 do not themselves illuminate a continuous-population phenomenon. That makes it a weak independent research priority.
The best version of that mirror would analyze the full pipeline, including the communication and bit costs of aggregating binary-rational masses. But the ranking types contribute independently to pairwise margins, so this appears to add a routine aggregation stage before the existing graph computation. That is a reason to doubt the value of this particular anchor, not a reason the continuous question is ill-posed.
Theorem 6 is much harder to argue against. Continuous STV on ranking types is a sensible model for a large electorate with repeated ballots. Replacing ballot counts by rational masses preserves every round’s first-choice totals up to a common scale, so it preserves the elimination sequence. The circuit reduction may therefore transfer, and the fact that the hardness is driven by the candidate dimension does not disqualify the mirror under ChoCo’s stated criteria. One can say that the result may be mainly a compact encoding of the discrete one; but the programme explicitly treats such a transfer as a useful Class B result. Calling its answer dull would not defeat the anchor.
So the negative case can question whether Proposition 3 merits a separate continuous-mirror study, since its core input is already a graph and the population adds only preprocessing. It cannot honestly rule out the STV mirror in any plausible scenario. On the material supplied, the universal claim that neither anchor yields worthwhile continuous work is weak.
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.