d4-conf-aaai-2014-0518

The lead mirror is Continuous Plurality Robust-Winner. Its anchor is Proposition 1, proved in the paper: a candidate \(x\in Y\) is a robust winner exactly when there is no destructive control by adding candidates, using the spoiler set \(U=X\setminus Y\). The paper then states that robust-winner checking is coNP-complete for plurality, deriving this from earlier NP-completeness results for destructive control by adding candidates. The numbering is slightly awkward: Proposition 1 proves the equivalence; the plurality complexity classification appears in the prose immediately after it, and its hardness input is cited from earlier work.

Here is the continuous problem. An instance gives candidates \(X\), a support \(\mathcal T\) of \(\tau\) complete rankings, rational masses \(\mu_\rho>0\) summing to \(1\), a set \(Y\subseteq X\) of known-available candidates, and a target \(x^\star\in Y\). Use the paper’s tie-breaking rule. For any \(A\) with \(Y\subseteq A\subseteq X\), candidate \(c\)’s plurality score is
\[ \operatorname{pl}_\mu(c,A) =\sum_{\rho\in\mathcal T:\,c=\operatorname{top}_{\rho}(A)}\mu_\rho . \]
The question is whether \(x^\star\) wins for every such \(A\). A NO answer has a compact witness: one available set \(A\) where \(x^\star\) loses. This is a decision problem about robust winner determination; it does not introduce a mass-transfer or querying action.

A credible regime is a large electorate ranking public projects or potential sites before costly feasibility studies. Many residents share a small number of complete ranking archetypes, so the population size \(N\) can greatly exceed \(\tau\); pending feasibility results determine which candidates survive. Each type is complete for this problem because its members have the same ranking, while availability and any inspection costs are candidate-level. The model leaves candidate availability discrete and continuizes the society, as required.

The expected result is coNP-completeness: hardness transfers. Map a discrete profile to \(\mu_\rho=n_\rho/n\), where \(n_\rho\) is the number of voters with ranking \(\rho\). For every available set, weighted plurality scores are the original scores divided by \(n\), so the winners are identical. This is a polynomial-size mapping from the paper’s discrete instances. Moreover, cloning every voter the same number of times leaves \(\mu\) unchanged: the underlying electorate can be made arbitrarily large relative to its number of distinct ranking types. The hard choices still concern subsets of candidates, so population continuization does not remove them. This is a useful Class B boundary, not a claim that the continuous representation makes the problem tractable.

A second, tractable mirror is Continuous Borda Robust-Winner, anchored by Corollary 1, proved in the paper from its characterizations. The corollary says that checking whether \(x\) is a robust winner can be done in polynomial time for top cycle, uncovered set, and Borda; I rely on its Borda entry. It uses the same instance schema, asking whether \(x^\star\) wins under Borda for every \(A\) containing \(Y\), with the paper’s unfavorable tie-breaking convention. Define
\[ B_\mu(c,A)=\sum_{\rho\in\mathcal T}\mu_\rho \bigl(|A|-\operatorname{pos}_{\rho|_A}(c)\bigr), \qquad N_\mu(a,b)=\sum_{\rho\in\mathcal T}\mu_\rho\,\mathbf 1[a\succ_\rho b]. \]
For each rival \(z\ne x^\star\), the paper’s Borda characterization reduces the check to one set:
\[ A_\mu(x^\star,z)=Y\cup\{z\}\cup \{u\in X\setminus(Y\cup\{z\}): N_\mu(z,u)>N_\mu(x^\star,u)\}. \]
The target must strictly outscore \(z\) at that set. Computing these sets and scores takes polynomial time in \(m,\tau\), and the input bit length \(L\); rational masses preserve the score comparisons. The expected direction is therefore tractable, Class A. This is an exact weighted-population extension of the paper’s result, not a claim that Borda robustness itself is newly tractable.

These mirrors cover robust-winner verification only. They do not continuize the paper’s decision-tree policies or availability probabilities. Those generate a further question: given \(\mu\), candidate availability probabilities, and query costs, can an optimal policy be computed substantially faster than the paper’s \(O(3^{|U|})\) dynamic program, perhaps using structure in the ranking support?

The weak point is that both mirrors retain the paper’s candidate-subset problem, and both can be expressed through rational type frequencies. The plurality mirror transfers hardness rather than dissolving it; the Borda mirror carries over an existing polynomial characterization. The case is strongest as a faithful high-multiplicity classification of where robustness is hard and where it is tractable, not as evidence that this paper already contains a new continuous complexity result.