Insight into Voting Problem Complexity Using Randomized Classes

The paper admits a credible continuous mirror. Its strongest anchor is not an NP-hardness theorem—the paper contains no named NP-hard or NP-complete result—but its exact replacement result sits precisely on the integrality boundary that continuization is meant to test.

My lead anchor is Theorem 13, proved by the authors, with its proof deferred to the full version:

Exact Perfect Matching logspace many-one reduces to \(2\)-Approval-CCRV!.

The relevant continuous problem is Continuous Exact \(2\)-Approval Replacement, defined as follows. Let \(T\) be the finite set of complete rankings. An instance consists of rational registered mass \(\mu\in\mathbb{Q}_{\ge 0}^{T}\) with \(\sum_t\mu_t=1\), rational reserve mass \(\nu\in\mathbb{Q}_{\ge 0}^{T}\), a preferred candidate \(p\), and an exact replacement mass \(\rho\in\mathbb{Q}_{\ge0}\). Here \(\mu_t\) is the fraction of the registered electorate of type \(t\), while \(\nu_t\) is the available mass of unregistered voters of that type, measured in the same units. A finite election with \(N\) registered voters and \(k\) replacements embeds by taking \(\mu_t=n_t/N\), \(\nu_t=w_t/N\), and \(\rho=k/N\).

The chair chooses a mass-transfer matrix \(x_{t,u}\). It must satisfy \(x_{t,u}\ge0\), \(\sum_u x_{t,u}\le\mu_t\), \(\sum_t x_{t,u}\le\nu_u\), and \(\sum_{t,u}x_{t,u}=\rho\). The resulting society is \(\mu'_q=\mu_q-\sum_u x_{q,u}+\sum_t x_{t,q}\). The question is whether \(p\) is a \(2\)-Approval co-winner, namely whether, for every candidate \(c\),

\[ \sum_q\mu'_q\,\mathbf{1}[p\text{ is in the top two positions of }q] \ge \sum_q\mu'_q\,\mathbf{1}[c\text{ is in the top two positions of }q]. \]

A feasible rational \(x\) is the solution. The objective is feasibility at exactly \(\rho\), matching \(2\)-Approval-CCRV!.

This is a genuine high-multiplicity regime: millions of voters in a large referendum, polling panel, or controlled re-poll may fall into a few dozen or hundred recurring complete preference profiles, with \(\tau\ll N\). The reserve-versus-registered distinction can be interpreted as two ballot pools; it is admittedly less natural than adding voters, but it is exactly the paper’s formal replacement action, not a different voting rule or a fractional outcome. Mass is headcount normalized by \(N\), not a probability distribution over winners.

I would expect this continuous problem to be Class A. The formulation is already a linear program with \(O(\tau^2)\) transfer variables and \(O(\tau+m)\) relevant constraints, hence polynomial in \(m\), \(\tau\), and the rational encoding length. This is consistent with the paper’s Theorem 12, which reduces \(2\)-Approval-CCRV! to Exact Red-Blue Perfect Bipartite \(b\)-Matching: after continuization, the selected red and blue edges become fractional mass, so the matching gadget becomes a fractional \(b\)-matching or transportation LP.

The important point is that this does not trivialize the paper’s problem by changing its subject. Candidates remain discrete, rankings remain complete, the rule remains \(2\)-Approval, the action remains exact voter replacement, and the winner condition is unchanged. Only the indivisible choice of named voters becomes divisible population mass. That is precisely the high-multiplicity relaxation. Theorem 13’s Exact Perfect Matching equivalence therefore supplies a useful boundary experiment: the discrete difficulty may be caused by integral population selection and disappear in the continuum.

I would not claim that Theorem 13 proves hardness that dissolves. Exact Perfect Matching itself is in \(RP\) and is not known to be NP-hard. Nor does the theorem’s reduction establish that its hard-looking instances have \(\tau\ll N\); its edge-voters may be relatively sparse. The honest claim is narrower: \(2\)-Approval-CCRV! has a natural large-population regime, and its continuous version is a well-defined computational problem whose expected tractability explains what the discrete matching reduction is measuring.

A second, cleaner but less consequential anchor is Theorem 10, proved in this paper:

\(2\)-Approval-CCAV! is in \(P\).

Its mirror is Continuous Exact \(2\)-Approval Addition. Given \((\mu,\nu,p,\rho)\), choose \(z_t\) satisfying \(0\le z_t\le\nu_t\) and \(\sum_tz_t=\rho\). The final society is \(\mu'_t=\mu_t+z_t\), and the question is whether \(p\) is a \(2\)-Approval co-winner. Equivalently, for every \(c\),

\[ \sum_t(\mu_t+z_t)\mathbf{1}[p\text{ is top-two in }t] \ge \sum_t(\mu_t+z_t)\mathbf{1}[c\text{ is top-two in }t]. \]

This is a linear feasibility problem with \(\tau\) variables, so it is also Class A. Here the regime is especially plausible: a large electorate with a repeated distribution of eligible but currently unregistered voter types, and a chair conducting an exact-mass get-out-the-vote operation. This mirror covers the exact addition result, while the at-most version gives the analogous minimization problem.

The scope is therefore deliberately limited: I am claiming a strong mirror for the paper’s exact \(2\)-Approval control problems, especially Theorem 13’s replacement result, not for every First-Last statement or for Exact Perfect Matching itself. The resulting research questions include whether continuous solutions can be rounded back to finite elections with controlled score loss, whether the bound can depend on the number of occupied types rather than all \(m!\) rankings, and whether any natural type-level indivisibility condition preserves matching hardness.

The weakest point is the replacement story and the sparse nature of the paper’s matching reduction. If a referee insists that replacement is institutionally artificial or that the theorem’s reductions do not inhabit a genuine \(\tau\ll N\) regime, the case weakens. But the continuous problem itself remains faithful: it is the same voter-control question over a population with repeated types, and its LP tractability is exactly the kind of discrete-to-continuous separation the ChoCo programme is designed to investigate.