d4-conf-atal-2009-0232

The strongest mirror is the paper’s sequential-elimination election interpretation. Take candidates \(C\) and a continuous electorate \(\mu\) over complete rankings of \(C\), with each ranking assigned a binary-rational mass and \(\sum_t\mu_t=1\). For candidates \(a,b\), let
\[ \Delta_\mu(a,b)=\sum_t\mu_t\bigl(\mathbf 1[a\succ_t b]-\mathbf 1[b\succ_t a]\bigr). \]
Set \(P^\mu_{ab}=1\) when \(\Delta_\mu(a,b)>0\), \(P^\mu_{ab}=0\) when it is negative, and \(P^\mu_{ab}=\tfrac12\) when it is zero. Thus each pairwise contest follows the electorate’s majority, with a fair coin breaking an exact tie.

Call the resulting problem Continuous Majority Balanced Agenda Control. An instance consists of \(C\), the supported rankings and their masses, a target candidate \(c^\star\), and a rational threshold \(\delta\). Ask whether there is a balanced binary tree with leaves seeded by the candidates such that \(q(c^\star,KT;P^\mu)\ge\delta\), using the paper’s recursive definition of tournament-winning probability. A solution is that tree and seeding. The objective is to maximize the probability that \(c^\star\) wins.

This is a credible high-multiplicity regime: a large electorate may contain millions of voters but only a moderate number \(\tau\) of distinct rankings. The masses express ballot shares directly. The paper itself says knockout tournaments are isomorphic to sequential pairwise-elimination elections and identifies the tree and seeding as the agenda-control choices. The mirror keeps those choices, the balanced-format constraint, and the target-winner objective; the continuous object is the electorate.

My anchor is Theorem 3, proved in this paper. It states that, given players \(N\), a pairwise winning-probability matrix with every \(P_{ij}\in\{0,1,\tfrac12\}\), a target \(k\), and threshold \(\delta\), it is NP-complete to decide whether there is a balanced knockout tournament \(KT\) with \(q(k,KT)\ge\delta\). The paper proves this by a reduction from Vertex Cover in the appendix. This is the best anchor because it gives hardness even with only win, lose, and tie outcomes, rather than relying on arbitrary probabilities.

I expect the continuous problem’s difficulty, if hardness holds on its domain, to be Class B: once \(\mu\) induces \(P^\mu\), the schedule’s combinatorics still lie in the number of candidates and the balanced agenda. The electorate’s scale does not enter the tree search. But Theorem 3 does not by itself prove hardness for this mirror: it allows arbitrary win–lose–tie matrices, whereas a matrix induced by a distribution over rankings must satisfy additional constraints. The key follow-up is whether the paper’s hard instances, or another hard family, can be realized by polynomial-size rational ranking distributions. It would also be useful to ask whether hardness persists when \(\tau\) is small relative to \(|C|\), and whether fixed \(|C|\) or fixed \(\tau\) yields useful algorithms.

The mirror covers the balanced win–lose–tie schedule-control result, not the paper’s general tournament model or its \(\epsilon\)-monotonic-probability result. Its weakest point is that realization gap: the continuous electorate makes the question natural and well-defined, but the paper’s reduction may not survive the restriction to majority matrices induced by rankings. That is a real proof obligation, not a reason to dismiss the mirror.