d4-conf-ecai-2020-0253

There is a credible continuous mirror here. The lead is Theorem 4.3, because Condorcet control in the paper is determined entirely by pairwise comparisons with the target, which become linear constraints on voter mass.

Use a type for each complete ranking together with everything that affects control eligibility. Let \(\mu_t\) be the registered mass of type \(t\), and \(\nu_t\) the available unregistered mass. These are binary rationals, measured against a reference population; take \(\sum_t\mu_t=1\). The number of people \(N\) can be much larger than the number of supported types \(\tau\). For example, a large consultation on a fixed candidate slate could have many thousands of voters but only a few dozen recurring rankings. Some ballot types could be available to recruit, while others are already registered.

For a chosen type, the controller changes a mass \(x_t\): in an adding problem, \(0\le x_t\le\nu_t\); in a deleting problem, \(0\le x_t\le\mu_t\). The cost is \(\sum_t x_t\), and the decision question is whether the target can become the unique winner with cost at most a given budget \(b\). This makes “control at most \(b\%\) of the electorate” the mass version of the paper’s “control at most \(\ell\) voters.” The fractional \(x_t\) represents a proportion of a continuum cohort, while each actual ballot remains a complete ranking.

Using the full-version theorem numbering, the three anchors are:

Theorem 4.3, proved in this paper: CCAV and CCDV for Condorcet in \(3\)-CP elections are \(\mathrm{NP}\)-hard. The paper reduces RX3C to both variants. [Full version, Theorem 4.3](https://arxiv.org/pdf/2002.03539#page=11)

Its mirror is 3-CP Condorcet Mass Control. The instance gives a candidate set, a \(3\)-partition of it, registered and available masses over complete rankings, a target \(p\), a budget \(b\), and an add/delete mode. Every supported ranking must be single-peaked when restricted to each block. The question is whether there is an allowed mass vector \(x\) of cost at most \(b\) that makes \(p\) the Condorcet winner. For each opponent \(c\), define the pairwise margin \(D_\rho(p,c)=\sum_t\rho_t\bigl(\mathbf 1[p\succ_t c]-\mathbf 1[c\succ_t p]\bigr)\). In add mode require \(D_{\mu+x}(p,c)>0\) for every \(c\ne p\); in delete mode require \(D_{\mu-x}(p,c)>0\). This mirrors the paper’s unique-winner condition: under its Condorcet correspondence, \(p\) is the unique winner exactly when it beats every opponent.

Theorem 3.3, proved in this paper: for every fixed \(r\ge4\), CCAV for \(r\)-approval in \(3\)-CP elections is \(\mathrm{NP}\)-hard. The proof reduces RX3C. [Full version, Theorem 3.3](https://arxiv.org/pdf/2002.03539#page=5)

Its mirror, 3-CP \(r\)-Approval Add-Mass, has the same registered and available masses, target, budget, and \(3\)-candidate-block structure. Write \(A_\rho(c)=\sum_t\rho_t\mathbf 1[c\text{ is in the top }r\text{ of }t]\). A solution is a vector \(x\) with \(0\le x_t\le\nu_t\), \(\sum_t x_t\le b\), and \(A_{\mu+x}(p)>A_{\mu+x}(c)\) for every other candidate \(c\).

Theorem 3.5, proved in this paper: for every fixed \(r\ge3\), CCDV for \(r\)-approval is \(\mathrm{NP}\)-hard even when the election is both \(2\)-axes single-peaked and \(2\)-CP single-peaked. Its proof also uses RX3C. [Full version, Theorem 3.5](https://arxiv.org/pdf/2002.03539#page=7)

Its mirror, 2-Axes-and-2-CP \(r\)-Approval Delete-Mass, gives the two axes and the \(2\)-partition as witnesses, along with registered masses, target, and budget. Every type must meet both domain restrictions. A solution is \(x\) with \(0\le x_t\le\mu_t\), \(\sum_t x_t\le b\), and \(A_{\mu-x}(p)>A_{\mu-x}(c)\) for every \(c\ne p\).

All three mass problems are expected to be Class A. Each has only \(\tau\) action variables and one winning constraint per opponent. The coefficients are computed from the explicitly listed rankings, so the support is not an exponentially large implicit type space. Strict victory is handled exactly by adding a slack variable \(\delta\) to each margin constraint and maximizing \(\delta\); a positive optimum is equivalent to a strict win. Thus these are linear programs of size polynomial in \(m\), \(\tau\), and the mass bit length \(L\). The nearly single-peaked conditions remain part of the instance, rather than being replaced by outcome or probability continuity.

The authors should recognize these as their control problems with the electorate measured in mass: the rule, target, eligible population, budget, and preference restriction all remain in place. The scenario is an electorate with repeated complete ballots over a fixed slate, where \(\tau\) is small relative to \(N\); \(3\)-CP captures voters who are single-peaked within each of three candidate blocks, while the other anchor captures a mixture of two single-peaked axes. The high-multiplicity-election literature supports treating such a regime as a sensible object. This is not a claim that the paper already studies a continuous society.

The finite-to-continuous bridge is explicit. A discrete population with \(n_t\) ballots of type \(t\) gives \(\mu_t=n_t/N\); a discrete control action gives a mass action on the grid of multiples of \(1/N\). The continuous problem allows off-grid actions. Conversely, a rational mass solution can be scaled to a finite electorate by clearing its denominators. What it does not settle is the fixed-\(N\) integrality gap: an LP solution may use a fraction of a type that the discrete controller cannot select. That is the main follow-up—bound the rounding error as \(N\) grows, especially when the target’s winning margin is small. A second question is whether jointly choosing an unknown axes or candidate partition changes the continuous complexity.

My weakest point is that divisible control is a substantive relaxation: the paper selects individual votes, while these mirrors allow control of part of a type’s mass. That is the intended population-level change, and the type retains every distinction the paper’s problem uses—ranking and control eligibility—but a reader who requires whole-cohort or person-by-person actions may reject it. The mirror covers only Theorems 3.3, 3.5, and 4.3; it makes no claim about the paper’s Copeland, Maximin, recognition, or other results.