d4-conf-atal-2015-0121

A credible high-multiplicity regime is a large party-based election in which many people follow a relatively small set of declared rankings: for example, a membership election with hundreds of thousands of voters and a few dozen party blocs. A type is a bloc’s complete ranking of the candidates; its mass \(\mu_t\) is the fraction of the electorate in that bloc. A proposed move transfers some mass from other blocs to one destination bloc, whose ranking the transferred voters then follow. This keeps the paper’s central action—switching to one party—and makes the size of a move a share of the population. I would use instances with one bloc per ranking, so party identity does not distinguish otherwise identical types.

My lead anchor is Theorem 6, proved in the paper by reduction from X3C. It says that One-Destination-Max for Borda is NP-hard: given a party election, a positive threshold \(k\), and a candidate \(p\) who is initially the unique winner, decide whether there is a destination party such that at least \(k\) voters outside it switch to it and \(p\) remains the unique winner. The paper’s reduction makes the threshold \(n-m/3\), where \(n\) is the number of sets and \(m\) is the size of the ground set.

I would ask the corresponding question as Continuous One-Destination Borda-Max. Its input is a candidate set \(C\), a finite support \(T\) of rankings with rational masses \(\mu_t\) summing to \(1\), a distinguished candidate \(p\) who is initially the unique Borda winner, and a rational threshold \(\kappa>0\). Is there a destination ranking \(d\in T\) and transfer amounts \(x_t\), for \(t\ne d\), with \(0\le x_t\le\mu_t\) and \(\sum_{t\ne d}x_t\ge\kappa\), such that the resulting society has masses \(\mu'_t=\mu_t-x_t\) for \(t\ne d\) and \(\mu'_d=\mu_d+\sum_{t\ne d}x_t\), and \(p\) remains the unique Borda winner? A solution is the destination \(d\) and a transfer vector \(x\) meeting those conditions. This is the same strategic question as Theorem 6, with \(k\) measured as a fraction of the population.

I expect this mirror to be tractable. For each possible destination \(d\), Borda’s requirement that \(p\) strictly outscore every other candidate is a set of linear inequalities in \(x\). Strictness can be handled by asking an LP to maximize a common score margin \(\epsilon\) and checking whether the optimum is positive. Trying all \(\tau=|T|\) destinations gives a polynomial-time algorithm in \(m,\tau,L\), where \(L\) is the input bit length. The follow-up question is how the continuous optimum relates to finite-electorate MAX: in particular, what additive rounding loss can be guaranteed as a function of the number of types and the initial Borda margins?

A second, independently credible anchor is Theorem 7, also proved in the paper, by an X3C reduction. It says that One-Destination-Max for the Condorcet voting rule is NP-hard. In the paper’s unique-winner setting, the question is whether at least \(k\) voters can switch to one destination party while the initially winning candidate \(p\) remains the unique winner.

The matching problem is Continuous One-Destination Condorcet-Max. Use the same input and transfer variables, with \(p\) initially the unique Condorcet winner; ask whether some destination \(d\) and transfer vector of total mass at least \(\kappa\) leave \(p\) beating every other candidate pairwise. The output is again \(d\) and \(x\). I also expect this version to be tractable: each pairwise margin is affine in the transferred masses, so for each destination the question is a linear feasibility problem with strict margin constraints. A common margin variable \(\epsilon>0\) handles strict Condorcet victories. Further questions include how the answer changes near pairwise ties, and what margin guarantees suffice to round a continuous solution to a finite electorate.

These are strong mirrors because the paper’s authors would recognize both the operation and the success condition: choose one destination party, move members of other parties to it, and test whether the predicted winner survives. I am covering only Theorems 6 and 7, not claiming a mirror for the paper’s other results. The continuous questions make sense on their own even if their answers are easy; the paper’s hardness results then pose the programme’s intended question of whether indivisibility is doing the hard work.

The weakest point is also the source of the expected tractability: the X3C reductions rely on selecting whole voters, while a continuous society permits partial transfers from each type. That can erase the reductions’ combinatorial choices. This means the mirrors may dissolve the hardness rather than preserve it. It is a real relaxation, but it remains a faithful high-multiplicity version of the paper’s switching problem: transferred mass still changes its ranking to the destination’s, and the one-destination restriction and winner test remain intact.