| paper | Computational Complexity of Verifying the Group No-show Paradox |
| authors | Farhad Mohsin, Qishen Han, Sikai Ruan, Pin-Yu Chen, Francesca Rossi, Lirong Xia |
| venue | IJCAI 2024 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4
statement extracted from the paper’s text layer
Given candidates \(C\), ranking types \(T=L(C)\), a rational society \(\mu\in\mathbb{Q}_{\ge 0}^{T}\) with \(\sum_t\mu_t=1\), and lexicographic tie-breaking, let \(a=\mathrm{STV}(\mu)\). Decide whether there exist \(b\ne a\) and rational abstention masses \(\nu_t\) such that \(0\le\nu_t\le\mu_t\), \(\sum_t\nu_t>0\), \(\nu_t>0\Rightarrow b\succ_t a\), and \(\mathrm{STV}(\mu-\nu)=b\).
A high-multiplicity STV electorate has ranking types \(t\in L(C)\), masses \(\mu_t\), and abstention variables \(\nu_t\); the decision objective is existence, with natural refinement \(\min\sum_t\nu_t\).
The mirror covers Theorem 4's STV NP-completeness result and its verification problem. It leaves Theorems 1–3, Proposition 1, the ILP and BFS algorithms, and the empirical likelihood results outside the mirror.
The strongest mirror is a direct high-multiplicity version of the paper’s Theorem 4.
Theorem 4 (STV), proved in this paper with the full proof in Appendix B.4, states that GNSP-STV is NP-complete under several tie-breaking mechanisms, including lexicographic tie-breaking. I would mirror it with the following problem, which I would call \( \mathrm{GNSP}^{\infty}\text{-}\mathrm{STV} \).
Let \(C\) be the candidates and \(T=L(C)\) the set of complete rankings. The input is a rational society \( \mu\in\mathbb{Q}_{\ge0}^{T} \) with \( \sum_t\mu_t=1 \), together with lexicographic tie-breaking. Let \(a=\mathrm{STV}(\mu)\). We ask whether there exist a different candidate \(b\) and a rational abstention-mass vector \( \nu\) such that
\[ 0\le \nu_t\le \mu_t, \qquad \nu_t>0\Longrightarrow b\succ_t a, \qquad \sum_t\nu_t>0, \]
and
\[ \mathrm{STV}(\mu-\nu)=b. \]
A solution is the pair \( (b,\nu)\). Thus \( \nu_t\) is the fraction of society of ranking type \(t\) that abstains; every abstaining type must prefer the new winner \(b\) to the original winner \(a\). The underlying decision problem is exactly the paper’s verification question, with integer counts replaced by rational masses. Minimizing \( \sum_t\nu_t\) would be a natural optimization refinement, but is not needed for the mirror.
This is a credible regime. Imagine a very large election whose voters fall into a comparatively small number of recurring preference templates: party supporters, demographic cohorts, or issue-based blocs with the same complete ranking. The population may have millions of members while the number of distinct rankings is moderate. That is not an artificial reinterpretation of this paper: its own ILP formulation groups agents by identical rankings, introduces their multiplicities \(n_i\), and uses the remaining counts \(x_i\) after abstention. Its experiments explicitly report that performance depends much more on the number of unique rankings than on the number of agents. The continuous model simply replaces \(n_i\) and \(x_i\) by masses.
The high-multiplicity correspondence is exact. If \( \mu_t=n_t/N\) and \( \nu_t=k_t/N\), then clearing denominators recovers a finite profile with \(n_t\) voters of type \(t\), of whom \(k_t\) abstain. Conversely, any rational mass solution can be lifted to a sufficiently large population of clones. STV’s plurality tallies are homogeneous under scaling, so the elimination order and all tie-breaking decisions are preserved. Nothing about the outcome is fractionalized: candidates and rankings remain discrete; only the population multiplicities become continuous.
I expect this mirror to be Class A in the programme’s natural \( \operatorname{poly}(m,\tau,L)\) sense. Guess a new winner \(b\) and an STV elimination order
\[ \pi=(\pi_1,\ldots,\pi_{m-1}) \]
whose final surviving candidate is \(b\). Once \( \pi\) is fixed, every type’s vote in every round goes to a known top-ranked surviving candidate. Hence every round’s plurality tally is a linear function of the residual masses \( \rho=\mu-\nu\). The conditions saying that \( \pi_j\) is the lexicographically selected lowest-scoring candidate in round \(j\) are therefore linear inequalities, with strict inequalities used exactly where lexicographic tie-breaking requires them. Together with the capacity constraints on \( \nu\) and the preference constraints \( \nu_t=0\) whenever \(b\not\succ_t a\), this gives a rational LP.
There are at most \(m!\) elimination orders and \(m\) choices of \(b\). Since the full ranking type space has \( \tau=m!\) types, enumerating all orders is polynomial in \(m\) and \(\tau\), though of course not polynomial in \(m\) alone. Solving the resulting LPs would decide \( \mathrm{GNSP}^{\infty}\text{-}\mathrm{STV}\). The discrete NP-hardness can therefore disappear because the hard choice of an integral subset of voters becomes a mass-allocation problem, while the remaining sequential structure is handled by enumerating the agenda orders.
The main further questions are whether the enumeration can be improved for sparse-support societies, whether the minimum abstaining mass has a compact formulation, and how closely continuous solutions can be rounded back to finite elections while preserving all STV elimination margins.
My weakest point is the representation assumption. The Class-A argument is polynomial in the programme’s explicit type-space parameter \( \tau\), as required by the continuization programme, but it is not automatically polynomial in \(m\) and the number \(K\) of types with positive mass: when \(K\ll m!\), enumerating all elimination orders may be too expensive. The sparse-support version could itself be harder or remain open. That is a genuine limitation, but it does not undermine the mirror: the full-population mass problem is still exactly the paper’s group no-show problem in the regime the paper’s own ILP experiments identify as meaningful.
I cannot make a defensible negative case against this anchor. The proposed \( \mathrm{GNSP}^{\infty}\text{-}\mathrm{STV} \) is a particularly clean population continuization.
The problem is anonymous: an agent matters only through their ranking, and the abstention condition depends only on whether \(b\succ_t a\). Replacing a group of identical voters by an abstaining mass \( \nu_t\) therefore loses no information about the paper’s question. Rational instances correspond exactly in both directions: if \( \mu_t=n_t/N\) and \( \nu_t=k_t/N\), one recovers a finite profile; conversely, clearing denominators lifts any rational mass instance to a finite election. STV’s plurality scores are homogeneous, so scaling preserves every elimination and tie-breaking decision.
Nor does the continuum degenerate. The existence question remains meaningful because the abstaining mass may need to cross a positive STV threshold. The natural refinement—minimum abstaining mass—is even more clearly a robustness problem. The fact that a profile exactly on an elimination boundary may admit arbitrarily small abstention is a feature of the robustness geometry, not a collapse of the model.
The strongest objection is to the complexity claim, not to the mirror itself. Fixing \(b\) and an elimination order makes every round’s tally a linear function of the residual masses. Lexicographic tie-breaking contributes strict or weak linear inequalities, which can be handled by standard rational LP feasibility techniques. Enumerating all elimination orders takes \(O(m!)\) cases, which is polynomial in the programme’s explicit type-space parameter \( \tau=m!\). Thus the claimed Class-A result is valid under the programme’s stated \( \operatorname{poly}(m,\tau,L)\) convention.
There is a genuine limitation: this is not automatically polynomial in \(m\) and the number \(K\) of positive-support rankings. A support-sensitive version could be substantially harder, and the paper’s reduction itself uses carefully distinguished ranking types. But that limits the strength of the result; it does not show that the continuous question is ill-posed or uninteresting. A large election with recurring party, demographic, or issue-based ranking blocs is precisely a credible high-multiplicity regime, and the paper’s own ILP experiments identify the number of unique rankings—not the number of named voters—as the relevant structural parameter.
Existing work on variable electorates, no-show likelihoods, and high-multiplicity elections would support this mirror rather than defeat it; none of the material supplied gives a continuous computational treatment of rational-mass GNSP for STV. Consequently, the universal negative claim fails on its only anchor: Theorem 4 does have a worthwhile continuous mirror.
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.