d4-conf-atal-2016-0303

The case I believe is a high-multiplicity limit of the paper’s lazy-voter equilibrium problem. Its population is described by type masses, while equilibrium is defined through larger and larger finite replications of those masses. This gives a continuous object to compute—limiting ballot masses—while retaining the one-voter deviations that make the paper’s Nash question meaningful.

Let \(T\) be the positive-mass support. A type \(t\) specifies a complete ranking \(\succ_t\), utility function \(u_t\), and lazy-voter attitude. The input gives rational masses \(\mu_t>0\), summing to \(1\), with \(\tau=|T|\). For each integer \(N\) such that every \(N\mu_t\) is integral, form an election with \(N\mu_t\) voters of type \(t\), using the paper’s lazy-voter utilities and, for example, \(\epsilon_N=1/(2m^2N^2)\). Require all types to be tie-consistent, and promise either a single-crossing order of the replicated voters or a common single-peaked candidate axis.

For each such \(N\), a ballot profile has normalized type-by-ballot masses
\[ x^{(N)}_{t,b}=\frac{|\{i:\operatorname{type}(i)=t,\ b_i=b\}|}{N}, \qquad b\in C\cup\{\emptyset\}. \]
They sum to \(\mu_t\) for each type, and candidate \(c\)’s normalized score is \(\sum_t x^{(N)}_{t,c}\). Define a limiting equilibrium mass profile \(x\) as the coordinatewise limit of profiles from pure Nash equilibria along some sequence \(N_j\to\infty\). My named problems are Limit-(L,\(R\))-ExistNE: does an unbounded sequence of these replications have a PNE, and return one limiting profile \(x\)? And Limit-(L,\(R\))-TieNE(\(c^\star\)): does such a sequence have PNEs in which \(c^\star\) belongs to a non-singleton winning set in every election, and return a limiting profile? Here \(R\in\{R_C,R_V\}\), as in the anchors below.

My lead anchor is Theorem 2, proved in this paper. It says that for lazy voters and either random-candidate or random-voter tie-breaking, both ExistNE and TieNE admit polynomial-time algorithms when the utilities are tie-consistent and the preference profile is single-crossing in the voter order. The paper uses an equilibrium characterization from Elkind et al. [15]; Theorem 2’s algorithmic result is proved here. Its single-crossing structure is especially apt for the limit problem: voter groups that support different members of a tied set must form consecutive blocks along the voter-mass order.

A second, independent anchor is Theorem 3, also proved here. It establishes the same polynomial-time results for lazy voters and either randomized tie-breaking rule when utilities are tie-consistent and preferences are single-peaked with respect to a common candidate order. In the limit model, this corresponds to societies whose voters’ rankings share a candidate axis; the paper’s dynamic program can be tested with weighted masses in place of voter counts.

For both limit problems, I expect Class A, tractable. The reason is more specific than “the finite problem is in P.” The paper’s Theorem 1, attributed to Elkind et al. [15], characterizes when the lazy-voter game has an equilibrium. In sufficiently large replications, its case requiring each candidate to be ranked first by at most one voter disappears: every positive-mass type is repeated many times. The remaining existence cases have direct mass certificates. Either all types share one favorite, or there is a set \(X\) of \(k\ge2\) candidates and a rational assignment \(y_{t,c}\) of each type’s mass to candidates in \(X\), satisfying
\[ \sum_{c\in X}y_{t,c}=\mu_t,\qquad \sum_t y_{t,c}=\frac1k. \]
Whenever \(y_{t,c}>0\), type \(t\) must rank \(c\) first within \(X\) and satisfy the paper’s strong-balance utility inequality
\[ \frac1k\sum_{d\in X}u_t(d)\ \ge\ \max_{d\in X\setminus\{c\}}u_t(d). \]
Such a certificate yields an equilibrium in all sufficiently divisible replications; for TieNE, require \(c^\star\in X\). The paper’s single-crossing graph and single-peaked dynamic program suggest ways to find these certificates from weighted type support, with work polynomial in \(m,\tau\), and the input bit length \(L\).

The plausible regime is a large electorate with many voters but relatively few recurring complete preference-and-utility types: for example, voters ordered by a salient ideological or socioeconomic dimension, with preferences single-crossing, or voters evaluating candidates along a shared policy axis, with preferences single-peaked. The type definition includes every feature the game uses, including utilities and tie attitude; mass means population share. The finite ballot choices and tie-breaking rule remain those of the paper.

The scope is deliberately narrow: lazy voters, randomized tie-breaking, and the paper’s tie-consistent single-crossing or single-peaked settings. This paper does not give a numbered hardness theorem of its own. Its cited NP-hardness results for unrestricted preferences come from Elkind et al. [15]; they motivate the structured cases but are not my anchors. I am not extending the claim to truth-biased voters or lexicographic tie-breaking.

The weakest point is that a limiting equilibrium of replications is a new asymptotic question; the paper computes equilibria in a specified finite election. Also, its polynomial bounds are stated for explicit voter profiles. A bit-complexity result for rational masses must show that the algorithms really process type multiplicities in compressed form. The graph and dynamic-programming proofs make that look plausible, but Theorems 2 and 3 do not establish it. That gap is a concrete part of the proposed mirror: prove compressed algorithms for the two limit problems, characterize their possible limiting winner sets, and then ask what survives when tie-consistency is relaxed.