d4-conf-atal-2017-0263

My lead mirror is Mass-RCG Best Response, anchored in Proposition 1, proved in this paper. Proposition 1 says that for a lexicographically tie-broken voting rule \(V=V_{\mathrm{lex}}\), if the underlying rule \(F\) can compute an outcome on \(n\) voters and \(m\) candidates in time \(O(T_{n,m})\), then, for any candidate and fixed positions of the other candidates, the candidate’s full best-response set can be computed in \(O(nm[T_{n,m}+\log m])\). Thus best responses are polynomial-time computable whenever \(F\) is. This is an algorithmic anchor, not a hardness result; the paper’s numbered equilibrium existence and nonexistence propositions are not computational-complexity results.

In the mirror, a voter type is an ideal point \(q_t\) on the paper’s political axis. A society is a finite-support distribution \(\mu\): each rational mass \(\mu_t\) is the fraction of the electorate at \(q_t\), and \(\sum_t\mu_t=1\). Suppose there are \(m\) candidates, the other candidates’ positions are fixed, and candidate \(c\) may choose any position \(x\) in a rational interval \(I_c\). Each type ranks candidates by distance from its ideal point, resolving equal distances by the paper’s fixed lexicographic order. Use a fixed rational positional scoring rule, with the election winner also selected lexicographically among candidates tied for highest score. Candidate \(c\) retains its preference order \(\succ_c\) over winners.

The problem asks for the set
\[ BR_c=\{x\in I_c: W(x)\succeq_c W(y)\text{ for every }y\in I_c\}, \]
where \(W(x)\) is the winning candidate when \(c\) chooses \(x\). Represent the answer as a union of intervals and individual breakpoint positions, so the full best-response set is specified exactly. This is the underlying strategic positioning problem from the paper; it does not ask the prover to compute an encoding.

A plausible regime is a large primary or party election with many voters concentrated at a modest number \(\tau\) of shared ideological positions. For example, millions of voters might belong to a few dozen stable platform groups. The type is the ideal point that determines all voter preferences used by the model; mass is the group’s share of the electorate. The number of people can greatly exceed \(\tau\), while candidates still choose positions continuously and retain their possibly non-selfish preferences over election winners.

I expect this mirror to be tractable (Class A). As \(c\) moves, a type’s ranking can change only at positions where \(c\) ties an opponent in distance. With \(\tau\) types and \(m\) candidates, these points partition \(I_c\) into polynomially many cells. Within each cell the weighted preference profile and winner are constant. Evaluating each cell and its boundary points therefore gives an exact polynomial-time algorithm in \(m,\tau\), and the rational input bit length \(L\). This adapts Proposition 1’s breakpoint idea to mass input; it is not a claim that the paper already proved this mass version. It also gives a useful high-multiplicity input measure: the computation can depend on the number of distinct ideal points rather than the electorate size.

The scope is deliberately narrow: this mirrors Proposition 1’s best-response computation, not the paper’s Nash-equilibrium existence results. It raises follow-up questions about the formal relationship between mass best responses and finite profiles with proportions \(n_t/n\), about richer representations such as piecewise-constant ideal-point densities, and about whether pure equilibria can be computed in the mass model. The last question connects to a direction the paper itself leaves open.

The weakest point is that the paper explicitly builds on Hotelling–Downs, whose voter distribution is already non-atomic. A plurality version of this proposal would sit especially close to that prior model. The distinction here is that the paper’s formal RCG input is still a finite vector of \(n\) voter positions, while this question combines a population measure with strategic candidates, their preferences over winners, and scoring-rule best responses. The paper itself observes that non-atomic Hotelling–Downs models had been limited to particular voting-rule variants, whereas RCGs permit broader rules. That makes this a credible mirror of the paper’s formal computational question, though a modest one: its strongest contribution is the population-based input and parameterization, not a predicted dissolution of discrete hardness.