Answer: For both \(R_C\) and \(R_V\), asymptotic equilibrium existence is in \(\mathrm P\), and one associated limit is computable in polynomial time. Bit-complexity bounds are \(O(\tau m^3L^2)\) for single-crossing and \(O((\tau+\min(m,\tau)^2)m^3L^2)\) for single-peaked.
Theorem 2 — class: algorithmic
Given a rational distribution μ over complete voter types, where each type specifies a ranking, utility function, and lazy-voter attitude, and where the support has a single-crossing voter order or a common single-peaked candidate axis, decide whether arbitrarily large integers \(N\) with \(Nμ_t\in\mathbb{Z}\) admit a pure Nash equilibrium in the replicated election under \(R\in\{R_C,R_V\}\), using \(\epsilon_N=1/(2m^2N^2)\); return one coordinatewise limit of the normalized type-by-ballot masses along such a sequence.
Let \(C\) contain \(m\geq1\) candidates. A society is given by its support: \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Each type has a binary-encoded nonnegative integer utility function \(u_t:C\to\mathbb Z_{\geq0}\) with distinct values, its induced strict ranking, and the lazy attitude. The support rankings are promised single-crossing in a supplied type order or single-peaked on a supplied candidate axis.
Every type is tie-consistent: for all \(X\subseteq C\) with \(|X|\geq3\), writing \(s_t(X)\) for its second-ranked candidate in \(X\), either \(\frac1{|X|}\sum_{c\in X}u_t(c)\geq u_t(s_t(X))\) always holds, or the reverse weak inequality always holds; different types may satisfy different alternatives.
For each positive integer \(N\) satisfying \(N\mu_t\in\mathbb Z\) for every type, create \(N\mu_t\) individual voters of type \(t\). Each chooses a ballot in \(C\cup\{\bot\}\), where \(\bot\) means abstention; use Plurality and let \(W\) be its entire set of maximum-score candidates, including \(W=C\) when everyone abstains.
The input specifies \(R\in\{R_C,R_V\}\). Rule \(R_C\) selects uniformly from \(W\); \(R_V\) selects uniformly from all \(N\) voters, including abstainers, and elects that voter's highest-ranked member of \(W\), using her intrinsic ranking.
A type-\(t\) voter's payoff is her expected intrinsic utility plus \(\epsilon_N=1/(2m^2N^2)\) if she abstains. Equilibrium means pure Nash equilibrium against any unilateral ballot change.
Call the input a yes-instance if such equilibria exist for arbitrarily large admissible \(N\). For an equilibrium \(b^{(N)}\), define \(x^{(N)}_{t,a}=N^{-1}|\{i:i\text{ has type }t,\ b_i^{(N)}=a\}|\) for \(a\in C\cup\{\bot\}\); the associated search problem asks for one coordinatewise limit along equilibria with \(N\to\infty\).
Is this asymptotic existence problem in \(\mathrm P\) or \(\mathrm{NP}\)-hard, and can one associated limit be computed in polynomial time on yes-instances? State running times in \(m,\tau,L\).
For explicitly listed finite electorates, equilibrium existence and existence of a tied equilibrium containing a specified candidate admit polynomial-time algorithms under tie-consistency and either structural promise ([Elkind et al., 2016](https://aamas.csc.liv.ac.uk/Proceedings/aamas2016/pdfs/p394.pdf)).
No result settling this exact unbounded-replication decision and limit problem was located in the literature search.
The asymptotic existence problem is in \(\mathrm P\) for both \(R_C\) and \(R_V\), under either structural promise. One associated limit can also be computed in polynomial time.
Put \(K=\min(m,\tau)\). Conservative bit-complexity bounds for both decision and search are:
The proof uses a characterization by weighted balanced candidate sets and then adapts the structured-preference graph and dynamic-programming ideas from [Elkind et al., Theorems 2–3](https://aamas.csc.liv.ac.uk/Proceedings/aamas2016/pdfs/p394.pdf). We prove the characterization and the weighted algorithms directly, including the equality cases allowed by the question’s weak inequalities.
For a nonempty set \(X\subseteq C\), let \(f_t(X)\) be type \(t\)’s favorite member of \(X\). For \(|X|\geq2\), let \(s_t(X)\) be its second-ranked member.
Call \(X\), of size \(k\geq2\), strongly mass-balanced if both of the following hold:
\[ \text{[The formulas below use the requested inline delimiters.]} \]
For every \(c\in X\),
\[ \displaystyle \sum_{t:f_t(X)=c}\mu_t=\frac1k. \tag{1} \]
For every type \(t\),
\[ \displaystyle \sum_{c\in X}u_t(c)\geq k\,u_t(s_t(X)). \tag{2} \]
Characterization. The input is a yes-instance if and only if either:
This characterization holds without single-crossing, single-peakedness, or tie-consistency.
Fix an admissible population size \(N>m\) and an equilibrium. Write \(q\) for the maximum score and \(W\) for the winning set.
A voter cannot vote for a candidate outside \(W\): withdrawing that ballot preserves \(W\), hence preserves its lottery under either rule, and gains the abstention bonus.
All abstain. If \(m=1\), the first alternative holds. Suppose \(m\geq2\).
Under \(R_C\), a voter can elect her global favorite by voting for it. Her intrinsic gain over the uniform lottery on \(C\) is at least \(1/m>\epsilon_N\), so all-abstention is not an equilibrium.
Under \(R_V\), if global favorites differ, a type-\(t\) voter’s favorite is strictly better for her than at least one candidate selected in the all-abstention lottery. That candidate has probability at least \(1/N\), so voting for her favorite gains at least \(1/N>\epsilon_N\). Thus an all-abstention equilibrium requires a common global favorite.
A unique winner. All active voters vote for that winner, say \(c\). If at least two vote, one can abstain while preserving the outcome. Hence exactly one voter votes.
That voter must rank \(c\) globally first: otherwise switching her sole ballot elects a strictly preferred candidate. Every abstainer must also rank \(c\) globally first. Indeed, if she prefers \(d\) to \(c\), voting for \(d\) creates the tie \(\{c,d\}\). Her intrinsic gain is at least \(1/2\) under \(R_C\), and at least \(1/N\) under \(R_V\), because she herself selects \(d\) when sampled. Both exceed \(\epsilon_N\).
Thus a unique-winner equilibrium requires a common global favorite.
A tied winning set. Suppose \(k=|W|\geq2\). We first prove that every active voter votes for her favorite member of \(W\).
Consider an active type-\(t\) voter voting for \(c\), and put \(d=f_t(W)\). If \(c\ne d\), switching to \(d\) makes \(d\) the unique winner. Unless her current expected intrinsic utility equals \(u_t(d)\), this is profitable.
Equality is impossible under \(R_C\). Under \(R_V\), equality implies that every sampled voter selects \(d\): utilities are distinct, and \(d\) is type \(t\)’s unique maximizer on \(W\). Withdrawing the ballot for \(c\) then leaves the outcome deterministically \(d\), and gains \(\epsilon_N\). This too contradicts equilibrium.
Consequently, each candidate in \(W\) is the favorite member of \(W\) of at least one active voter. The lottery therefore gives every member of \(W\) positive probability. Under \(R_V\), each such probability is at least \(1/N\).
There can now be no abstainer. An abstainer voting for \(f_t(W)\) makes that candidate the unique winner. Her intrinsic gain is at least \(1/k\) under \(R_C\), or at least \(1/N\) under \(R_V\), exceeding her lost abstention bonus.
Thus everyone votes for her favorite member of \(W\). Equal winning scores give \(N=kq\), and normalization yields (1). In particular, the \(R_V\) lottery is uniform on \(W\), just like \(R_C\).
A type-\(t\) voter can switch to \(s_t(W)\) and make it the unique winner. Preventing this deviation requires (2). Hence \(W\) is strongly mass-balanced.
Suppose first that every type globally prefers the same candidate \(c\).
These give equilibria for every admissible \(N\).
Now suppose \(X\) is strongly mass-balanced, with \(k=|X|\). Let \(D\) be a common denominator of the masses. For every \(N\) that is a multiple of \(kD\) and satisfies \(N/k\geq2\), let every type-\(t\) voter vote for \(f_t(X)\). Every candidate in \(X\) receives \(q=N/k\) votes; all others receive zero. Both rules give the uniform lottery on \(X\).
Consider a voter whose ballot is \(c=f_t(X)\).
Under \(R_C\), removing her favorite decreases her intrinsic expectation by
\( \displaystyle \frac{u_t(c)-\frac1{k-1}\sum_{d\in X\setminus\{c\}}u_t(d)}{k}\geq\frac1k. \)
Under \(R_V\), exactly mass \(1/k\) previously selected \(c\). Only those types change their selected candidate after its removal. Every replacement is strictly worse than \(c\) for the deviating voter, so her intrinsic loss is again at least \(1/k\).
These losses exceed \(\epsilon_N\). All unilateral deviations have therefore been checked, and the ballot profile is an equilibrium. Such populations are arbitrarily large, completing the characterization.
Call a type tie-loving if its uniform-lottery inequality holds in the forward direction for every set of size at least three.
Sets of sizes two and three will be checked directly. This is necessary because a type satisfying the reverse weak inequality may satisfy (2) at equality for a three-candidate set.
For larger sets, the following observation removes that difficulty.
Lemma. If a type satisfies the reverse inequality for every set of size at least three, it cannot satisfy (2) for any set of size at least four.
Proof. Write its utilities on such a set in descending order as \(a_1>a_2>\cdots>a_k\), where \(k\geq4\). Applying the reverse inequality to the top three gives \(a_1+a_3\leq2a_2\). Therefore,
\( \displaystyle \sum_{j=1}^k a_j \leq3a_2+\sum_{j=4}^k a_j <3a_2+(k-3)a_2 =ka_2. \)
This contradicts (2). \(\square\)
By the promise, a type that is not tie-loving satisfies the reverse inequality. Consequently:
Write its full utility sequence as \(v_1>\cdots>v_m\), and let \(S_r\) be the sum of its \(r\) smallest utilities.
A set whose second-ranked member has utility \(v_j\) contains one higher utility and \(r\) lower utilities, for some \(1\leq r\leq m-j\). Its forward inequality is hardest when the higher utility is \(v_{j-1}\) and the lower utilities are the \(r\) smallest ones. Hence the type is tie-loving exactly when
\( \displaystyle v_{j-1}+S_r\geq(r+1)v_j \)
for every \(2\leq j\leq m-1\) and \(1\leq r\leq m-j\).
Necessity follows by taking those particular sets. Sufficiency follows because every other set with the same second-ranked utility and size has a weakly larger utility sum.
This uses \(O(m^2)\) arithmetic operations per type. Checking all two- and three-candidate sets uses \(O(\tau m^3)\) operations.
Finally, every mass-balanced set has size at most \(K\): each candidate’s positive favorite mass must contain at least one type, and a type has only one favorite in the set.
Assume all types are tie-loving, and fix \(4\leq k\leq K\).
For any candidate set, the types having a particular favorite form a contiguous block in the supplied order. Otherwise, types \(i<j<\ell\) with favorites \(c,d,c\) would compare \(c\) and \(d\) in the pattern \(c\succ d\), \(d\succ c\), \(c\succ d\), contradicting single-crossing.
For a mass-balanced set, these blocks must each have mass \(1/k\). Let \(M_i=\sum_{t=1}^i\mu_t\). Every boundary must therefore occur at a prefix with mass \(j/k\), for \(1\leq j<k\).
If any required prefix is absent, reject this value of \(k\). Otherwise positivity of the masses determines unique consecutive blocks \(B_1,\ldots,B_k\). A type cannot be split across blocks because its favorite is unique.
Construct a graph with vertices \((j,c)\), one for each block and candidate. Join \((j,c)\) to \((j+1,d)\) exactly when:
We claim that a path through all layers exists exactly when a mass-balanced set of size \(k\) exists.
A balanced set immediately gives such a path by assigning its favorite candidate to each block.
Conversely, let a path assign \(c_j\) to \(B_j\). For a type in \(B_j\), single-crossing propagates every adjacent comparison to give
\( c_j\succ c_{j-1}\succ\cdots\succ c_1 \)
and
\( c_j\succ c_{j+1}\succ\cdots\succ c_k. \)
Indeed, a comparison that has switched by the first type of an earlier block persists afterward; a comparison that has not switched by the last type of a later block holds beforehand. Transitivity proves that \(c_j\) is every type in \(B_j\)’s favorite among the path candidates. It also proves that the path candidates are distinct.
Their favorite masses are exactly \(1/k\), establishing the claim. Since all types are tie-loving, the resulting set is strongly mass-balanced.
For fixed \(k\), constructing and searching the graph takes \(O(km^2+\tau)\) operations. Summing over \(k\leq K\), and including the small-set checks, gives
\( O(\tau m^3+K^2m^2)=O(\tau m^3), \)
using \(K^2\leq\tau m\). A successful path supplies the required set.
Label the supplied axis \(c_1,\ldots,c_m\).
Local-favorite property. In an increasing selected sequence, a type’s favorite is a selected candidate if and only if it prefers that candidate to its immediate selected neighbors, with only one comparison at an endpoint.
To justify this, single-peakedness implies that for \(a<b<c\), preferring \(c_a\) to \(c_b\) forces \(c_b\succ c_c\): the middle candidate cannot be worse than both endpoints. Symmetrically, preferring \(c_c\) to \(c_b\) forces \(c_b\succ c_a\). Thus preference over an immediate neighbor propagates to every selected candidate farther in that direction.
Precompute, for \(i<j\),
\( \displaystyle A(i,j)=\sum_{t:u_t(c_i)>u_t(c_j)}\mu_t, \)
and, for \(r<i<j\),
\( \displaystyle B(r,i,j)= \sum_{t:u_t(c_i)>u_t(c_r),\,u_t(c_i)>u_t(c_j)}\mu_t. \)
For a selected increasing sequence:
Fix \(4\leq k\leq K\). Define a Boolean state \(F_s(i,j)\) to mean that an increasing sequence of \(s\) selected candidates ending in \(c_i,c_j\) exists, with every selected candidate except the last already having favorite mass \(1/k\).
Initialize
\( F_2(i,j)=\mathrm{true}\quad\Longleftrightarrow\quad A(i,j)=1/k. \)
For \(r<i<j\), permit the transition
\( F_s(r,i)\longrightarrow F_{s+1}(i,j) \quad\Longleftrightarrow\quad B(r,i,j)=1/k. \)
Appending \(c_j\) leaves the immediate neighbors of earlier candidates unchanged. It finalizes precisely the previous last candidate \(c_i\), so the local-favorite property proves this recurrence in both directions.
Accept exactly when some \(F_k(i,j)\) is true and \(1-A(i,j)=1/k\). This finalizes the last candidate. Hence acceptance is equivalent to a mass-balanced set of size \(k\). Backtracking produces that set.
Precomputation takes \(O(\tau m^3)\) operations. For fixed \(k\), the dynamic program takes \(O(km^3)\); summing gives \(O(K^2m^3)\). Including the direct checks, the total is
\( O((\tau+K^2)m^3). \)
The decision algorithms also produce the required limit.
If every type has the same global favorite, use the equilibria constructed in Section 1. Their normalized ballot counts converge to
\( x_{t,\bot}=\mu_t,\qquad x_{t,c}=0\quad(c\in C). \)
Under \(R_C\) with \(m\geq2\), the single active ballot has normalized mass \(1/N\), which tends to zero.
Otherwise, obtain a strongly mass-balanced set \(X\) from direct enumeration, a graph path, or dynamic-programming backtracking. Output
\( \displaystyle x_{t,a}= \begin{cases} \mu_t,&a=f_t(X),\\ 0,&\text{otherwise}, \end{cases} \qquad x_{t,\bot}=0. \)
For the arbitrarily large populations constructed in Section 1, these are exactly the normalized ballot counts, so they form a constant sequence and are an associated coordinatewise limit.
Use a common denominator \(D\), for example the product of the input denominators, and store each mass as the integer \(D\mu_t\). Under the stated binary encoding, these integers and \(D\) have \(O(L)\) bits.
All mass tests become integer comparisons, such as checking whether \(k\) times a group weight equals \(D\). Utility tests use sums of at most \(m\) input utilities. Intermediate integers therefore have \(O(L)\) bits. Charging \(O(L^2)\) per arithmetic operation yields the stated bit bounds.
No replicated electorate is constructed. The output has \(\tau(m+1)\) rational coordinates, each either zero or an input mass, and fits within the same polynomial bounds.
Thus both asymptotic decision and associated-limit search are polynomial-time solvable under either promised structure.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task. The equilibrium characterization, both polynomial-time algorithms, and the associated-limit construction are correct as written. I found no major or minor mathematical gaps.
The claimed bit-complexity bounds are valid:
Ballots outside the winning set. The argument is correct. Removing a vote for a nonwinner preserves the maximum-score candidates. Both lotteries depend only on that set and the intrinsic rankings, so abstaining strictly improves payoff through the bonus.
All-abstention profiles. Both cases are handled correctly:
Both bounds exceed \(\epsilon_N\). The separate treatment of \(m=1\) is correct.
Unique-winner profiles. Once nonwinning ballots are excluded, two or more votes for the winner would permit a profitable abstention preserving the outcome. Therefore exactly one voter votes. The active voter’s switching deviation and each abstainer’s tie-creating deviation correctly force a common global favorite. For \(R_V\), sampling the deviating abstainer supplies the claimed probability lower bound.
Tied profiles: active voters’ ballots. Switching from a nonfavorite winner to the voter’s favorite makes the latter uniquely victorious. The equality exception under \(R_V\) is handled correctly: equality forces every sampled voter to select that favorite, so withdrawing the nonfavorite ballot preserves the deterministic outcome and gains the bonus.
Tied profiles: excluding abstainers. Every winner consequently has an active supporter who intrinsically prefers it within the winning set. Thus every winner has positive lottery probability, including probability at least \(1/N\) under \(R_V\). An abstainer can make her favorite uniquely victorious, obtaining the stated strict improvement after accounting for the lost bonus.
Balance and utility conditions. Everyone therefore votes for her favorite within the winning set. Equal scores imply equal favorite masses. This also makes the \(R_V\) lottery uniform. Switching to the second-ranked winner yields exactly the necessary utility inequality (2).
The initial restriction \(N>m\) is legitimate: arbitrarily large admissible equilibrium populations necessarily include such a population. Necessity does not require a claim about every smaller population.
Common global favorite. The constructions work for every admissible \(N\):
Strongly mass-balanced sets. Multiples of \(kD\) are admissible and provide arbitrarily large populations with \(q=N/k\geq2\). The proposed profile gives equal scores to the selected candidates and a uniform lottery under both rules.
The deviation analysis is exhaustive:
The displayed \(R_C\) loss calculation is correct. Under \(R_V\), precisely the voters whose favorite was the removed candidate change their selected candidate. Their total mass is \(1/k\), and every replacement is strictly worse for the deviator than her removed favorite. Integer utilities give the claimed loss lower bound.
These losses exceed the abstention bonus. The constructed profiles are therefore equilibria.
Reverse-inequality lemma. The computation is correct. Applying the reverse inequality to the top three utilities gives the stated bound, while every additional utility is strictly below the second-highest utility. Consequently, a reverse-consistent type cannot satisfy (2) on a set of size at least four.
Equality cases. Checking sizes two and three directly correctly preserves the possible equality cases. Larger sets are considered only when every type satisfies the forward inequality universally. The procedure does not incorrectly exclude a type merely because it also satisfies some reverse inequalities.
Testing tie-loving types. The extremal-set test is correct:
The coefficient \(r+1\) in the test is correct for a set containing one higher candidate, its second-ranked candidate, and \(r\) lower candidates.
The bounds \(O(m^2)\) per type and \(O(\tau m^3)\) for direct small-set checks are valid. The bound \(k\leq\min(m,\tau)\) follows correctly from positive favorite mass and each type having exactly one favorite.
Contiguous favorite blocks. The forbidden comparison pattern used in the proof correctly contradicts single-crossing.
Forced boundaries. Positive masses make prefix sums strictly increasing, so boundaries of mass \(j/k\) are unique when present. A type cannot be divided between different favorite blocks.
Graph equivalence. Both directions are justified:
The same chains exclude repeated path candidates. Thus the path represents a candidate set of the required size, with equal favorite masses.
The operation count \(O(km^2+\tau)\) for a fixed size and its stated aggregate bound are correct.
Local-favorite property. The supplied justification correctly uses the absence of a preference valley on the axis. Preference over an immediate selected neighbor propagates farther in that direction.
Favorite-mass formulas. The formulas using \(A\), \(B\), and \(1-A\) correctly describe the first, interior, and last selected candidates. Distinct utilities ensure that the complementary endpoint comparison has no equality case.
Dynamic-programming invariant. Initialization correctly finalizes the first candidate. Each transition finalizes the previous last candidate, and appending a candidate leaves earlier finalized favorite masses unchanged. The final endpoint test is correct.
Backtracking therefore produces a balanced set exactly when one exists. The precomputation and aggregate dynamic-programming operation counts match the claimed bounds.
The reference to [Elkind et al., Theorems 2–3](https://aamas.csc.liv.ac.uk/Proceedings/aamas2016/pdfs/p394.pdf) accurately identifies the finite-electorate structured algorithms. The present argument proves its weighted variants directly; it does not rely on an unstated extension of those theorems.
Common-favorite limit. The constructed profiles converge to full abstention in normalized coordinates. Under \(R_C\), the single active ballot contributes only \(1/N\).
Balanced-set limit. The reported coordinates equal the normalized ballot counts for every population in the constructed sequence. They therefore constitute an associated coordinatewise limit without any additional compactness or selection argument.
Arithmetic costs. The product denominator has \(O(L)\) bits, and the scaled masses, utility sums, and comparison operands retain \(O(L)\)-bit length. Charging \(O(L^2)\) per arithmetic operation is conservative and sufficient. Denominator preparation, witness recovery, and writing the explicit output fit within the stated bounds.
No electorate replication is required by the algorithms.
None. The output establishes polynomial-time decision and associated-limit search under each supplied structural promise and both specified rules.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.