d4-conf-aaai-2010-0117

The strongest mirror I can defend is narrow: take an election with many voters but relatively few distinct rankings, and represent it by the fraction of voters holding each ranking. For example, a large membership election may have millions of voters but ballots drawn from a small recurring set. A type is a complete ranking \(t\in L(A)\); its mass \(\mu_t\) is its share of the electorate.

My closest named anchor is Theorem 3, proved in this paper, with its proof relegated to the full version. It states that no strategyproof randomized voting rule can approximate Plurality to a factor of \(\omega(1/\sqrt m)\). That is, as the number \(m\) of alternatives grows, no such rule guarantees a factor asymptotically larger than \(1/\sqrt m\).

Here is the continuous question I would hand to a prover:

High-Multiplicity Continuous Plurality Approximation under Strategyproofness. The target is an alternative set \(A\), with \(|A|=m\), and the domain is every society \(\mu\in\Delta(L(A))\). Define the per-capita Plurality score
\[ p_\mu(a)=\sum_{t:\,a\text{ is ranked first in }t}\mu_t. \]
Find the largest guarantee \(\gamma_m\) for which there is a lottery rule \(\Phi:\Delta(L(A))\to\Delta(A)\) satisfying
\[ \sum_{a\in A}\Phi(a\mid\mu)\,p_\mu(a) \ge \gamma_m\max_{a\in A}p_\mu(a) \]
for every \(\mu\) with positive optimal score.

To keep strategyproofness meaningful, count \(\Phi\) as admissible only if it is a limit of anonymous, strategyproof \(N\)-voter rules: whenever empirical distributions \(\mu_N\) converge to \(\mu\), the corresponding lotteries converge to \(\Phi(\cdot\mid\mu)\). A solution is an admissible rule and its guarantee, or an upper-bound proof ruling out a larger guarantee. The question is whether the \(O(1/\sqrt m)\) impossibility in Theorem 3 survives this high-multiplicity limit.

I expect the finite result to transfer if its bound holds uniformly for the growing electorates used in the limit. In the programme’s three-way vocabulary, this is closest to hardness transferring: the desired negative bound comes from the finite strategic restriction on rules, and the mirror should reproduce it. That label is only an analogy here; the result is not a complexity-hardness theorem.

The fit has a clear limit. The paper’s numbered Theorems 2–8 give approximation guarantees for strategyproof mechanisms. Its introduction explicitly distinguishes this from computational approximation of hard-to-compute voting rules. It supplies no named classification of running time or computational hardness of bribery, control, campaigning, or robustness. So the proposed question is a coherent continuous version of the paper’s mechanism-design objective, but it is not a strong ChoCo computational anchor.

My weakest point is the incentive model. In a strictly atomless society, one voter has zero mass, so individual strategyproofness becomes vacuous for rules depending only on aggregate masses. The finite-rule lift preserves the paper’s incentive condition, but also retains finite-resolution strategic effects. The theorem’s stated voter-count quantification must be checked before claiming its bound survives when each type has many copies.