| paper | Dimensionality and Coordination in Voting: The Distortion of STV |
| authors | Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos |
| venue | AAAI 2022 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
The proposed mass formulations are faithful, author-recognizable high-multiplicity mirrors, especially for COORDINATION. However, the paper contains no named theorem asserting computational hardness, tractability, parameterized complexity, or an algorithm for a computational problem. The strict source gate therefore fails, regardless of whether the resulting continuous questions are worthwhile.
fails bit a — no named computational result to mirror
The paper's named results are distortion and convergence guarantees rather than computational results, so the proposed continuous tasks are new evaluations of fixed voting processes rather than continuizations of established complexity problems.
fatal: True
The mirrors cover weighted-population readings of Theorems 4.3 and 1.5 for COORDINATION and Theorems 1.2 and 3.2 for STV, with Theorem 3.3 serving only as a boundary test; they do not cover a named computational result because none is present.
There is a defensible positive case, but it begins with an important qualification: this paper contains no named NP-hardness, membership-in-\(\mathrm{P}\), parameterized, or approximation-algorithm theorem in the usual computational-complexity sense. Its named results concern distortion bounds and convergence of voting dynamics. Thus, under ChoCo’s strict source gate, it has no qualifying computational anchor. The strongest honest case is instead that two of its proved results admit unusually faithful high-multiplicity computational mirrors.
The natural regime is a large electorate of voters clustered into a small number of repeated spatial-preference types. A type \(t\) should include its location or complete distances to candidates, its induced ranking \(\sigma_t\), and any tie-breaking information used by the dynamics. Let \(T\) be the finite type set, \(|T|=\tau\), and let \(\mu_t\) be the fraction of voters of type \(t\), with \(\tau\ll n\). For candidates \(C\), define
\[ \mathrm{SC}_\mu(c)=\sum_{t\in T}\mu_t\,\delta(t,c). \]
This could represent a large municipal electorate, an online political platform, or a national election whose voters fall into a few stable issue-position and demographic clusters. The low-dimensional metric is not being mistaken for the continuization: the continuous object is the population measure \(\mu\). If \(\mu_t=a_t/N\), cloning type \(t\) into \(a_t\) voters reproduces plurality masses and multiplies every social cost by \(N\), so distortion ratios are unchanged.
My lead mirror is COORDINATION\(_\infty\)-Metric Winner, based on Theorem 4.3, proved in this paper. The paper proves that its COORDINATION dynamics produce a candidate with distortion at most \(11\); Theorem 1.5 is the corresponding summary statement, also proved here.
An instance consists of:
During exploration round \(r\), every type \(t\) assigns all its mass \(\mu_t\) to its most-preferred candidate not already placed in its list. Thus the action variables are
\[ v^{(r)}_{t,c}\in\{0,\mu_t\}, \qquad \sum_{c\in C}v^{(r)}_{t,c}=\mu_t. \]
After the exploration rounds, candidate \(c\) is considered viable once its accumulated mass reaches \(1/2\). In the exploitation phase, each type supports the first viable candidate in its list, exactly as in the paper. The output is the resulting winner \(w\), together with its exact continuous distortion
\[ D_\mu(w)= \frac{\mathrm{SC}_\mu(w)} {\min_{c\in C}\mathrm{SC}_\mu(c)}. \]
A solution is the winner, the induced type-level transcript, and the exact value of \(D_\mu(w)\). The process can be simulated in polynomial time in \(m\), \(\tau\), and the input bit length; no individual voter needs to be represented. The proof of Theorem 4.3 transfers almost verbatim: every occurrence of a count divided by \(n\) becomes a mass, and the crucial threshold \(n/2\) becomes \(1/2\).
This is the strongest mirror because it preserves the paper’s object exactly. The agents do not become fractional voters with new powers; identical types simply act identically under the deterministic exploration rule. The metric objective remains indivisible candidate selection, not a fractional outcome. I would expect this mirror to be tractable—an A-like case—but that is a classification of the mirror, not a complexity theorem supplied by the paper. Further questions include whether the constant \(11\) can be improved in the finite-type model, how sensitive the result is to approximate mass information, and whether one can optimize over admissible tie-breaking rules.
A second, more central but weaker mirror is Parallel-Universe STV\(_\infty\)-Distortion, based on Theorem 1.2, proved here; its detailed proof appears as Theorem 3.2. The theorem states that if the underlying metric has doubling dimension \(d\), STV has distortion \(O(d\log\log m)\). Corollary 1.3 gives the low-dimensional Euclidean specialization, and Theorem 3.3 supplies a matching-direction lower bound of \(\Omega(\sqrt d)\), also proved here.
For a continuous instance, let \(p_\mu(a\mid S)\) be the mass whose top-ranked active candidate in \(S\subseteq C\) is \(a\). An admissible elimination sequence repeatedly removes a candidate of minimum \(p_\mu(a\mid S)\). Let \(W_{\mathrm{STV}}(\mu)\) be the set of candidates that can survive under some such sequence. The computational problem is:
\[ \mathrm{PDSTV}_\infty: \quad \text{compute } \max_{w\in W_{\mathrm{STV}}(\mu)} \frac{\mathrm{SC}_\mu(w)} {\min_{c\in C}\mathrm{SC}_\mu(c)}, \]
and return a maximizing candidate together with an elimination sequence witnessing membership in \(W_{\mathrm{STV}}(\mu)\).
The input is \(C\), \(T\), rational \(\mu\), the type rankings, a rational metric of doubling dimension at most \(d\), and the tie convention. This is author-recognizable as STV: only voter multiplicities have become masses, while candidates, rankings, plurality support, elimination, and the social-cost benchmark remain unchanged. Clearing denominators recovers the corresponding finite high-multiplicity election.
For a fixed elimination sequence, evaluation is polynomial in \(m\) and \(\tau\). The genuinely interesting version maximizes over possible elimination sequences. I expect any hardness here to be Class B rather than population-specific: the combinatorics lie in the \(m\)-candidate elimination agenda, not in the number of voters. Continuization may compress support computation, but it does not obviously remove the difficulty of choosing among exponentially many elimination histories. The paper does not prove such a complexity classification, so this remains a proposed research question rather than an attributed result.
This mirror also gives a useful boundary. Theorem 3.3’s lower-bound construction is finite and candidate-geometric; after rational weighting or cloning, its distortion obstruction should persist. Thus the continuous population model should not be expected to erase lower bounds whose source is candidate geometry or elimination structure. The natural follow-ups are whether the \(O(d\log\log m)\) guarantee becomes \(O(d)\) in the mass model, as conjectured in Conjecture 1.4, and whether parallel-universe STV distortion can be computed or approximated in time polynomial in \(m\), \(\tau\), and the mass bit length.
The mirror covers Theorem 4.3 most convincingly, and Theorem 1.2 secondarily. It does not cover the paper’s cited prior bounds, Question 1, Question 2, or Conjecture 1.4 as established computational results. Theorem 3.3 is best treated as a boundary test, not as a hardness anchor.
The weakest point is decisive under the strict ChoCo rubric: the paper’s results are distortion and convergence theorems, not complexity results. The continuous questions above are faithful and computationally formulable, but they do not demonstrate that a discrete complexity barrier dissolves in the continuum. Moreover, for this particular paper, much of the mass formulation is already implicit in the proofs’ use of voter fractions. My positive claim is therefore modest: this is a credible high-multiplicity mirror, with a particularly clean tractable version for COORDINATION, but not strong evidence by itself for the programme’s main complexity-landscape thesis.
The decisive objection is the paper’s lack of a qualifying computational anchor. Theorem 1.2, Theorem 3.2, Theorem 3.3, Theorem 4.3, and Theorem 1.5 are distortion, convergence, and existential performance statements. None asserts the complexity of a computational problem, gives an exact, approximation, or parameterized algorithm, or proves hardness. Under ChoCo’s source gate, that is decisive: the proposed continuous problems are inventions around the paper, not continuizations of computational results established by it.
The COORDINATION mirror is the cleanest example. With types containing rankings, metric information, and tie-breaking data, the dynamics can certainly be run on masses. A type of mass \(\mu_t\) casts one batch vote, plurality scores are weighted sums, and the \(1/2\) threshold is well-defined. The resulting transcript and
\[ \frac{\mathrm{SC}_\mu(w)}{\min_{c\in C}\mathrm{SC}_\mu(c)} \]
are computable directly in polynomial time in \(m\), \(\tau\), and the encoding length. But this is merely the execution of a fixed finite-state process on weighted votes. If \(\mu_t=a_t/N\), expanding the types into \(a_t\) identical voters reproduces the same transcript exactly. If one does not expand them, one has the standard high-multiplicity representation.
That is not an objection that the continuous answer is easy. It is the more basic point that Theorem 4.3 never posed a computational problem whose complexity could change. Its proof already reasons in fractions such as \(|W|/n\); replacing them by masses is a notational and representational generalization of the theorem, not the relaxation of a computational task. The continuous version therefore supplies no LP, pricing problem, optimization barrier, or discrete complexity phenomenon for ChoCo to investigate.
One could improve the proposed mirror by asking for the tie-breaking rule that maximizes or minimizes distortion, or for the minimum mass of voters that must change type to make a target win. Those could be reasonable new control or manipulation problems. They would also cease to be mirrors of Theorem 4.3: the paper fixes the dynamics and proves their guarantee, whereas the new problem introduces an external optimization layer absent from the result. It is always possible to invent such a problem around a voting rule, but that cannot make this paper a computational continuization anchor.
The STV mirror has a similar defect, although its finite-type regime is entirely sensible. Given \(\mu\), one can compute every candidate’s current support by weighted tallying, and a fixed elimination sequence can be checked efficiently. Theorem 1.2 is not an algorithm for finding a worst distortion winner, however; it is a universal bound applying to every metric and every admissible STV outcome. The proposed problem
\[ \max_{w\in W_{\mathrm{STV}}(\mu)} \frac{\mathrm{SC}_\mu(w)} {\min_{c\in C}\mathrm{SC}_\mu(c)} \]
is therefore a new possible-winner problem, not a computational formulation supplied by the theorem.
Its difficult part, if any, is the choice among elimination histories indexed by the \(m\) candidates. Population multiplicity is only supplying weighted plurality scores. That does not make the question illegitimate—hardness driven by the agenda could still be a valuable Class B result—but it means the proposed difficulty is not created by continuizing the population. The paper’s dimensionality theorem gives no algorithmic handle on that problem. Doubling dimension is a promise about the finite metric geometry, not a continuous population variable.
A genuinely spatial version with a density over a low-dimensional region is no better as a mirror. It requires a representation of that density—piecewise constant data, an oracle, a circuit, or something similar—before computational complexity is even defined. If the density is instead represented by finitely many clusters, the problem returns to the weighted finite-type model above. Thus the better spatial interpretation either leaves the paper’s finite computational setting or collapses back to high-multiplicity STV.
Theorem 3.3 does not rescue the case. Its lower-bound construction is already finite. Rationally weighting or cloning its voter locations preserves the distortion ratio, which is evidence that a high-multiplicity regime is sensible. But that is supporting evidence for ChoCo, not a continuous computational result. Asking whether the worst distortion over all mass distributions and doubling metrics equals some bound would be a new extremal geometry problem, with a new input and optimization domain; it is not a complexity mirror of the theorem.
The proponent is right that repeated spatial voter types are plausible, and no identity-based or measure-zero objection defeats these constructions. The honest negative case is therefore not that no weighted or population-based study could ever be worthwhile. It is that none of the paper’s named results supplies the kind of computational problem ChoCo is designed to continuize. The proposed mirrors are faithful weighted reformulations and potentially useful new projects, but they cannot support the stronger claim that this paper contributes to the programme’s computational complexity landscape.
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.