Introduction
A few weeks before an election, a poll shows two front-runners, a centrist narrowly in third place, and a fourth candidate far behind. Supporters of the fourth candidate do the sensible thing: they rally behind the centrist, their second choice. Meanwhile, some of the centrist’s wavering supporters, who prefer her only slightly to one of the front-runners, conclude that she cannot win and defect. Both groups act on the same poll, at the same time. The defectors are then surprised by the next poll: the centrist, their favorite all along, is now in the lead. Everyone revises again, and the poll moves again. Do such revisions ever settle, or can polls and ballots keep chasing each other forever?
Each individual move in this story is the familiar logic behind Duverger’s law: plurality rule tends to concentrate support on two candidates, because voters desert those who cannot win [2 , 5 ] . Formal accounts of this coordination usually avoid the issue by relying on large electorates, deriving pivot probabilities from aggregate uncertainty about votes and obtaining two-candidate competition in the limit [20 , 23 ] . We instead fix a finite electorate, let all voters respond to the same poll simultaneously, and follow the resulting ballot profiles exactly.
The difficulty in a finite electorate is that most voters are not pivotal at the observed counts, so all ballots lead to the same outcome. Following Obraztsova et al. [22 ] , we resolve this indifference with trembling-hand beliefs: each voter treats the other ballots as subject to small independent deviations and chooses the ballot with the highest expected utility as the deviation probability tends to zero. These deviations are beliefs, not realized errors, and they select a deterministic response in every finite election. Applying this response to all voters simultaneously after each poll defines the dynamics we study, which Obraztsova et al. leave as an open direction.
Contributions. Our first contribution, in Section 4, identifies when one simultaneous revision ends the dynamics. If the runner-up leads every lower candidate by at least four votes, every voter switches to her preferred poll leader and no voter wants to move again: the profile becomes a sincere runoff between the leaders. This holds for any number of candidates and any full-support tremble belief; with three candidates a lead of two suffices, and parity decides the remaining cases. Failure thus requires a near-tie in the initial poll, which has probability O ( N − 1 / 2 ) O(N^{-1/2}) O ( N − 1/2 ) under random preferences.
Our second contribution, in Section 5, shows that convergence can nevertheless fail, already with three candidates, and in escalating ways. Beyond the period-two swap in an election of Obraztsova et al. [22 ] , period-three cycles with three candidates arise with six active voters, and never with fewer than four. Cycles can alternate the plurality winner, as in the story above. Finally, for every odd ℓ ≥ 3 \ell\ge3 ℓ ≥ 3 , an election with 3 ( ℓ + 4 ) 3(\ell+4) 3 ( ℓ + 4 ) voters started from truthful votes enters a cycle whose poll has period ℓ \ell ℓ and whose ballot profile has period 2 ℓ 2\ell 2 ℓ .
Related work
Duverger’s law and pivotal voting. Duverger’s law asserts that plurality rule concentrates support on two candidates [5 ] , which Cox [2 ] explains as strategic coordination. Formal derivations usually rely on large electorates, where pivot probabilities stem from aggregate uncertainty [20 , 23 ] . Fey [7 ] shows that non-Duvergerian equilibria are unstable under poll-driven belief adjustment, and Messner and Polborn [19 ] obtain exactly two vote-getters in equilibria robust to rare miscounts. Forand and Maheshri [8 ] give a dynamic account based on party entry and exit rather than voter coordination. These works study equilibria and their stability; we follow individual ballots exactly in a fixed finite electorate.
Non-pivotal voters and trembling hands. In a finite election most voters are not pivotal, so Nash equilibrium predicts little. Refinements break this indifference through truth bias [21 ] , abstention [3 ] , or local dominance [14 , 16 ] . Obraztsova et al. [22 ] adapt trembling-hand perfection [26 ] to plurality and characterize the resulting equilibria. Their Proposition 2 is the static precursor of our separation theorem; their Example 4 admits no equilibrium, and they list trembling-hand best-response dynamics as an open direction. We analyze exactly these dynamics under synchronous updates. Since our update is a deterministic map on a finite set (Lemma 3.1), their Example 4 must cycle; it does so with period two, as two voters swap ballots around an otherwise stable profile.
Iterative and poll-based voting. Under plurality, sequential best responses converge given suitable tie-breaking [17 , 18 ] , while other rules may not [13 ] ; see [15 ] for a survey. Further work asks which equilibria are reached and how good they are [1 , 10 , 11 , 24 , 27 ] . Poll-based models let voters respond to published scores [25 , 29 ] , which also shape human votes [6 ] . Closest to us, Vasselai [28 ] lets all voters respond synchronously to pivot probabilities estimated from current vote shares, proving convergence for large electorates and observing it in simulations of small ones. We derive responses from vanishing tremble beliefs instead, and exhibit cycles with only three candidates.
Cycles under simultaneous updates. Simultaneous revisions can cycle where sequential ones converge [18 ] . Kloeckner [12 ] proves that synchronous cycles are robust to small perturbations and exhibits bad cycles under approval voting. Goldberg et al. [9 ] show that detecting convergence or cycles is NP-complete for iterative plurality, and build truthful period-m m m cycles with two voters and m m m candidates under top-bottom updates. We instead fix three candidates and obtain periods growing with the electorate, with count period ℓ \ell ℓ and profile period 2 ℓ 2\ell 2 ℓ .
Model: Polls, Trembles, and Synchronous Update
Let M M M contain m ≥ 2 m \ge2 m ≥ 2 candidates and let [ N ] = { 1 , … , N } [N] = \{1,\ldots,N\} [ N ] = { 1 , … , N } index the voters. Voter i i i has fixed utilities u i : M → R u_i:M \to\mathbb{R} u i : M → R with distinct values. At round t t t , the complete ballot profile is S t = ( s i t ) i ∈ [ N ] S^t = (s_i^t)_{i\in[N]} S t = ( s i t ) i ∈ [ N ] , and a poll publishes the counts n c t = ∣ { i : s i t = c } ∣ n_c^t = |\{i:s_i^t=c\}| n c t = ∣ { i : s i t = c } ∣ . Write e c e_c e c for the unit vector of candidate c c c and W ( n ) = arg max c ∈ M n c W(n)=\arg\max_{c\in M}n_c W ( n ) = arg max c ∈ M n c for the plurality winner set. A nonempty tied set is valued by its uniform lottery u i ( W ) = 1 ∣ W ∣ ∑ c ∈ W u i ( c ) u_i(W)=\frac{1}{|W|}\sum_{c\in W}u_i(c) u i ( W ) = ∣ W ∣ 1 ∑ c ∈ W u i ( c ) . This convention is used only in the expected-utility calculation; no final winner is drawn.
Trembling-hand responses. After the poll, each voter reconsiders her ballot. She first removes her own ballot from the poll, giving the private counts q i = n t − e s i t q_i=n^t-e_{s_i^t} q i = n t − e s i t ; hence identical voters with different current ballots may respond differently. Taking the other ballots as certain would usually leave her indifferent, since a single ballot rarely changes the winner. Following Obraztsova et al. [22 ] , she instead believes that each other ballot independently stays with probability 1 − p 1-p 1 − p and otherwise switches uniformly to another candidate, so a specified directed tremble has probability p / ( m − 1 ) p/(m-1) p / ( m − 1 ) . These trembles are beliefs, not realized errors. If q ~ \widetilde{q} q denotes the resulting random private counts, the expected payoff of ballot c c c is
U i p ( c ∣ q ) = E [ u i ( W ( q ~ + e c ) ) ] . U_i^p(c\mid q)=\mathbb{E}\left[u_i\left(W(\widetilde{q}+e_c)\right)\right]. U i p ( c ∣ q ) = E [ u i ( W ( q + e c ) ) ] .
For a fixed private count q q q , every pairwise payoff difference is a polynomial in p p p , and its first nonzero coefficient determines its sign for all sufficiently small p > 0 p>0 p > 0 . To compute these coefficients, we call a realization v v v of q ~ \widetilde{q} q a terminal private vector . A flow specifies how many of the other ballots tremble from each candidate to each other candidate; for instance, k ( A → B ) k(A\to B) k ( A → B ) denotes k k k ballots trembling from A A A to B B B . Many individual tremble assignments yield the same flow, and their number is its multiplicity . In words, a voter compares ballots on the most likely flows under which her ballot matters. We write B R i ( q ) \mathrm{BR}_i(q) BR i ( q ) for the resulting best response.
Synchronous update. All voters read the same poll and revise at the same time, so the next profile is F ( S ) i = B R i ( n − e s i ) F(S)_i=\mathrm{BR}_i(n-e_{s_i}) F ( S ) i = BR i ( n − e s i ) . For a fixed p > 0 p>0 p > 0 , let F p F_p F p denote the analogous update with exact expected payoffs. The next lemma shows that, under strict utilities, both updates are well defined and coincide for small p p p , without any further assumption on utilities.
Lemma 3.1 (Unique limiting responses). Under strict utilities and uniform tremble destinations, every private vector has a unique limiting best response. For each finite election, F p = F F_p=F F p = F on all profiles for all sufficiently small positive p p p .
Proof. At p ⋆ = ( m − 1 ) / m p_\star=(m-1)/m p ⋆ = ( m − 1 ) / m , every other ballot is uniform on M M M , regardless of its current value. By symmetry, casting c c c gives c c c an expected lottery share α \alpha α (the expectation of 1 { c ∈ W } / ∣ W ∣ 1\{c\in W\}/|W| 1 { c ∈ W } /∣ W ∣ ) and every other candidate the same share β \beta β . Moreover, α > β \alpha>\beta α > β : moving the focal ballot from c ′ c' c ′ to c c c never decreases c c c 's share, and increases it strictly at terminal counts ( k , k , 0 , … , 0 ) (k,k,0,\ldots,0) ( k , k , 0 , … , 0 ) or ( k + 1 , 0 , … , 0 ) (k+1,0,\ldots,0) ( k + 1 , 0 , … , 0 ) in ( c , c ′ , … ) (c,c',\ldots) ( c , c ′ , … ) coordinates, according as ∣ q ∣ = 2 k |q|=2k ∣ q ∣ = 2 k or 2 k + 1 2k+1 2 k + 1 . Such counts have positive probability.
U i p ⋆ ( c ∣ q ) − U i p ⋆ ( c ′ ∣ q ) = ( α − β ) ( u i ( c ) − u i ( c ′ ) ) ≠ 0. U_i^{p_\star}(c\mid q)-U_i^{p_\star}(c'\mid q)=(\alpha-\beta)(u_i(c)-u_i(c'))\ne0. U i p ⋆ ( c ∣ q ) − U i p ⋆ ( c ′ ∣ q ) = ( α − β ) ( u i ( c ) − u i ( c ′ )) = 0.
No pairwise polynomial is identically zero. Its sign is constant near zero, so the finitely many ballots have a strict ordering there. Taking the minimum of the finitely many bounds over voters and profiles proves the second claim. □
Thus F F F is a deterministic map on the finite set of complete profiles, and every trajectory is eventually periodic. A lowest-order coefficient can vanish for special utilities; then the first later nonzero coefficient decides the comparison, so no generic-utility assumption is needed. The bound on p p p can depend on the entire election and on N N N ; we do not claim a uniform bound as electorates grow.
Convergence and cycles. Initialization is truthful if every voter supports her favorite candidate. A profile is Duvergerian if at most two candidates have positive support, and stable if F ( S ) = S F(S)=S F ( S ) = S . A stable profile is thus precisely a pure trembling-hand equilibrium in the sense of Obraztsova et al. [22 ] . The dynamics converge if they reach a stable profile. Otherwise, the trajectory enters a recurrent orbit after finitely many rounds, its preperiod . The period is the smallest positive return time of the complete profile on this orbit, and an active voter changes ballot somewhere on it. The period of the polls is the smallest positive L L L for which n t + L = n t n^{t+L}=n^t n t + L = n t at every recurrent phase; it divides the period of the profile.
With m = 2 m=2 m = 2 , truthful voting is trivially stable, so the dynamics converge immediately; we assume m ≥ 3 m\ge3 m ≥ 3 from now on. We use c , c ′ ∈ M c,c'\in M c , c ′ ∈ M for arbitrary candidates and A , B , C A,B,C A , B , C for named candidates.
For a single voter’s ranking with three candidates, X ≻ Y ≻ Z X \succ Y \succ Z X ≻ Y ≻ Z denotes her favorite, middle, and least-preferred candidates.
One-Step Convergence to Duverger
That such dynamics often converge, and towards Duverger, is perhaps not surprising. A voter compares ballots on the most likely configurations in which her ballot matters. If her favorite trails far behind, many trembles are needed before a ballot for that candidate could make a difference, whereas a few trembles already make the race between the two leaders close. Her decisive comparison should therefore involve only the leaders, and she should vote for the one she prefers. Two things could still go wrong though. First, the revised profile could trigger further revisions, as in the introductory story, where a narrowly trailing candidate gains and loses supporters at once; a large enough gap rules this out. Second, the leaders themselves could lose support; truthful initialization prevents this, since their supporters already vote for them and keep doing so. We formalize this argument in the remainder of the section.
Arbitrary Number of Candidates
We first consider an election with any number of candidates and a general tremble belief, and derive a simple sufficient condition for one-step convergence. In this subsection only, voters may believe that trembles are biased towards some candidates. A ballot for c c c trembles to c ′ ≠ c c' \ne c c ′ = c with probability p λ c c ′ p\lambda_{cc'} p λ c c ′ , where the shares λ c c ′ > 0 \lambda_{cc'} > 0 λ c c ′ > 0 sum to one over c ′ ≠ c c' \ne c c ′ = c and do not depend on p p p . Trembles remain independent, and uniform trembles are the case λ c c ′ = 1 / ( m − 1 ) \lambda_{cc'} = 1/(m-1) λ c c ′ = 1/ ( m − 1 ) ; expected payoffs are defined as before. The following lemma then shows that a voter facing two leaders well separated from all other candidates has a unique best response—her preferred leader—independent of her tremble belief.
Lemma 4.1 (Choice between separated leaders). If A , B A,B A , B have the two highest private counts and min { q A , q B } ≥ q c + 3 \min\{q_A,q_B\} \ge q_c + 3 min { q A , q B } ≥ q c + 3 , for every c ∉ { A , B } c \notin\{A,B\} c ∈ / { A , B } , then the unique limiting response is the one of A , B A,B A , B the voter prefers, for every choice of positive shares λ \lambda λ .
Proof. Relabel so that q A ≥ q B q_A \ge q_B q A ≥ q B and put d = q A − q B d = q_A - q_B d = q A − q B , r = ⌈ d / 2 ⌉ r = \lceil d/2\rceil r = ⌈ d /2 ⌉ . In any configuration where at most r r r other ballots tremble, the resulting private vector v v v satisfies
v A − v c ≥ d + 3 − 2 r ≥ 2 ( c ∉ { A , B } ) . v_A - v_c \ge d + 3 - 2r \ge2 \qquad(c \notin\{A,B\}). v A − v c ≥ d + 3 − 2 r ≥ 2 ( c ∈ / { A , B }) .
Even after adding any contemplated ballot, no lower candidate can win or tie for the lead. On every such terminal assignment, voting for the preferred member of { A , B } \{A,B\} { A , B } is therefore weakly better than any other ballot: it can only shift the winner lottery toward that candidate.
There is a strict comparison at or before order r r r . If the voter prefers A A A , use r r r trembles A → B A \to B A → B , leaving gap 0 0 0 when d d d is even and − 1 -1 − 1 when d d d is odd. Ballot A A A then strictly beats every alternative. If she prefers B B B , use ⌊ d / 2 ⌋ \lfloor d/2\rfloor ⌊ d /2 ⌋ trembles A → B A \to B A → B , leaving gap 0 0 0 or 1 1 1 , and ballot B B B strictly beats every alternative. These flows are feasible because q A ≥ d + 3 q_A \ge d + 3 q A ≥ d + 3 . Every assignment with η \eta η trembles has probability p η ( 1 − p ) N − 1 − η p^\eta(1-p)^{N-1-\eta} p η ( 1 − p ) N − 1 − η times a positive constant depending on the assignment. Take the earliest order with a strict contribution to the required margin. It has η ≤ r \eta\le r η ≤ r , all contributions at that order are nonnegative, and all earlier ones vanish. Their positive sum is therefore the first nonzero coefficient. □
The lemma concerns a single voter’s private counts, while all voters respond to the same public poll. Since removing one’s own ballot lowers a gap by at most one, a public gap of four gives every voter a private gap of three. Combined with truthful initialization, this yields convergence in a single update.
Theorem 4.2 (One-step convergence). Let S 0 S^0 S 0 be truthful and let A , B A,B A , B be the two leaders of the initial poll. If min { n A 0 , n B 0 } ≥ n c 0 + 4 \min\{n_A^0,n_B^0\} \ge n_c^0 + 4 min { n A 0 , n B 0 } ≥ n c 0 + 4 , for every c ∉ { A , B } c \notin\{A,B\} c ∈ / { A , B } , then one update makes every voter support her preferred member of { A , B } \{A,B\} { A , B } , and the resulting profile is stable. This holds for every choice of positive shares λ \lambda λ .
Proof. Removing any ballot leaves both leaders at least three above every lower candidate, so Lemma 4.1 determines every first response. Truthful A A A - and B B B -supporters keep their ballots. Both candidates therefore retain at least their initial support, which is at least four, while every other candidate has zero support. At the successor, removing any ballot again leaves both supported candidates at least three above all others, and the lemma makes every voter stay. □
After a single revision, the profile thus coincides with sincere voting in a runoff between the two poll leaders, although no candidate is formally eliminated. Note that the shares λ \lambda λ must not vanish with p p p : otherwise, trembles towards some candidates become less likely than others, which changes which configurations are decisive.
Sharper Conditions for Three Candidates
The previous result gives a sufficient condition in a very general setting. We next show that this condition can be relaxed considerably assuming three candidates and uniform trembles. We first state a simple but useful lemma.
Lemma 4.3 (Least-preferred ballot). No voter’s limiting best response is her least-preferred candidate. With three candidates, each voter thus chooses between her favorite and middle candidates.
Proof. Let X X X and Z Z Z be the voter’s favorite and least-preferred candidates. Fix a terminal private vector v v v , and compare W X = W ( v + e X ) W_X = W(v+e_X) W X = W ( v + e X ) with W Z = W ( v + e Z ) W_Z = W(v+e_Z) W Z = W ( v + e Z ) , where the two ballots change only the counts of X X X and Z Z Z , either W X = { X } W_X = \{X\} W X = { X } , or W Z = { Z } W_Z = \{Z\} W Z = { Z } , or W X ∖ { X } = W Z ∖ { Z } W_X \setminus\{X\} = W_Z \setminus\{Z\} W X ∖ { X } = W Z ∖ { Z } . In the first two cases, u i ( W X ) ≥ u i ( W Z ) u_i(W_X) \ge u_i(W_Z) u i ( W X ) ≥ u i ( W Z ) is immediate. In the third, W X W_X W X is obtained from W Z W_Z W Z by possibly removing Z Z Z and possibly adding X X X ; neither operation lowers the value of the uniform lottery. Hence ballot X X X is weakly better at every terminal vector. It is strictly better at v = ( k , k , 0 , … , 0 ) v = (k,k,0,\ldots,0) v = ( k , k , 0 , … , 0 ) or v = ( k , k + 1 , 0 , … , 0 ) v = (k,k+1,0,\ldots,0) v = ( k , k + 1 , 0 , … , 0 ) in ( X , Z , … ) (X,Z,\ldots) ( X , Z , … ) coordinates, according as ∣ q ∣ = 2 k |q| = 2k ∣ q ∣ = 2 k or 2 k + 1 2k+1 2 k + 1 . These vectors have positive probability, so the expected comparison is strict for every p > 0 p > 0 p > 0 . □
This is the trembling-hand counterpart of the classical fact that voting for one’s worst alternative is weakly dominated under plurality [4 ] . With three candidates, the gap that matters is the one between the runner-up and the trailing candidate. The next theorem shows that a gap of two always suffices, and a gap of one suffices when the leaders’ gap is even. Parity matters because a tremble from one leader to the other changes their gap by two, so whether they can be brought exactly level depends on its parity.
Theorem 4.4 (Three-candidate refinement). Let S 0 S^0 S 0 be truthful, with n A 0 ≥ n B 0 > n C 0 ≥ 1 n_A^0 \ge n_B^0 > n_C^0 \ge1 n A 0 ≥ n B 0 > n C 0 ≥ 1 . If n B 0 − n C 0 ≥ 2 n_B^0-n_C^0 \ge2 n B 0 − n C 0 ≥ 2 or n A 0 − n B 0 n_A^0-n_B^0 n A 0 − n B 0 is even, then initial A A A - and B B B -voters stay, initial C C C -voters choose their preferred member of { A , B } \{A,B\} { A , B } , and S 1 S^1 S 1 is stable.
Proof. Write the poll as ( r + d , r , r − s ) (r+d,r,r-s) ( r + d , r , r − s ) , where r ≥ 2 r \ge2 r ≥ 2 , d ≥ 0 d \ge0 d ≥ 0 , and 1 ≤ s ≤ r − 1 1 \le s \le r-1 1 ≤ s ≤ r − 1 . The three truthful voter blocks see
q A = ( r + d − 1 , r , r − s ) , q B = ( r + d , r − 1 , r − s ) , q^A=(r+d-1,r,r-s),\qquad q^B=(r+d,r-1,r-s), q A = ( r + d − 1 , r , r − s ) , q B = ( r + d , r − 1 , r − s ) ,
and
q C = ( r + d , r , r − s − 1 ) . q^C=(r+d,r,r-s-1). q C = ( r + d , r , r − s − 1 ) .
By Lemma 4.3, each voter has two candidate ballots. A tremble A ↦ B A \mapsto B A ↦ B reduces the A A A –B B B gap by two, and A ↦ C A \mapsto C A ↦ C or C ↦ B C \mapsto B C ↦ B by one, so parity determines which flows can first make a ballot decisive. At d = 0 d=0 d = 0 the claimed responses follow from the tied-top winner sets; for d > 0 d>0 d > 0 , Table 1 gives the order of each required positive margin, and all earlier coefficients vanish.
Table 1. Orders of the first positive margins in the proof of Theorem 4.4, as powers of p p p . Only favorite–middle comparisons are needed, by Lemma 4.3.
The even-gap boundary s = 1 s=1 s = 1 , with d = 2 k > 0 d=2k>0 d = 2 k > 0 , shows why the guarantee depends on parity. A truthful B ≻ C ≻ A B \succ C \succ A B ≻ C ≻ A voter sees
q B = ( r + 2 k , r − 1 , r − 1 ) . q^B=(r+2k,r-1,r-1). q B = ( r + 2 k , r − 1 , r − 1 ) .
At order k k k , the only contributing flows are k ( A ↦ B ) k(A \mapsto B) k ( A ↦ B ) and k ( A ↦ C ) k(A \mapsto C) k ( A ↦ C ) , with equal multiplicity and payoff differences ( u i ( B ) − u i ( A ) ) / 2 (u_i(B)-u_i(A))/2 ( u i ( B ) − u i ( A )) /2 and ( u i ( A ) − u i ( C ) ) / 2 (u_i(A)-u_i(C))/2 ( u i ( A ) − u i ( C )) /2 . Their sum gives
2 − k − 1 ( r + 2 k k ) ( u i ( B ) − u i ( C ) ) > 0 2^{-k-1}\binom{r+2k}{k}\bigl(u_i(B)-u_i(C)\bigr)>0 2 − k − 1 ( k r + 2 k ) ( u i ( B ) − u i ( C ) ) > 0
as the first nonzero coefficient. Thus even when the trailing candidate enters the first decisive order, its contribution preserves the required response. For an odd gap, s = 2 s=2 s = 2 is the corresponding boundary: the trailing candidate can again enter the first decisive order, so its contribution must be summed. For a truthful B ≻ C ≻ A B \succ C \succ A B ≻ C ≻ A voter, put a = r + 2 k + 1 a=r+2k+1 a = r + 2 k + 1 . The coefficient of p k + 1 p^{k+1} p k + 1 in U i P ( B ∣ q B ) − U i P ( C ∣ q B ) U_i^P(B\mid q^B)-U_i^P(C\mid q^B) U i P ( B ∣ q B ) − U i P ( C ∣ q B ) is
2 − k − 2 [ ( a k + 1 ) ( u i ( B ) − u i ( C ) ) + ( 2 r + k − 1 ) ( a k ) ( u i ( B ) − u i ( A ) ) ] , 2^{-k-2}\left[\binom{a}{k+1}\bigl(u_i(B)-u_i(C)\bigr)+(2r+k-1)\binom{a}{k}\bigl(u_i(B)-u_i(A)\bigr)\right], 2 − k − 2 [ ( k + 1 a ) ( u i ( B ) − u i ( C ) ) + ( 2 r + k − 1 ) ( k a ) ( u i ( B ) − u i ( A ) ) ] ,
which is positive since u i ( B ) u_i(B) u i ( B ) exceeds both u i ( C ) u_i(C) u i ( C ) and u i ( A ) u_i(A) u i ( A ) . The remaining rows follow by the same gap reduction and flow counts; Appendix B.1 gives the flow lists and the remaining coefficient and sign calculations.
It remains to show that S 1 S^1 S 1 is stable. If x x x of the initial C C C -voters move to A A A , the successor counts are ( r + d + x , 2 r − s − x , 0 ) (r+d+x,2r-s-x,0) ( r + d + x , 2 r − s − x , 0 ) , and every voter prefers the candidate she supports to the other supported candidate. For r ≥ 3 r \ge3 r ≥ 3 , both supported counts are at least three. If both private counts are at least three, Lemma 4.1 makes the voter stay. The only remaining case, up to exchanging A , B A,B A , B , is an A A A -supporter with q A = 2 q_A=2 q A = 2 and q B ≥ 3 q_B \ge3 q B ≥ 3 . With at most ⌊ ( q B − 2 ) / 2 ⌋ \lfloor(q_B-2)/2\rfloor ⌊( q B − 2 ) /2 ⌋ trembles, B B B remains at least two above C C C , so the unsupported candidate cannot win after any contemplated ballot. Ballot A A A is weakly best in every such configuration, and moving exactly that many ballots B ↦ A B \mapsto A B ↦ A makes it strictly best. The one-step-order argument of Lemma 4.1 therefore makes this voter stay as well.
If r = 2 r=2 r = 2 , then s = 1 s=1 s = 1 , and the hypothesis forces d = 2 k d=2k d = 2 k to be even. The successors are ( 2 k + 2 , 3 , 0 ) (2k+2,3,0) ( 2 k + 2 , 3 , 0 ) and ( 2 k + 3 , 2 , 0 ) (2k+3,2,0) ( 2 k + 3 , 2 , 0 ) . The first is covered above for k ≥ 1 k \ge1 k ≥ 1 . At ( 2 , 3 , 0 ) (2,3,0) ( 2 , 3 , 0 ) , both A A A -supporters are truthful A A A -voters; their first A A A -minus-C C C coefficient is 3 [ 2 u i ( A ) − u i ( B ) − u i ( C ) ] / 4 > 0 3[2u_i(A)-u_i(B)-u_i(C)]/4>0 3 [ 2 u i ( A ) − u i ( B ) − u i ( C )] /4 > 0 , and their A A A -minus-B B B coefficient is positive. At ( 2 k + 3 , 2 , 0 ) (2k+3,2,0) ( 2 k + 3 , 2 , 0 ) , every B B B -supporter is a truthful B B B -voter. Her first B B B -minus-C C C coefficient is a positive multiple of ( k + 1 ) ( u i ( B ) − u i ( A ) ) + u i ( B ) − u i ( C ) > 0 (k+1)(u_i(B)-u_i(A))+u_i(B)-u_i(C)>0 ( k + 1 ) ( u i ( B ) − u i ( A )) + u i ( B ) − u i ( C ) > 0 , while her B B B -minus-A A A comparison has the sign of her preference. An A A A -supporter has an even private A A A –B B B gap 2 k 2k 2 k ; its first decisive order contains only supported winners and favors A A A . Hence both boundary successors are stable. The full coefficients are given in Appendix B.2. □ \square □
The theorem leaves open tied lower counts and a one-vote gap below the runner-up when the leaders’ gap is odd. The latter can genuinely fail to converge in one step, much as in the story of the introduction. Take four voters with utilities ( 1 , 1 / 2 , 0 ) (1,1/2,0) ( 1 , 1/2 , 0 ) , three with ( 19 / 20 , 1 , 0 ) (19/20,1,0) ( 19/20 , 1 , 0 ) , and two with ( 0 , 19 / 20 , 1 ) (0,19/20,1) ( 0 , 19/20 , 1 ) , in ( A , B , C ) (A,B,C) ( A , B , C ) order. Starting from truthful votes, the dynamics give
( 4 , 3 , 2 ) ↦ ( 7 , 2 , 0 ) ↦ ( 4 , 5 , 0 ) . (4,3,2)\mapsto(7,2,0)\mapsto(4,5,0). ( 4 , 3 , 2 ) ↦ ( 7 , 2 , 0 ) ↦ ( 4 , 5 , 0 ) .
In the first update, the C C C -voters rally behind B B B , while the B B B -voters, who prefer B B B only slightly to A A A and see C C C close behind, defect to A A A : at their private counts ( 4 , 2 , 2 ) (4,2,2) ( 4 , 2 , 2 ) , their margin for B B B over A A A is − 19 p / 40 + O ( p 2 ) -19p/40+O(p^2) − 19 p /40 + O ( p 2 ) . B B B is now carried entirely by former C C C -voters. With C C C gone, the defectors face ( 6 , 2 , 0 ) (6,2,0) ( 6 , 2 , 0 ) , where their margin becomes 3 p 2 / 8 + O ( p 3 ) > 0 3p^2/8+O(p^3)>0 3 p 2 /8 + O ( p 3 ) > 0 , and they return. The final profile is stable, and B B B wins although her own supporters had abandoned her. Here the dynamics still converge after two updates; Section 5 shows that they need not converge at all.
Duverger’s Law in Typical Elections
We now argue that these results offer an intuitive explanation for why Duverger’s law is commonly observed in practice. Fix m ≥ 3 m \ge3 m ≥ 3 candidates and a probability distribution over utility vectors, with almost surely strict rankings, and view each observed electorate of N N N voters as N N N independent draws from it. Let α c \alpha_c α c be the probability that candidate c c c is a voter’s favorite, and assume α c > 0 \alpha_c>0 α c > 0 for every c c c . The truthful poll is then multinomial with parameters N N N and ( α c ) c ∈ M (\alpha_c)_{c\in M} ( α c ) c ∈ M . The condition of Theorem 4.2 fails only if the runner-up is within three votes of the third-placed candidate, and such near-ties become rare as the electorate grows.
Corollary 4.5 (Random elections). In this random model, truthful initialization reaches a stable Duvergerian profile after one update with probability at least 1 − O ( N − 1 / 2 ) 1-O(N^{-1/2}) 1 − O ( N − 1/2 ) . If two candidates have favorite probabilities strictly greater than those of every other candidate, the probability is at least 1 − e − Ω ( N ) 1-e^{-\Omega(N)} 1 − e − Ω ( N ) .
Proof. If α c = α c ′ \alpha_c=\alpha_{c'} α c = α c ′ , condition on K = n c 0 + n c ′ 0 K=n_c^0+n_{c'}^0 K = n c 0 + n c ′ 0 . Then n c 0 n_c^0 n c 0 is binomial with parameters K , 1 / 2 K,1/2 K , 1/2 , and ∣ n c 0 − n c ′ 0 ∣ ≤ 3 |n_c^0-n_{c'}^0|\le3 ∣ n c 0 − n c ′ 0 ∣ ≤ 3 permits at most four values. Outside the exponentially unlikely event K < N α c K<N\alpha_c K < N α c , the largest conditional point probability is O ( ( N α c ) − 1 / 2 ) O((N\alpha_c)^{-1/2}) O (( N α c ) − 1/2 ) . Thus the near-tie probability is O ( N − 1 / 2 ) O(N^{-1/2}) O ( N − 1/2 ) , including the possibility K = 0 K=0 K = 0 . If α c ≠ α c ′ \alpha_c \ne\alpha_{c'} α c = α c ′ , concentration about the nonzero mean gap gives an exponentially small probability. A union bound over the fixed number of pairs shows that all counts differ by at least four with probability at least 1 − O ( N − 1 / 2 ) 1-O(N^{-1/2}) 1 − O ( N − 1/2 ) , and Theorem 4.2 applies on this event. For the stronger bound, let A , B A,B A , B be the two candidates whose favorite probabilities exceed all others. Each difference n A c − n c 0 n_A^c-n_c^0 n A c − n c 0 or n B c − n c 0 n_B^c-n_c^0 n B c − n c 0 , with c ∉ { A , B } c\notin\{A,B\} c ∈ / { A , B } , has a positive mean proportional to N N N . Hoeffding’s inequality bounds the probability that any one is below four by e − Ω ( N ) e^{-\Omega(N)} e − Ω ( N ) , and a union bound over these pairs proves the claim; no separation between A A A and B B B is needed. □
The bound holds for every such distribution; only the constant depends on m m m and on the distribution, and it grows as the favorite probabilities of the trailing candidates shrink. Near-ties are exponentially unlikely unless the second-highest favorite probability is shared by several candidates, as when the distribution is symmetric across candidates. Even then, they are rare, so elections rarely fail to settle on two candidates after a single round of revisions. Near-ties matter mainly when candidates are equally popular, for instance under a distribution symmetric across candidates, with α c = 1 / m \alpha_c=1/m α c = 1/ m for all c c c . Even then, they are rare, so elections rarely fail to settle on two candidates after a single round of revisions.
When the Dynamics Do Not Converge
The results above show that convergence is the typical outcome, but it is not guaranteed. The following example, inspired by an election of Obraztsova et al. [22 ] that admits no trembling-hand equilibrium, provides a simple counter-example.
Example 5.1 (A period-two cycle). Consider three candidates and four voters: voters 1 and 2 rank A ≻ B ≻ C A \succ B \succ C A ≻ B ≻ C , voter 3 ranks B ≻ C ≻ A B \succ C \succ A B ≻ C ≻ A , and voter 4 ranks C ≻ B ≻ A C \succ B \succ A C ≻ B ≻ A , with any strict utilities consistent with these rankings. Starting from truthful votes, the ballot profile alternates between
( A , A , B , C ) ⟷ ( A , A , C , B ) , (A,A,B,C) \longleftrightarrow(A,A,C,B), ( A , A , B , C ) ⟷ ( A , A , C , B ) ,
where the i i i -th entry is voter i i i ’s ballot. Voters 3 and 4 each try to create a tie between A A A and their favorite by switching to the other’s candidate, and their simultaneous switches cancel out.
This cycle is hardly a failure of coordination. The poll reads ( 2 , 1 , 1 ) (2,1,1) ( 2 , 1 , 1 ) in both phases; only two voters exchange their ballots. Judged by the poll alone, these dynamics have converged. Can the dynamics exhibit genuinely richer behavior, with longer cycles in which the poll itself keeps changing?
Three-Cycles: How Many Active Voters?
We now look for richer cycles, in which the poll itself changes from round to round, and start with simple ones: three candidates and period three. We first show that such cycles require enough active voters, that is, voters who change their ballot somewhere on the cycle; all other voters keep the same ballot throughout, and their counts act as a fixed background.
Theorem 5.2 (Active-voter lower bound). With three candidates, every period-three cycle of the complete ballot profile has at least four active voters.
Proof. If the other voters cast the same ballots at two phases, the focal voter has the same private counts and must repeat her response. By Lemma 4.3, each active voter alternates between her favorite and her middle candidate. Up to a time shift, her ballots along the cycle are therefore ( X , Y , X ) (X,Y,X) ( X , Y , X ) or ( Y , X , Y ) (Y,X,Y) ( Y , X , Y ) , with exactly one stay among the three transitions.
A single active voter always faces the same private vector and cannot cycle. With two, suppose voter 1 stays in the first transition. Voter 2 then faces the same other ballots at the first two phases, so she stays in the next transition. This forces voter 1 to stay again, a contradiction. With three active voters, the same argument, and the fact that not all voters can stay in the same transition, leave only two patterns of stays, ( 1 , 1 , 1 ) (1,1,1) ( 1 , 1 , 1 ) and ( 2 , 1 , 0 ) (2,1,0) ( 2 , 1 , 0 ) , up to a time shift.
For these patterns, let z = ( z A , z B , z C ) z=(z_A,z_B,z_C) z = ( z A , z B , z C ) count the ballots of the inactive voters. Two restrictions on responses rule them out. First, a voter with X ≻ Y ≻ Z X\succ Y\succ Z X ≻ Y ≻ Z can choose Y Y Y only if q Y > q X q_Y>q_X q Y > q X . Second, for c ∈ { Y , Z } c\in\{Y,Z\} c ∈ { Y , Z } with q c > 0 q_c>0 q c > 0 , no voter responds X X X at q q q and Y Y Y at q + e X − e c q+e_X-e_c q + e X − e c : moving one other ballot towards a voter’s favorite cannot make her abandon it. For the pattern ( 1 , 1 , 1 ) (1,1,1) ( 1 , 1 , 1 ) , these restrictions leave two classes of cycles, each requiring an impossible strict cycle chain among z A , z B , z C z_A,z_B,z_C z A , z B , z C . For ( 2 , 1 , 0 ) (2,1,0) ( 2 , 1 , 0 ) , six classes remain, each violating one of the restrictions. Appendix C proves both restrictions and covers every branch of the case analysis. □
The bound holds for any number and composition of inactive voters, and it does not require truthful initialization. As we show next, six active voters suffice: we exhibit a period-three cycle, reached from truthful votes, in which the poll changes in every round.
Theorem 5.3 (Six active voters suffice). There is a three-candidate election with six voters, all of them active, whose dynamics from truthful votes cycle with period three.
Proof. Choose 9 / 11 < ρ < 1 9/11<\rho<1 9/11 < ρ < 1 and 1 / 2 < γ < 1 1/2<\gamma<1 1/2 < γ < 1 . Take two voters with ranking A ≻ C ≻ B A\succ C\succ B A ≻ C ≻ B , two with B ≻ C ≻ A B\succ C\succ A B ≻ C ≻ A , and one with C ≻ B ≻ A C\succ B\succ A C ≻ B ≻ A . Their utilities in ranking order are ( 1 , ρ , 0 ) (1,\rho,0) ( 1 , ρ , 0 ) for the first four and ( 1 , γ , 0 ) (1,\gamma,0) ( 1 , γ , 0 ) for the last two. Their ballots over three rounds are ( A , C , C ) (A,C,C) ( A , C , C ) , ( B , C , C ) (B,C,C) ( B , C , C ) , ( C , A , C ) (C,A,C) ( C , A , C ) and ( C , B , C ) (C,B,C) ( C , B , C ) , respectively, so the counts are
( 2 , 2 , 2 ) ⟼ ( 1 , 1 , 4 ) ⟼ ( 0 , 0 , 6 ) ⟼ ( 2 , 2 , 2 ) . (2,2,2) \longmapsto(1,1,4) \longmapsto(0,0,6) \longmapsto(2,2,2). ( 2 , 2 , 2 ) ⟼ ( 1 , 1 , 4 ) ⟼ ( 0 , 0 , 6 ) ⟼ ( 2 , 2 , 2 ) .
Appendix D checks, for each round and each voter, that the next ballot on her path is her strict best response: the first nonzero coefficient of the payoff difference with her other option is positive throughout these intervals. Every voter returns to her ballot after three updates, and the three count vectors are distinct, thus the period is exactly three. □
The cycle has a simple reading. From the three-way tie, the supporters of A A A and B B B move to their common middle candidate C C C , while the C C C -voters simultaneously move to their own middle candidates; C C C thus leads, but without its own supporters. These return in the next round, so that everyone votes for C C C . The supporters of A A A and B B B then return to their favorites, and the tie reappears. The minimum number of active voters for period three thus lies between four and six. An extensive computer search found no period-three cycle with four or five active voters and at most ten inactive voters per candidate.
Table 1 (PDF p. 6). A period-four cycle with alternating leaders. Rows are voters, columns are rounds, and round 4 repeats round 0. Outlined ballots change between rounds 2 and 3 although the poll does not: responses depend on each voter’s own ballot.
Cycles with Changing Leaders
In the period-three cycle above, the poll changes in every round, but the outcome hardly does: C C C leads alone in two rounds, and the third is a three-way tie. A more convincing failure of coordination is a cycle in which different candidates take turns as the unique leader. The following example showcases this property.
Example 5.4 (Alternating leaders). Figure 1 lists the utilities and ballots of six voters. Starting from truthful votes, the dynamics cycle with period four, and both B B B and A A A recur as unique plurality leaders. Voter 3 always votes for B B B ; the other five voters are active.
From the three-way tie, the voters whose second choice is B B B rally behind it, while the B B B -voter who nearly likes A A A as much moves to A A A . Facing a strong B B B , the A A A -voters return and are joined by the C ≻ A ≻ B C \succ A \succ B C ≻ A ≻ B voter, so A A A takes the lead. The poll then stays at ( 3 , 2 , 1 ) (3,2,1) ( 3 , 2 , 1 ) for two rounds while three voters exchange ballots, before the tie reappears. We prove in Appendix § 13 that every response is a strict best response; as the four profiles are distinct, the period is four.
Moreover, the two rounds with the same poll show that a voter’s response depends on her own current ballot. Consider voter 4, with ranking B ≻ A ≻ C B \succ A \succ C B ≻ A ≻ C . At round 2, she votes for B B B and sees private counts ( 3 , 1 , 1 ) (3,1,1) ( 3 , 1 , 1 ) : both ballots leave A A A ahead, so only trembles matter. The one-tremble flows A ↦ B A \mapsto B A ↦ B , A ↦ C A \mapsto C A ↦ C and C ↦ B C \mapsto B C ↦ B , with multiplicities 3, 3 and 1, change her payoff from voting A A A rather than B B B by − 1 / 6 -1/6 − 1/6 , 2 / 9 2/9 2/9 and − 1 / 12 -1/12 − 1/12 , respectively, giving
U 4 p ( A ∣ ( 3 , 1 , 1 ) ) − U 4 p ( B ∣ ( 3 , 1 , 1 ) ) = p 24 + O ( p 2 ) > 0 , U_4^p(A\mid(3,1,1))-U_4^p(B\mid(3,1,1))=\frac{p}{24}+O(p^2)>0, U 4 p ( A ∣ ( 3 , 1 , 1 )) − U 4 p ( B ∣ ( 3 , 1 , 1 )) = 24 p + O ( p 2 ) > 0 ,
so she switches to A A A . At round 3, the poll is unchanged, but since she now votes for A A A , her private counts are ( 2 , 2 , 1 ) (2,2,1) ( 2 , 2 , 1 ) . Voting B B B now makes her favorite win outright, so her margin for B B B over A A A is 1 / 6 + O ( p ) > 0 1/6+O(p)>0 1/6 + O ( p ) > 0 , and she switches back.
Arbitrarily Long Cycles
All cycles so far are short and involve at most six active voters. We now show that the dynamics can be much richer: with only three candidates, larger electorates sustain cycles of arbitrarily long period, in which the poll keeps changing round after round.
Theorem 5.5 (Cycle lengths growing with the electorate). For every odd integer ℓ ≥ 3 \ell\ge3 ℓ ≥ 3 , there is a nonempty open set of strict utility profiles with three candidates and N = 3 ( ℓ + 4 ) N=3(\ell+4) N = 3 ( ℓ + 4 ) voters, for which the dynamics from truthful votes enter a recurrent orbit after three updates. On this orbit, the poll has period ℓ \ell ℓ , whereas the complete ballot profile has period 2 ℓ 2\ell 2 ℓ . Every candidate keeps positive support throughout, and C C C is the unique plurality leader.
Figure 2 shows the construction for ℓ = 5 \ell=5 ℓ = 5 , with 27 voters. After three transient updates, the poll cycles through five distinct values. When it returns, however, two pairs of voters have exchanged their roles, so the complete profile returns only after ten updates.
Figure 2. The long cycle for ℓ = 5 \ell=5 ℓ = 5 (27 voters), with poll ( x , x , 27 − 2 x ) (x,x,27-2x) ( x , x , 27 − 2 x ) for x x x split pairs. Open dots mark the transient updates. The poll has period five, the profile ten: the shaded halves differ in which pairs are split.
The construction rests on pairs of opposing partisans who share a compromise candidate. Each pair consists of one voter with ranking A ≻ C ≻ B A \succ C \succ B A ≻ C ≻ B and one with B ≻ C ≻ A B \succ C \succ A B ≻ C ≻ A ; a pair is split when its voters support their favorites A A A and B B B , and pooled when both vote for C C C . Loyal C C C -supporters complete the electorate. Since every pair is either split or pooled, the poll is determined by the number x x x of split pairs, and A A A and B B B are always tied. Whether a voter keeps her favorite or retreats to C C C then depends on the parity of x x x and on how strongly she values the compromise. Odd values of x x x flip every pair at once, while even values let only the pairs that value the compromise least move towards their favorites. Choosing these utilities carefully lets us steer the number of split pairs through a long sequence of distinct values before it repeats.
Formally, fix an odd integer h = 2 s + 1 ≥ 7 h=2s+1\ge7 h = 2 s + 1 ≥ 7 . For each identity i i i in a set P P P of h h h pairs, create one voter with ranking A ≻ C ≻ B A\succ C\succ B A ≻ C ≻ B and one with ranking B ≻ C ≻ A B\succ C\succ A B ≻ C ≻ A . After normalizing top and bottom utilities to 1 and 0, write their utilities for C C C as ρ i A \rho_i^A ρ i A and ρ i B \rho_i^B ρ i B . Add h h h voters with ranking C ≻ A ≻ B C\succ A\succ B C ≻ A ≻ B and utility y i y_i y i for A A A . A profile in which every pair is split or pooled is identified by its set I ⊆ P I\subseteq P I ⊆ P of split pairs. Writing x = ∣ I ∣ x=|I| x = ∣ I ∣ , its poll is
( x , x , 3 h − 2 x ) . (1) (x,x,3h-2x). \tag*{(1)} ( x , x , 3 h − 2 x ) . (1)
Let Φ ( I ) \Phi(I) Φ ( I ) denote the set of split pairs after one update. A pair’s response depends on how much its voters value the compromise C C C : the more they value it, the more readily they pool. The lemma makes this precise through a single increasing chain of utility thresholds, and classifies pairs by where their utility for C C C falls in this chain.
Lemma 5.6 (Paired response). There exist thresholds 1 2 = κ 0 < κ 1 < ⋯ < κ h < κ h + 1 = 1 \frac{1}{2}=\kappa_0<\kappa_1<\cdots<\kappa_h<\kappa_{h+1}=1 2 1 = κ 0 < κ 1 < ⋯ < κ h < κ h + 1 = 1 with the following property. Whenever x = 2 k x=2k x = 2 k pairs are split, a voter in a split pair keeps her favorite if her utility for C C C is strictly below κ k \kappa_k κ k , and moves to C C C if it is strictly above; a voter in a pooled pair returns to her favorite if her utility for C C C is strictly below κ h − k \kappa_{h-k} κ h − k , and stays at C C C if it is strictly above.
Consequently, suppose that each pair i i i has a type τ i ∈ { 0 , … , h } \tau_i\in\{0,\ldots,h\} τ i ∈ { 0 , … , h } with ρ i A , ρ i B ∈ ( κ τ i , κ τ i + 1 ) \rho_i^A,\rho_i^B\in(\kappa_{\tau_i},\kappa_{\tau_i+1}) ρ i A , ρ i B ∈ ( κ τ i , κ τ i + 1 ) , and that every γ j ∈ ( 0 , 1 / 2 ) \gamma_j\in(0,1/2) γ j ∈ ( 0 , 1/2 ) . Then every pair remains split or pooled, all responses are strict, the added voters remain at C C C , and
Φ ( I ) = { P ∖ I , x odd , { i ∈ I : τ i < k } ∪ { i ∈ P ∖ I : τ i < h − k } , x = 2 k . (2) \Phi(I)=
\begin{cases}
P\setminus I, & x\text{ odd},\\
\{i\in I:\tau_i<k\}\cup\{i\in P\setminus I:\tau_i<h-k\}, & x=2k.
\end{cases} \tag*{(2)} Φ ( I ) = { P ∖ I , { i ∈ I : τ i < k } ∪ { i ∈ P ∖ I : τ i < h − k } , x odd , x = 2 k . (2)
Proof. Consider an A ≻ C ≻ B A\succ C\succ B A ≻ C ≻ B voter with normalized utilities ( u ( A ) , u ( C ) , u ( B ) ) = ( 1 , ρ , 0 ) (u(A),u(C),u(B))=(1,\rho,0) ( u ( A ) , u ( C ) , u ( B )) = ( 1 , ρ , 0 ) , where 1 / 2 < ρ < 1 1/2<\rho<1 1/2 < ρ < 1 . Let d : = h − x d:=h-x d := h − x be the number of pooled pairs, so that C C C leads both A A A and B B B by 3 d 3d 3 d votes. Her private counts are
q A = ( x − 1 , x , x + 3 d ) q^A=(x-1,x,x+3d) q A = ( x − 1 , x , x + 3 d )
if her pair is split, so x > 0 x>0 x > 0 ,
q C = ( x , x , x + 3 d − 1 ) q^C=(x,x,x+3d-1) q C = ( x , x , x + 3 d − 1 )
if her pair is pooled, so x < h x<h x < h .
By Lemma 4.3 , she never votes B B B .
Which trembles matter. At a terminal private vector v v v , the comparison between A A A and C C C is zero whenever v A ≤ v C − 2 v_A\le v_C-2 v A ≤ v C − 2 and $v_B\le v_C-1: both ballots then leave C C C the unique winner. A nonzero contribution therefore requires
v A ≥ v C − 1 or v B ≥ v C . v_A\ge v_C-1\qquad\text{or}\qquad v_B\ge v_C. v A ≥ v C − 1 or v B ≥ v C .
Each tremble reduces either lead of C C C by at most two. To reduce a lead by 2 r 2r 2 r with r r r trembles, every tremble must move a ballot from C C C to the corresponding candidate. To reduce it by 2 r − 1 2r-1 2 r − 1 , either all r r r trembles have this direction, or exactly one reduces the lead by one. For the C C C –A A A lead, the latter directions are C ↦ B C\mapsto B C ↦ B and B ↦ A B\mapsto A B ↦ A ; for the C C C –B B B lead they are C ↦ A C\mapsto A C ↦ A and A ↦ B A\mapsto B A ↦ B . This gives the complete lists of first contributing flows below, and shows that all lower orders contribute nothing.
Odd number of split pairs. If x x x is odd, d d d is even. For d = 0 d=0 d = 0 , a split voter has margin ( 1 − 2 ρ ) / 3 < 0 (1-2\rho)/3<0 ( 1 − 2 ρ ) /3 < 0 without trembles, so she chooses C C C . For d ≥ 2 d\ge2 d ≥ 2 , put t = 3 d / 2 t=3d/2 t = 3 d /2 . At q C q^C q C , the first contributing order is t − 1 t-1 t − 1 , with the single flow ( t − 1 ) ( C ↦ A ) (t-1)(C\mapsto A) ( t − 1 ) ( C ↦ A ) and payoff difference ( 1 − ρ ) / 2 > 0 (1-\rho)/2>0 ( 1 − ρ ) /2 > 0 . At q A q^A q A , the first order is t t t , with flows t ( C ↦ A ) t(C\mapsto A) t ( C ↦ A ) and t ( C ↦ B ) t(C\mapsto B) t ( C ↦ B ) of equal multiplicity and payoff differences ( 1 − ρ ) / 2 (1-\rho)/2 ( 1 − ρ ) /2 and − ρ / 2 -\rho/2 − ρ /2 , whose sum is negative. Thus every pair changes configuration, proving the odd case of (2).
Even number of split pairs: pooled voters. Now let x = 2 k x=2k x = 2 k , so d d d is odd. First take d ≥ 3 d\ge3 d ≥ 3 and put t = ( 3 d − 1 ) / 2 t=(3d-1)/2 t = ( 3 d − 1 ) /2 . A pooled voter sees q C = ( x , x , x + 2 t ) q^C=(x,x,x+2t) q C = ( x , x , x + 2 t ) , and her first contributing order is t t t . After dividing multiplicities by ( x + 2 t t ) \binom{x+2t}{t} ( t x + 2 t ) , the complete list is
Table 1 (PDF p. 7).
For example, the second flow has multiplicity t ( x + 2 t t ) t\binom{x+2t}{t} t ( t x + 2 t ) , while the fourth has multiplicity x ( x + 2 t t − 1 ) x\binom{x+2t}{t-1} x ( t − 1 x + 2 t ) . Each order-t t t assignment carries the same probability factor 2 − t 2^{-t} 2 − t , so summing the table gives, up to a positive factor,
2 + t + t x x + t + 1 − ( 3 + t + t x x + t + 1 ) ρ . 2+t+\frac{tx}{x+t+1}-\left(3+t+\frac{tx}{x+t+1}\right)\rho. 2 + t + x + t + 1 t x − ( 3 + t + x + t + 1 t x ) ρ .
Its root defines κ h − k \kappa_{h-k} κ h − k ; away from equality, a pooled voter chooses A A A exactly below this root.
Even number of split pairs: split voters. If x > 0 x>0 x > 0 , a split voter sees
q A = ( x − 1 , x , x + 2 t + 1 ) , q^A=(x-1,x,x+2t+1), q A = ( x − 1 , x , x + 2 t + 1 ) ,
and her first contributing order is t + 1 t+1 t + 1 . The same gap reductions give two pure and four mixed flows, whose sum has the sign of
t + 3 + x ( t + 1 ) x + t + 1 − ( 2 t + 5 + ( 2 x − 1 ) ( t + 1 ) x + t + 1 ) ρ . t+3+\frac{x(t+1)}{x+t+1}-\left(2t+5+\frac{(2x-1)(t+1)}{x+t+1}\right)\rho. t + 3 + x + t + 1 x ( t + 1 ) − ( 2 t + 5 + x + t + 1 ( 2 x − 1 ) ( t + 1 ) ) ρ .
Its root defines κ k \kappa_k κ k ; away from equality, a split voter keeps A A A exactly below it. Appendix F lists all six flows and their multiplicities. When x = 0 x=0 x = 0 , no split voter exists, and κ 0 = 1 / 2 \kappa_0=1/2 κ 0 = 1/2 is only the lower utility bound.
The case of a single pooled pair. For d = 1 d=1 d = 1 , three-way ties change the calculation. The pooled voter’s order-one flows are C ↦ A C\mapsto A C ↦ A , C ↦ B C\mapsto B C ↦ B and B ↦ A B\mapsto A B ↦ A . For the split voter, the order-two mixed flow ( C ↦ A ) + ( C ↦ B ) (C\mapsto A)+(C\mapsto B) ( C ↦ A ) + ( C ↦ B ) produces a three-way tie, with payoff difference ( 1 − 2 ρ ) / 2 (1-2\rho)/2 ( 1 − 2 ρ ) /2 , and must be counted once. Summing the flow lists in Appendix F gives
κ h − k = 11 x + 16 13 x + 20 , κ k = 16 x + 20 29 x + 28 . \kappa_{h-k}=\frac{11x+16}{13x+20},\qquad
\kappa_k=\frac{16x+20}{29x+28}. κ h − k = 13 x + 20 11 x + 16 , κ k = 29 x + 28 16 x + 20 .
Ordering of the thresholds. The split thresholds lie in ( 1 / 2 , 2 / 3 ) (1/2,2/3) ( 1/2 , 2/3 ) and the pooled thresholds in ( 2 / 3 , 1 ) (2/3,1) ( 2/3 , 1 ) , and adjacent thresholds in each range are strictly increasing, including across d = 3 d=3 d = 3 and d = 1 d=1 d = 1 ; Appendix F gives the differences explicitly. Together with κ 0 = 1 / 2 \kappa_0=1/2 κ 0 = 1/2 and κ h + 1 = 1 \kappa_{h+1}=1 κ h + 1 = 1 , this proves the ordering κ 0 < κ 1 < ⋯ < κ h < κ h + 1 \kappa_0<\kappa_1<\cdots<\kappa_h<\kappa_{h+1} κ 0 < κ 1 < ⋯ < κ h < κ h + 1 stated in the lemma.
The paired map. Since every utility lies strictly between two consecutive thresholds, each leading coefficient is nonzero, and responses are strict. A split voter then keeps A A A precisely when τ i < k \tau_i<k τ i < k , and a pooled voter chooses A A A precisely when τ i < h − k \tau_i<h-k τ i < h − k . Exchanging A A A and B B B gives the same decision for her partner, so pairs remain split or pooled, and (2) follows.
The added voters. An added voter with C ≻ A ≻ B C\succ A\succ B C ≻ A ≻ B has private counts ( x , x , x + 3 d − 1 ) (x,x,x+3d-1) ( x , x , x + 3 d − 1 ) for utility vector x x x . Her margin for C C C over A A A is ( 1 − 2 γ j ) / 3 > 0 (1-2\gamma_j)/3>0 ( 1 − 2 γ j ) /3 > 0 at d = 0 d=0 d = 0 , and the same flow sums give positive leading coefficients for every d > 0 d>0 d > 0 when γ j < 1 / 2 \gamma_j<1/2 γ j < 1/2 (Appendix F). By Lemma 4.3 , she never votes B B B , so every added voter stays at C C C , and all responses are strict. □ \square □
Lemma 5.6 reduces Theorem 5.5 to iterating the map (2) on a well-chosen set of types. In short, an odd number of split pairs flips every pair, while an even number applies two ordered cutoffs to the types. The construction duplicates the higher types, so that each even step changes the number of split pairs by one layer of two pairs at a time; this lengthens the poll’s cycle. Two exceptional pairs, of types s − 1 s-1 s − 1 and s s s , exchange roles halfway through, which doubles the period of the complete profile.
Proof of Theorem 5.5. Set h = ℓ + 4 = 2 s + 1 h=\ell+4=2s+1 h = ℓ + 4 = 2 s + 1 , so that ℓ = 2 s − 3 \ell=2s-3 ℓ = 2 s − 3 . The construction uses two exceptional types, t 1 = s − 1 t_1=s-1 t 1 = s − 1 and t 2 = s t_2=s t 2 = s . We index them by σ ∈ { 1 , 2 } \sigma\in\{1,2\} σ ∈ { 1 , 2 } and write σ ˉ = 3 − σ \bar{\sigma}=3-\sigma σ ˉ = 3 − σ for the other index, so that t σ ˉ t_{\bar{\sigma}} t σ ˉ is the exceptional type other than t σ t_\sigma t σ . Take the pair set
P = { π 0 , π t 1 , π t 2 , π s + 2 , π h } ∪ ⋃ r = s + 3 2 s { π r 1 , π r 2 } , P=\{\pi_0,\pi_{t_1},\pi_{t_2},\pi_{s+2},\pi_h\}\cup\bigcup_{r=s+3}^{2s}\{\pi_r^1,\pi_r^2\}, P = { π 0 , π t 1 , π t 2 , π s + 2 , π h } ∪ r = s + 3 ⋃ 2 s { π r 1 , π r 2 } ,
where each pair’s type is its displayed subscript, and the two copies π r 1 , π r 2 \pi_r^1,\pi_r^2 π r 1 , π r 2 both have type r r r . There are 5 + 2 ( s − 2 ) = h 5+2(s-2)=h 5 + 2 ( s − 2 ) = h pairs. The product of the corresponding open utility intervals is nonempty and open, all comparisons are strict, and for each resulting election the responses persist for all sufficiently small p > 0 p>0 p > 0 .
For σ ∈ { 1 , 2 } \sigma\in\{1,2\} σ ∈ { 1 , 2 } and 0 ≤ j ≤ s − 3 0\leq j\leq s-3 0 ≤ j ≤ s − 3 , define the turning set T σ : = { π 0 , π t σ } T_\sigma:=\{\pi_0,\pi_{t_\sigma}\} T σ := { π 0 , π t σ } , the odd sets O σ , j : = T σ ∪ { π s + 2 } ∪ ⋃ r = s + 3 2 s − 1 − j { π r 1 , π r 2 } O_{\sigma,j}:=T_\sigma\cup\{\pi_{s+2}\}\cup\bigcup_{r=s+3}^{2s-1-j}\{\pi_r^1,\pi_r^2\} O σ , j := T σ ∪ { π s + 2 } ∪ ⋃ r = s + 3 2 s − 1 − j { π r 1 , π r 2 } , and the even sets E σ , j : = P ∖ O σ ˉ , j E_{\sigma,j}:=P\setminus O_{\bar{\sigma},j} E σ , j := P ∖ O σ ˉ , j , of respective sizes 2 2 2 , 2 s − 3 − 2 j 2s-3-2j 2 s − 3 − 2 j and 4 + 2 j 4+2j 4 + 2 j . Lemma 5.6 gives the chain
T σ ↦ O σ , 0 ↦ E σ , 0 ↦ O σ , 1 ↦ E σ , 1 ↦ ⋯ T_\sigma\mapsto O_{\sigma,0}\mapsto E_{\sigma,0}\mapsto O_{\sigma,1}\mapsto E_{\sigma,1}\mapsto\cdots T σ ↦ O σ , 0 ↦ E σ , 0 ↦ O σ , 1 ↦ E σ , 1 ↦ ⋯
↦ O σ , s − 3 ↦ E σ , s − 3 ↦ T σ ˉ , \mapsto O_{\sigma,s-3}\mapsto E_{\sigma,s-3}\mapsto T_{\bar{\sigma}}, ↦ O σ , s − 3 ↦ E σ , s − 3 ↦ T σ ˉ ,
hence the recurrent orbit runs from T 1 T_1 T 1 to T 2 T_2 T 2 along the chain with σ = 1 \sigma=1 σ = 1 , and back to T 1 T_1 T 1 along the chain with σ = 2 \sigma=2 σ = 2 . Indeed, at T σ T_\sigma T σ we have k = 1 k=1 k = 1 : only π 0 \pi_0 π 0 stays split, and precisely the pooled pairs of type below 2 s 2s 2 s join it. Each O σ , j O_{\sigma,j} O σ , j has odd size and is therefore complemented. At E σ , j E_{\sigma,j} E σ , j , we have k = j + 2 k=j+2 k = j + 2 : no split type is below k k k , while the pooled types strictly below 2 s − j − 1 2s-j-1 2 s − j − 1 form O σ ˉ , j + 1 O_{\bar{\sigma},j+1} O σ ˉ , j + 1 when j < s − 3 j<s-3 j < s − 3 , and T σ ˉ T_{\bar{\sigma}} T σ ˉ when j = s − 3 j=s-3 j = s − 3 .
The passage from T 1 T_1 T 1 to T 2 T_2 T 2 takes 1 + 2 ( s − 2 ) = ℓ 1+2(s-2)=\ell 1 + 2 ( s − 2 ) = ℓ updates, during which the numbers of split pairs are ∣ T 1 ∣ = 2 |T_1|=2 ∣ T 1 ∣ = 2 , followed by ∣ O 2 , j ∣ = 2 s − 3 − 2 j |O_{2,j}|=2s-3-2j ∣ O 2 , j ∣ = 2 s − 3 − 2 j and ∣ E 1 , j ∣ = 4 + 2 j |E_{1,j}|=4+2j ∣ E 1 , j ∣ = 4 + 2 j for j = 0 , … , s − 3 j=0,\ldots,s-3 j = 0 , … , s − 3 . These ℓ \ell ℓ numbers are pairwise distinct: after the initial 2 2 2 , the odd values decrease from 2 s − 3 2s-3 2 s − 3 to 3 3 3 , while the even values increase from 4 4 4 to 2 s − 2 2s-2 2 s − 2 . Since the poll (1) is determined by the number of split pairs, it first returns after exactly ℓ \ell ℓ updates. At that time, T 1 T_1 T 1 has become the distinct set T 2 T_2 T 2 , and only after ℓ \ell ℓ further updates do the split pairs return as well. Any return of the profile is also a return of the poll, so the profile has period exactly 2 ℓ 2\ell 2 ℓ .
Finally, from truthful votes every pair is split, and Equation (2) gives the entry path P ↦ ∅ ↦ P ∖ { π h } ↦ T 1 P\mapsto\varnothing\mapsto P\setminus\{\pi_h\}\mapsto T_1 P ↦ ∅ ↦ P ∖ { π h } ↦ T 1 : the odd-size set P P P is complemented, every pair except π h \pi_h π h then splits, and at k = s k=s k = s the cutoff retains exactly π 0 \pi_0 π 0 and π t 1 \pi_{t_1} π t 1 . The transient numbers of split pairs, h h h , 0 0 0 and 2 s 2s 2 s , lie outside the range [ 2 , 2 s − 2 ] [2,2s-2] [ 2 , 2 s − 2 ] of the orbit, so the orbit is entered after exactly three updates. Since 2 ≤ x < h 2\leq x<h 2 ≤ x < h on the orbit, Equation (1) gives every candidate positive support and n C − n A = n C − n B = 3 ( h − x ) > 0 n_C-n_A=n_C-n_B=3(h-x)>0 n C − n A = n C − n B = 3 ( h − x ) > 0 . For s = 3 s=3 s = 3 , the chain reduces to j = 0 j=0 j = 0 , which covers ℓ = 3 \ell=3 ℓ = 3 . □
The theorem gives an open set of cardinal utilities, not just of rankings, since normalizing by the gap between top and bottom utilities is continuous on each strict-ranking region. Both periods grow linearly with the electorate, while the number of candidates stays at three: C C C remains uniquely ahead throughout, yet neither the ballots nor the poll ever stabilize.
Discussion
Summary of findings. We studied what happens when every voter in a fixed, finite electorate responds to the same poll, using trembling-hand beliefs to decide between ballots that the poll alone leaves equivalent. A single revision typically produces a stable sincere runoff between the two poll leaders: although the dynamics are deterministic, a population drawn from any fixed distribution of preferences rarely contains the near-ties needed to prevent Duverger’s law. Cycles are therefore unlikely, but their behavior can be rich: already with three candidates, cycles can have arbitrarily long periods, keep changing the poll, or let different candidates take turns as the unique winner.
What drives convergence, and what breaks it. Three ingredients shape the dynamics. First, separation: when the runner-up is clearly ahead, a few trembles can only make the leaders’ race close, and every voter simply picks between them. Second, simultaneity: when all voters react to the same poll, sensible individual responses can cancel out or overshoot, and several of our cycles rely on this synchronization; whether cycles also arise under sequential updates, as in related models [12 , 18 ] , is left open. Third, own-ballot discounting: the same poll can prompt opposite responses from identical voters, a feature our long cycles rely on and that poll-based responses alone cannot capture.
Polls in practice. With due caution, these results suggest that a clear first poll is the main driver of coordination, while repeated polls in close three-way races may induce oscillations rather than settle them. Experiments show that real voters do react to poll information [6 ] , and synchronous cycles in related models persist when only a large fraction of voters update [12 ] . Whether such oscillations are observable in actual elections is beyond the scope of this paper.
Open questions. A first set of questions concerns where cycles arise. Our conditions for one-step convergence are sufficient, and matching necessary conditions would show where cycles can start, although a full characterization may be out of reach: even deciding whether a trembling-hand equilibrium with a given winner exists is NP-hard [22 ] . Within the cycles themselves, our computer search suggests that six active voters are the minimum for period three, which remains to be proved. Whether long cycles can also change the leader, and how cycle lengths are distributed under random preferences, remain similarly open. A second set of questions concerns the model itself. Partial or asynchronous revisions, and other voting rules such as runoff voting, would test which of our findings depend on the synchronous plurality setting. More fundamentally, two stochastic variants would make the model more realistic: voters whose hands actually tremble, so that their beliefs about others’ deviations become consistent with their own behavior; or polls that sample only a random subset of the electorate, so that uncertainty stems from the information rather than from beliefs about other voters. Both turn the deterministic dynamics into a Markov chain, whose long-run behavior we expect to favor Duvergerian profiles, but which calls for different tools to analyze.
CRediT Author Statement
Maximilian Weigel: Methodology, Software, Formal Analysis, Investigation, Writing – Original Draft, Visualization. Damien Berriaud: Conceptualization, Methodology, Writing – Review & Editing, Visualization, Supervision. Roger Wattenhofer: Supervision, Funding Acquisition.
References
This Appendix gives the coefficient calculations and case reductions used in the paper. All calculations use three candidates and uniform trembles: each other ballot stays with probability 1 − p 1-p 1 − p and moves to either alternative with probability p / 2 p/2 p /2 . As in Section 3, a tied winner set is valued by its uniform lottery, q q q denotes the private counts, which exclude the focal ballot, and v v v denotes a terminal private vector.
For a fixed voter, we suppress her index and write Δ p ( c , c ′ ∣ q ) = U p ( c ∣ q ) − U p ( c ′ ∣ q ) \Delta^{p}(c,c' \mid q)=U^{p}(c\mid q)-U^{p}(c'\mid q) Δ p ( c , c ′ ∣ q ) = U p ( c ∣ q ) − U p ( c ′ ∣ q ) . A margin written c − c ′ c-c' c − c ′ means this difference at the displayed private vector. We use A , B , C A,B,C A , B , C for named candidates and X ≻ Y ≻ Z X\succ Y\succ Z X ≻ Y ≻ Z for a voter’s favorite, middle, and least-preferred candidate. The first nonzero coefficient determines a margin’s sign for sufficiently small positive p p p ; if a coefficient vanishes, later orders decide.
Counting Directed Trembles
We first give a formula for calculating expected-utility differences by group the believed trembles according to their number. The first nonzero coefficient determines the limiting comparison as p → 0 p\to0 p → 0 . Nevertheless, we have to take all contributions at that order into account. Lemma A.1 provides the formula used in the response calculations and cycle examples below.
Lemma A.1. Fix a voter with private counts q = ( q A , q B , q C ) q=(q_A,q_B,q_C) q = ( q A , q B , q C ) and write ∣ q ∣ : = q A + q B + q C |q|:=q_A+q_B+q_C ∣ q ∣ := q A + q B + q C . For η ∈ N 0 \eta\in\mathbb{N}_0 η ∈ N 0 , let F η ( q ) F_\eta(q) F η ( q ) be the set of flows f = ( f c c ′ ) c ≠ c ′ f=(f_{cc'})_{c\ne c'} f = ( f c c ′ ) c = c ′ of nonnegative integers satisfying
∑ c ≠ c ′ f c c ′ = η , ∑ c ′ ≠ c f c c ′ ≤ q c for every c . \sum_{c\ne c'}f_{cc'}=\eta,\qquad\sum_{c'\ne c}f_{cc'}\le q_c\quad\text{for every }c. c = c ′ ∑ f c c ′ = η , c ′ = c ∑ f c c ′ ≤ q c for every c . Here f c c ′ f_{cc'} f c c ′ counts the ballots moving from c c c to c ′ c' c ′ , and the inequalities ensure that the flows do not exceed the number of counts they depart from. The change in the private counts is
( D f ) c : = ∑ c ′ ≠ c f c ′ c − ∑ c ′ ≠ c f c c ′ (D_f)_c:=\sum_{c'\ne c}f_{c'c}-\sum_{c'\ne c}f_{cc'} ( D f ) c := c ′ = c ∑ f c ′ c − c ′ = c ∑ f c c ′ so the resulting private counts are q + D f q+D_f q + D f . The number of assignments of individual ballots producing this flow is
M q ( f ) : = ∏ c q c ! ( q c − ∑ c ′ ≠ c f c c ′ ) ! ∏ c ′ ≠ c f c c ′ ! . M_q(f):=\prod_c\frac{q_c!}{\left(q_c-\sum_{c'\ne c}f_{cc'}\right)!\prod_{c'\ne c}f_{cc'}!}. M q ( f ) := c ∏ ( q c − ∑ c ′ = c f c c ′ ) ! ∏ c ′ = c f c c ′ ! q c ! . For two contemplated ballots c c c and c ′ c' c ′ , define
H η ( c , c ′ ; q ) : = ∑ f ∈ F η ( q ) M q ( f ) [ u ( W ( q + D f + e c ) ) − u ( W ( q + D f + e c ′ ) ) ] . H_\eta(c,c';q):=\sum_{f\in F_\eta(q)}M_q(f)\left[u\left(W(q+D_f+e_c)\right)-u\left(W(q+D_f+e_{c'})\right)\right]. H η ( c , c ′ ; q ) := f ∈ F η ( q ) ∑ M q ( f ) [ u ( W ( q + D f + e c ) ) − u ( W ( q + D f + e c ′ ) ) ] . Under the uniform three-candidate tremble belief,
U p ( c ∣ q ) − U p ( c ′ ∣ q ) = ∑ η = 0 ∣ q ∣ ( p 2 ) η ( 1 − p ) ∣ q ∣ − η H η ( c , c ′ ; q ) . U^p(c\mid q)-U^p(c'\mid q)=\sum_{\eta=0}^{|q|}\left(\frac{p}{2}\right)^\eta(1-p)^{|q|-\eta}H_\eta(c,c';q). U p ( c ∣ q ) − U p ( c ′ ∣ q ) = η = 0 ∑ ∣ q ∣ ( 2 p ) η ( 1 − p ) ∣ q ∣ − η H η ( c , c ′ ; q ) . In particular, if d ∈ N 0 d\in\mathbb{N}_0 d ∈ N 0 and H η ( c , c ′ ; q ) = 0 H_\eta(c,c';q)=0 H η ( c , c ′ ; q ) = 0 for every η < d \eta<d η < d , then
[ p d ] ( U p ( c ∣ q ) − U p ( c ′ ∣ q ) ) = 2 − d H d ( c , c ′ ; q ) . [p^d]\left(U^p(c\mid q)-U^p(c'\mid q)\right)=2^{-d}H_d(c,c';q). [ p d ] ( U p ( c ∣ q ) − U p ( c ′ ∣ q ) ) = 2 − d H d ( c , c ′ ; q ) .
Proof. For each candidate c c c , the multinomial factor in M q ( f ) M_q(f) M q ( f ) chooses which of the q c q_c q c ballots supporting c c c move to either other candidate. Each moved ballot contributes p / 2 p/2 p /2 and each unchanged ballot contributes 1 − p 1-p 1 − p . A flow with η \eta η trembles therefore has probability
M q ( f ) ( p 2 ) η ( 1 − p ) ∣ q ∣ − η . M_q(f)\left(\frac{p}{2}\right)^\eta(1-p)^{|q|-\eta}. M q ( f ) ( 2 p ) η ( 1 − p ) ∣ q ∣ − η .
Summing its payoff difference over all flows proves the expansion. If H η = 0 H_\eta=0 H η = 0 for every η < d \eta<d η < d , the terms with η < d \eta<d η < d vanish and those with η > d \eta>d η > d contain the factor p η p^\eta p η . The coefficient of p d p^d p d is therefore 2 − d H d 2^{-d}H_d 2 − d H d .
Proof of Theorem 4.4
Theorem 4.4 asserts both that the first update concentrates support on the initial leaders and that the resulting profile is stable. We first calculate the individual responses under the given gap conditions, where we separate the even and odd leader gaps. Then we verify that no voter switches at the resulting profile.
The Three-Candidate Response Calculation
Write
( n A 0 , n B 0 , n C 0 ) = ( r + d , r − s ) , r ≥ 2 , d ≥ 0 , 1 ≤ s ≤ r − 1. (n_A^0,n_B^0,n_C^0)=(r+d,r-s),\qquad r\ge2,\quad d\ge0,\quad1\le s\le r-1. ( n A 0 , n B 0 , n C 0 ) = ( r + d , r − s ) , r ≥ 2 , d ≥ 0 , 1 ≤ s ≤ r − 1.
The private vectors of an A A A -, B B B -, and C C C -voter are
q A = ( r + d − 1 , r , r − s ) , q B = ( r + d , r − 1 , r − s ) , q C = ( r + d , r , r − s − 1 ) . q^A=(r+d-1,r,r-s),\qquad q^B=(r+d,r-1,r-s),\qquad q^C=(r+d,r,r-s-1). q A = ( r + d − 1 , r , r − s ) , q B = ( r + d , r − 1 , r − s ) , q C = ( r + d , r , r − s − 1 ) .
For terminal private vectors v v v , one directed tremble changes the two gaps as follows (the rows always give the decrease):
Each tremble reduces a given gap by at most two. Reducing it by at least 2 j 2j 2 j in j j j trembles therefore requires every tremble to move from the leader to the other candidate. To reduce it by at least 2 j − 1 2j-1 2 j − 1 , either all j j j trembles reduce it by two or exactly one reduces it by one. Checking when the contemplated ballots give different winner sets gives the complete flow lists below and shows that all earlier coefficients vanish.
For d = 0 d=0 d = 0 , staying restores the A A A –B B B tie for a truthful A A A -voter. Switching to B B B makes B B B win alone; switching to C C C leaves B B B alone when s ≥ 2 s\ge2 s ≥ 2 and creates a B B B –C C C tie when s = 1 s=1 s = 1 . Both alternatives are strictly worse because A A A is her favorite. The symmetric comparison holds for a truthful B B B -voter. A truthful C C C -voter chooses between making A A A or B B B win alone and retaining the A A A –B B B tie. She therefore chooses the one of A , B A,B A , B she prefers. Suppose first that d = 2 k > 0 d=2k>0 d = 2 k > 0 and put a = r + 2 k a=r+2k a = r + 2 k , with ( x − 1 ) = 0 \binom{x}{-1}=0 ( − 1 x ) = 0 . Lemma A.1 gives the following first nonzero coefficients:
The contributing flows, in the same row order as (B.3), are
( k − 1 ) ( A ↦ B ) (k-1)(A\mapsto B) ( k − 1 ) ( A ↦ B )
k ( A ↦ B ) k(A\mapsto B) k ( A ↦ B )
k ( A ↦ B ) , k ( A ↦ C ) k(A\mapsto B),\ k(A\mapsto C) k ( A ↦ B ) , k ( A ↦ C ) only when s = 1 s=1 s = 1
k ( A ↦ B ) k(A\mapsto B) k ( A ↦ B )
k ( A ↦ B ) , ( k − 1 ) ( A ↦ B ) + ( A ↦ C or C ↦ B ) k(A\mapsto B),\ (k-1)(A\mapsto B)+(A\mapsto C\text{ or }C\mapsto B) k ( A ↦ B ) , ( k − 1 ) ( A ↦ B ) + ( A ↦ C or C ↦ B )
For example, in the third row with s = 1 s=1 s = 1 the two equal multiplicities ( a k ) \binom{a}{k} ( k a ) multiply payoff changes ( u ( B ) − u ( A ) ) / 2 (u(B)-u(A))/2 ( u ( B ) − u ( A )) /2 and ( u ( A ) − u ( C ) ) / 2 (u(A)-u(C))/2 ( u ( A ) − u ( C )) /2 . In the last row, the two mixed-flow multiplicities sum to ( k k − 1 ) + ( r − s − 1 k − 1 ) \binom{k}{k-1} + \binom{r-s-1}{k-1} ( k − 1 k ) + ( k − 1 r − s − 1 ) ; adding the pure flow gives (B.3).
The remaining even-gap comparison is A − C A-C A − C at q A q^A q A . Below order k k k both ballots leave A A A the unique winner. At order k k k , (B.2) implies v A ≥ v C v_A \ge v_C v A ≥ v C and v B ≤ v A + 1 v_B \le v_A + 1 v B ≤ v A + 1 . If v B ≤ v A v_B \le v_A v B ≤ v A , ballot A A A makes the voter’s favorite the unique winner. Otherwise v B = v A + 1 v_B = v_A + 1 v B = v A + 1 : ballot A A A gives an A A A –B B B tie, whereas ballot C C C gives either B B B alone or a B B B –C C C tie. Thus every contribution is nonnegative for A ≻ C ≻ B A \succ C \succ B A ≻ C ≻ B . The flow k ( A ↦ B ) k(A \mapsto B) k ( A ↦ B ) is strictly positive, with payoff change ( u ( A ) − u ( B ) ) / 2 (u(A)-u(B))/2 ( u ( A ) − u ( B )) /2 . Therefore its order-k k k coefficient is strictly positive.
Now let d = 2 k + 1 d=2k+1 d = 2 k + 1 and s ≥ 2 s\ge2 s ≥ 2 , and put a = r + 2 k + 1 a=r+2k+1 a = r + 2 k + 1 . The first nonzero coefficients are
Table B.5.
The decisive flows in the six rows are, respectively,
k ( A ↦ B ) k(A\mapsto B) k ( A ↦ B ) , ( k − 1 ) ( A ↦ B ) + ( A ↦ C or C ↦ B ) (k-1)(A\mapsto B)+(A\mapsto C\ \text{or}\ C\mapsto B) ( k − 1 ) ( A ↦ B ) + ( A ↦ C or C ↦ B )
k ( A ↦ B ) k(A\mapsto B) k ( A ↦ B )
( k + 1 ) ( A ↦ B ) (k+1)(A\mapsto B) ( k + 1 ) ( A ↦ B ) , k ( A ↦ B ) + ( A ↦ C or C ↦ B ) k(A\mapsto B)+(A\mapsto C\ \text{or}\ C\mapsto B) k ( A ↦ B ) + ( A ↦ C or C ↦ B )
the flows in row 3; also ( k + 1 ) ( A ↦ C ) (k+1)(A\mapsto C) ( k + 1 ) ( A ↦ C ) when s = 2 s=2 s = 2
( k + 1 ) ( A ↦ B ) (k+1)(A\mapsto B) ( k + 1 ) ( A ↦ B ) , k ( A ↦ B ) + ( A ↦ C or C ↦ B ) k(A\mapsto B)+(A\mapsto C\ \text{or}\ C\mapsto B) k ( A ↦ B ) + ( A ↦ C or C ↦ B )
k ( A ↦ B ) k(A\mapsto B) k ( A ↦ B )
Terms containing k − 1 k-1 k − 1 are absent when k = 0 k=0 k = 0 . The mixed-flow multiplicities in rows 1, 3, and 5 are ( 2 r + k + 1 − s ) ( a − 1 k − 1 ) (2r+k+1-s)\binom{a-1}{k-1} ( 2 r + k + 1 − s ) ( k − 1 a − 1 ) , ( 2 r + k + 1 − s ) ( a k ) (2r+k+1-s)\binom{a}{k} ( 2 r + k + 1 − s ) ( k a ) , and ( 2 r + k − s ) ( a k ) (2r+k-s)\binom{a}{k} ( 2 r + k − s ) ( k a ) , respectively. Formula (B.2) also shows that C C C cannot enter an earlier winner set and can enter the first contributing order only when s = 2 s=2 s = 2 . In that case, the fourth coefficient in (B.5) rewrites as
2 − k − 2 [ ( a k + 1 ) ( u ( B ) − u ( C ) ) + ( 2 r + k − 1 ) ( a k ) ( u ( B ) − u ( A ) ) ] > 0. (3) 2^{-k-2}\left[\binom{a}{k+1}(u(B)-u(C))+(2r+k-1)\binom{a}{k}(u(B)-u(A))\right]>0. \tag*{(3)} 2 − k − 2 [ ( k + 1 a ) ( u ( B ) − u ( C )) + ( 2 r + k − 1 ) ( k a ) ( u ( B ) − u ( A )) ] > 0. (3)
When k = 0 = s − 2 k=0=s-2 k = 0 = s − 2 , the flow A ↦ C A\mapsto C A ↦ C in (B.6) is one flow whose payoff is corrected from ( u ( B ) − u ( A ) ) / 2 (u(B)-u(A))/2 ( u ( B ) − u ( A )) /2 to ( u ( B ) − u ( C ) ) / 2 (u(B)-u(C))/2 ( u ( B ) − u ( C )) /2 , not a second copy. Equations (B.3)–(B.7), together with Lemma 4.3, prove every entry of the response table in the main proof.
Why the Successor Is Stable
Removing all support from C C C after one update does not by itself establish convergence. We must also show that every voter keeps her new ballot. The argument below covers the resulting profile for the remaining two candidates.
Suppose a profile has counts ( a , b , 0 ) (a,b,0) ( a , b , 0 ) with a , b ≥ 3 a,b\ge3 a , b ≥ 3 , every A A A -supporter prefers A A A to B B B , and every B B B -supporter prefers B B B to A A A . An A A A -supporter has private counts q = ( a − 1 , b , 0 ) q=(a-1,b,0) q = ( a − 1 , b , 0 ) . If q A ≥ 3 q_A\ge3 q A ≥ 3 , Lemma 4.1 makes her stay. Otherwise q A = 2 q_A=2 q A = 2 . Put η = ⌊ ( q B − 2 ) / 2 ⌋ \eta=\lfloor(q_B-2)/2\rfloor η = ⌊( q B − 2 ) /2 ⌋ . Throughout that most η \eta η trembles, every voter who satisfies v B − v C ≥ q B − 2 η ≥ 2 v_B-v_C\ge q_B-2\eta\ge2 v B − v C ≥ q B − 2 η ≥ 2 , so C C C cannot win after any contemplated ballot. Voting for A A A is therefore weakly better than either alternative because u ( A ) > u ( B ) u(A)>u(B) u ( A ) > u ( B ) . The flow η ( B ↦ A ) \eta(B\mapsto A) η ( B ↦ A ) leaves v B − v A ∈ { 0 , 1 } v_B-v_A\in\{0,1\} v B − v A ∈ { 0 , 1 } and makes ballot A A A strictly better than both alternatives. For each comparison, its first nonzero coefficient is consequently a positive sum of contributions at some order at most η \eta η , by Lemma A.1. Exchanging A , B A,B A , B proves that every supporter stays, so the profile is stable.
The successor in Theorem 4.4 is
( r + d + x , 2 r − s − x , 0 ) , 0 ≤ x ≤ r − s . (4) (r+d+x,\ 2r-s-x,\ 0),\qquad0\le x\le r-s. \tag*{(4)} ( r + d + x , 2 r − s − x , 0 ) , 0 ≤ x ≤ r − s . (4)
and every supporter prefers her current top to the other supported candidate. Both supported counts are at least three when r ≥ 3 r\ge3 r ≥ 3 , so the preceding argument applies. If r = 2 r=2 r = 2 , then s = 1 s=1 s = 1 , d = 2 j − 2 d=2j-2 d = 2 j − 2 for some j ≥ 1 j\ge1 j ≥ 1 , and the two possible successors are ( 2 j , 3 , 0 ) (2j,3,0) ( 2 j , 3 , 0 ) and ( 2 j + 1 , 2 , 0 ) (2j+1,2,0) ( 2 j + 1 , 2 , 0 ) . The first is covered above for j ≥ 2. F o r j\ge2. For j ≥ 2. F or (2,3,0)$, the required margins are
Table B.9.
In ( 2 , 3 , 0 ) (2,3,0) ( 2 , 3 , 0 ) , both A A A -supporters are original truthful A A A -voters, so 2 u ( A ) − u ( B ) − u ( C ) > 0 2u(A)-u(B)-u(C)>0 2 u ( A ) − u ( B ) − u ( C ) > 0 in (B.9). For ( 2 j + 1 , 2 , 0 ) (2j+1,2,0) ( 2 j + 1 , 2 , 0 ) , an A A A -supporter has q = ( 2 j , 2 , 0 ) q=(2j,2,0) q = ( 2 j , 2 , 0 ) and a B B B -supporter has q = ( 2 j + 1 , 1 , 0 ) q=(2j+1,1,0) q = ( 2 j + 1 , 1 , 0 ) . With μ j = 2 − j − 1 ( 2 j + 1 j ) \mu_j=2^{-j-1}\binom{2j+1}{j} μ j = 2 − j − 1 ( j 2 j + 1 ) , the first coefficients are
[ p j − 1 ] Δ p ( A , C ∣ ( 2 j , 2 , 0 ) ) = 2 − j ( 2 j j − 1 ) ( u ( A ) − u ( B ) ) , [p^{j-1}]\Delta^p(A,C\mid(2j,2,0))=2^{-j}\binom{2j}{j-1}(u(A)-u(B)), [ p j − 1 ] Δ p ( A , C ∣ ( 2 j , 2 , 0 )) = 2 − j ( j − 1 2 j ) ( u ( A ) − u ( B )) ,
[ p j − 1 ] Δ p ( A , B ∣ ( 2 j , 2 , 0 ) ) = 2 − j ( j + 1 ) ( 2 j j ) ( u ( A ) − u ( B ) ) , [p^{j-1}]\Delta^p(A,B\mid(2j,2,0))=2^{-j}(j+1)\binom{2j}{j}(u(A)-u(B)), [ p j − 1 ] Δ p ( A , B ∣ ( 2 j , 2 , 0 )) = 2 − j ( j + 1 ) ( j 2 j ) ( u ( A ) − u ( B )) ,
[ p j ] Δ p ( B , A ∣ ( 2 j + 1 , 1 , 0 ) ) = μ j ( j + 2 ) ( u ( B ) − u ( A ) ) , [p^j]\Delta^p(B,A\mid(2j+1,1,0))=\mu_j(j+2)(u(B)-u(A)), [ p j ] Δ p ( B , A ∣ ( 2 j + 1 , 1 , 0 )) = μ j ( j + 2 ) ( u ( B ) − u ( A )) ,
[ p j ] Δ p ( B , C ∣ ( 2 j + 1 , 1 , 0 ) ) = μ j ( ( j + 1 ) u ( B ) − j u ( A ) − u ( C ) ) . (5) [p^j]\Delta^p(B,C\mid(2j+1,1,0))=\mu_j((j+1)u(B)-ju(A)-u(C)). \tag*{(5)} [ p j ] Δ p ( B , C ∣ ( 2 j + 1 , 1 , 0 )) = μ j (( j + 1 ) u ( B ) − j u ( A ) − u ( C )) . (5)
The first two lines come from the pure flow ( j − 1 ) ( A ↦ B ) (j-1)(A\mapsto B) ( j − 1 ) ( A ↦ B ) and, for A − B A-B A − B , the additional flow ( j − 2 ) ( A ↦ B ) + ( A ↦ C ) (j-2)(A\mapsto B)+(A\mapsto C) ( j − 2 ) ( A ↦ B ) + ( A ↦ C ) , which is absent when j = 1 j=1 j = 1 . The last two come from j ( A ↦ B ) j(A\mapsto B) j ( A ↦ B ) and ( j − 1 ) ( A ↦ B ) + ( A ↦ C ) (j-1)(A\mapsto B)+(A\mapsto C) ( j − 1 ) ( A ↦ B ) + ( A ↦ C ) ; for B − C B-C B − C one also includes j ( A ↦ C ) j(A\mapsto C) j ( A ↦ C ) . At j = 1 j=1 j = 1 , the last two descriptions of A ↦ C A\mapsto C A ↦ C denote the same flow, which is counted once with its actual payoff. All four expressions are positive: the last equals μ j [ j ( u ( B ) − u ( A ) ) + u ( B ) − u ( C ) ] \mu_j[j(u(B)-u(A))+u(B)-u(C)] μ j [ j ( u ( B ) − u ( A )) + u ( B ) − u ( C )] , and every B B B -supporter in this case is a truthful B B B -voter. Hence both boundary successors are stable, completing the calculation.
Proof of Theorem 5.2
Theorem 5.2. With three candidates, every period-three cycle of the complete ballot profile has at least four active voters.
We prove the lower bound in Theorem 5.2 without assuming truthful initialization or restricting the ballots of inactive voters. We first reduce the possible ballot paths to two stay patterns, then prove the response comparisons needed to exclude both. The final two subsections verify that the case reductions used in this argument are indeed exhaustive.
Ballot Paths and Stay Patterns
Lemma C.1. On a period-three cycle, every active voter uses her favorite and middle candidate and stays in exactly one of the three transitions. There are at least three active voters. With exactly three, the numbers of active voters are, up to a cyclic shift,
( 2 , 1 , 0 ) or ( 1 , 1 , 1 ) . (2,1,0)\qquad\text{or}\qquad(1,1,1). ( 2 , 1 , 0 ) or ( 1 , 1 , 1 ) .
Proof. Lemma 4.3 restricts every ballot on the orbit to the voter’s two highest-ranked candidates. A nonconstant cyclic word of length three on two candidates has exactly one stay. Equal private counts require equal responses. In particular, a voter who is the only mover in a transition must stay in the next transition: the other ballots have not changed between the two source phases.
One active voter faces constant private counts and cannot cycle. With two active voters, a stay by voter 1 makes voter 2 the sole mover, so voter 2 stays next. Voter 1 is then the sole mover and must stay again, contradicting her unique stay. A transition in which both stay would already be stable.
With three active voters, there are three stays in total, and no transition has three stays. If a transition has two stays, its sole mover stays next, so the stay counts are (2, 1, 0) up to a cyclic shift. Otherwise every transition has one stay. □
Response Comparisons
The following comparisons restrict the responses that the two stay patterns can require. We prove them for a single voter and then apply them to the private counts determined by the other active ballots and the fixed inactive ballots.
Fix one voter and rename her candidates so that X ≻ Y ≻ Z X \succ Y \succ Z X ≻ Y ≻ Z , ( u ( X ) , u ( Y ) , u ( Z ) ) = ( 1 , ρ , 0 ) (u(X),u(Y),u(Z))=(1,\rho,0) ( u ( X ) , u ( Y ) , u ( Z )) = ( 1 , ρ , 0 ) , 0 < ρ < 1 0 < \rho< 1 0 < ρ < 1 .
We write BR ( q ) \operatorname{BR}(q) BR ( q ) for her response to the private count vector q q q . The directed-flow expansion of Lemma A.1 will be used throughout.
Lemma C.2. If q X ≥ q Y q_X \ge q_Y q X ≥ q Y , ballot X X X strictly beats ballot Y Y Y for every 0 < p < 2 / 3 0 < p < 2/3 0 < p < 2/3 . Hence a limiting middle response requires q Y > q X q_Y > q_X q Y > q X .
Proof. Normalize the utilities to ( u ( X ) , u ( Y ) , u ( Z ) ) = ( 1 , ρ , 0 ) (u(X),u(Y),u(Z))=(1,\rho,0) ( u ( X ) , u ( Y ) , u ( Z )) = ( 1 , ρ , 0 ) , where 0 < ρ < 1 0 < \rho< 1 0 < ρ < 1 . Put α = 1 − p \alpha=1-p α = 1 − p and β = p / 2 \beta=p/2 β = p /2 . For 0 < p < 2 / 3 0 < p < 2/3 0 < p < 2/3 , we have α > β > 0 \alpha> \beta> 0 α > β > 0 .
First compare the probabilities of terminal private vectors obtained by exchanging the counts of X X X and Y Y Y . Let P q ( v ) P_q(v) P q ( v ) be the probability of v v v , and let σ v \sigma v σ v exchange its X X X - and Y Y Y -coordinates. We show that
P q ( v ) ≥ P q ( σ v ) whenever v X ≥ v Y . (6) P_q(v) \ge P_q(\sigma v) \qquad\text{whenever } v_X \ge v_Y. \tag*{(6)} P q ( v ) ≥ P q ( σ v ) whenever v X ≥ v Y . (6)
Write q X = q Y + k q_X=q_Y+k q X = q Y + k , where k ≥ 0 k \ge0 k ≥ 0 . The probability P q ( v ) P_q(v) P q ( v ) is the coefficient of s v X t v Y w v Z s^{v_X}t^{v_Y}w^{v_Z} s v X t v Y w v Z in
( α s + β t + β w ) q Y ( β s + α t + β w ) k [ β ( s + t ) + α w ] q Z . (\alpha s+\beta t+\beta w)^{q_Y}(\beta s+\alpha t+\beta w)^k[\beta(s+t)+\alpha w]^{q_Z}. ( α s + β t + β w ) q Y ( β s + α t + β w ) k [ β ( s + t ) + α w ] q Z .
The two relevant factors can be written as
( α s + β t + β w ) ( β s + α t + β w ) = α β ( s + t ) 2 + ( α − β ) 2 s t + β ( α + β ) w ( s + t ) + β 2 w 2 , (\alpha s+\beta t+\beta w)(\beta s+\alpha t+\beta w)
=\alpha\beta(s+t)^2+(\alpha-\beta)^2st+\beta(\alpha+\beta)w(s+t)+\beta^2w^2, ( α s + β t + β w ) ( β s + α t + β w ) = α β ( s + t ) 2 + ( α − β ) 2 s t + β ( α + β ) w ( s + t ) + β 2 w 2 ,
and
α s + β t + β w = β ( s + t ) + ( α − β ) s + β w . \alpha s+\beta t+\beta w=\beta(s+t)+(\alpha-\beta)s+\beta w. α s + β t + β w = β ( s + t ) + ( α − β ) s + β w .
All displayed coefficients are nonnegative. After fixing the power of w w w , expanding these factors therefore gives a sum of nonnegative multiples of terms
s a t b ( s + t ) ℓ , a ≥ b ≥ 0 , ℓ ≥ 0. s^at^b(s+t)^\ell,\qquad a\ge b\ge0,\quad\ell\ge0. s a t b ( s + t ) ℓ , a ≥ b ≥ 0 , ℓ ≥ 0.
In each such term, the coefficients corresponding to v v v and σ v \sigma v σ v are
( ℓ v X − a ) , ( ℓ v Y − a ) , \binom{\ell}{v_X-a},\qquad\binom{\ell}{v_Y-a}, ( v X − a ℓ ) , ( v Y − a ℓ ) ,
respectively. We interpret a binomial coefficient as zero when its lower index is outside { 0 , … , ℓ } \{0,\ldots,\ell\} { 0 , … , ℓ } . Since v X + v Y = a + b + ℓ v_X+v_Y=a+b+\ell v X + v Y = a + b + ℓ , the two lower indices satisfy
v X − a ≥ v Y − a , ( v X − a ) + ( v Y − a ) = ℓ − ( a − b ) ≤ ℓ . v_X-a\ge v_Y-a,\qquad(v_X-a)+(v_Y-a)=\ell-(a-b)\le\ell. v X − a ≥ v Y − a , ( v X − a ) + ( v Y − a ) = ℓ − ( a − b ) ≤ ℓ .
The first index is therefore at least as close to ℓ / 2 \ell/2 ℓ /2 as the second. Binomial coefficients increase toward the middle and have equal values at reflected indices, so the first coefficient is at least the second. Adding these comparisons proves (C.1).
Next compare the payoffs. Put
D ( v ) = u ( W ( v + e X ) ) − u ( W ( v + e Y ) ) . D(v)=u(W(v+e_X))-u(W(v+e_Y)). D ( v ) = u ( W ( v + e X )) − u ( W ( v + e Y )) .
For v X ≥ v Y v_X\ge v_Y v X ≥ v Y , all nonzero possibilities are listed below:
Table C.2.
Any omitted entry is zero. In every row, D ( v ) ≥ 0 D(v)\ge0 D ( v ) ≥ 0 and D ( v ) + D ( σ v ) ≥ 0 D(v)+D(\sigma v)\ge0 D ( v ) + D ( σ v ) ≥ 0 . For v X > v Y v_X>v_Y v X > v Y , the combined contribution of v v v and σ v \sigma v σ v is therefore
P q ( v ) D ( v ) + P q ( σ v ) D ( σ v ) = [ P q ( v ) − P q ( σ v ) ] D ( v ) + P q ( σ v ) [ D ( v ) + D ( σ v ) ] ≥ 0. \begin{aligned}
P_q(v)D(v)+P_q(\sigma v)D(\sigma v)
&=[P_q(v)-P_q(\sigma v)]D(v)\\
&\quad+P_q(\sigma v)[D(v)+D(\sigma v)]\ge0.
\end{aligned} P q ( v ) D ( v ) + P q ( σ v ) D ( σ v ) = [ P q ( v ) − P q ( σ v )] D ( v ) + P q ( σ v ) [ D ( v ) + D ( σ v )] ≥ 0.
using (C.1). When v X = v Y v_X=v_Y v X = v Y , the vector is counted once and its contribution is also nonnegative.
Finally, at least one contribution is strictly positive. If ∣ q ∣ = 2 r |q|=2r ∣ q ∣ = 2 r , take v = ( r , r , 0 ) v=(r,r,0) v = ( r , r , 0 ) ; if ∣ q ∣ = 2 r + 1 |q|=2r+1 ∣ q ∣ = 2 r + 1 , take v = ( r , r , 1 ) v=(r,r,1) v = ( r , r , 1 ) , in ( X , Y , Z ) (X,Y,Z) ( X , Y , Z ) -coordinates. In both cases, (C.2) gives D ( v ) > 0 D(v)>0 D ( v ) > 0 , and full support gives P q ( v ) > 0 P_q(v)>0 P q ( v ) > 0 . Thus U p ( X ∣ q ) > U p ( Y ∣ q ) . U^p(X\mid q)>U^p(Y\mid q). U p ( X ∣ q ) > U p ( Y ∣ q ) . □
Lemma C.3. A top response X X X is impossible if
q Z ≥ q Y ≥ q X + 2 or min { q Y , q Z } ≥ q X + 3. q_Z\ge q_Y\ge q_X+2\qquad\text{or}\qquad\min\{q_Y,q_Z\}\ge q_X+3. q Z ≥ q Y ≥ q X + 2 or min { q Y , q Z } ≥ q X + 3.
Proof. We record two elementary ways in which a proposed top response can fail. If v X + 1 < max { v Y , v Z } v_X+1<\max\{v_Y,v_Z\} v X + 1 < max { v Y , v Z } , adding X X X cannot make X X X a winner. The comparison between ballots X X X and Y Y Y is then
Table C.3.
Put
η = { ⌊ ( q Z − q Y ) / 2 ⌋ , q Z ≥ q Y , ⌊ ( q Y − q Z ) / 2 ⌋ , q Y > q Z , \eta=
\begin{cases}
\lfloor(q_Z-q_Y)/2\rfloor, & q_Z\ge q_Y,\\
\lfloor(q_Y-q_Z)/2\rfloor, & q_Y>q_Z,
\end{cases} η = { ⌊( q Z − q Y ) /2 ⌋ , ⌊( q Y − q Z ) /2 ⌋ , q Z ≥ q Y , q Y > q Z ,
and let c = Z c=Z c = Z in the first case and c = Y c=Y c = Y in the second. If
q c − q X ≥ 2 η + 2 , q_c-q_X\ge2\eta+2, q c − q X ≥ 2 η + 2 ,
then after at most η \eta η trembles the score of c c c remains at least two above that of X X X , so adding X X X cannot put X X X in the winner set. With fewer than η \eta η trembles, adding Y Y Y cannot alter the winner set either, by the choice of η \eta η . With exactly η \eta η trembles, (C.3) weakly favors Y Y Y for every flow and strictly favors it for the flow that moves η \eta η ballots from the higher of Y , Z Y,Z Y , Z to the lower. Hence Y Y Y asymptotically strictly beats X X X . Applying (C.4), and also observing that a Y Y Y –Z Z Z tie favors Y Y Y already at order zero, proves the statement once its two hypotheses are checked. If q Z ≥ q Y ≥ q X + 2 q_Z \ge q_Y \ge q_X + 2 q Z ≥ q Y ≥ q X + 2 , then q Z − q X ≥ ( q Z − q Y ) + 2 ≥ 2 ⌊ ( q Z − q Y ) / 2 ⌋ + 2 q_Z - q_X \ge(q_Z - q_Y) + 2 \ge2\lfloor(q_Z - q_Y)/2\rfloor+ 2 q Z − q X ≥ ( q Z − q Y ) + 2 ≥ 2 ⌊( q Z − q Y ) /2 ⌋ + 2 . Under the second hypothesis, if q Y > q Z q_Y > q_Z q Y > q Z and g = q Y − q Z g = q_Y - q_Z g = q Y − q Z , then q Y − q X ≥ g + 3 ≥ 2 ⌈ g / 2 ⌉ + 2 q_Y - q_X \ge g + 3 \ge2\lceil g/2\rceil+ 2 q Y − q X ≥ g + 3 ≥ 2 ⌈ g /2 ⌉ + 2 . If q Z ≥ q Y q_Z \ge q_Y q Z ≥ q Y , then instead q Z − q X ≥ ( q Z − q Y ) + 3 ≥ 2 ⌊ ( q Z − q Y ) / 2 ⌋ + 2 q_Z - q_X \ge(q_Z - q_Y) + 3 \ge2\lfloor(q_Z - q_Y)/2\rfloor+ 2 q Z − q X ≥ ( q Z − q Y ) + 3 ≥ 2 ⌊( q Z − q Y ) /2 ⌋ + 2 . □
For the remaining comparisons, we keep ρ \rho ρ as a variable when calculating the coefficients of U P ( X ∣ q ) − U P ( Y ∣ q ) U^P(X \mid q) - U^P(Y \mid q) U P ( X ∣ q ) − U P ( Y ∣ q ) . For each private vector considered below, these calculations give a threshold θ ( q ) ∈ [ 0 , 1 ] \theta(q) \in[0, 1] θ ( q ) ∈ [ 0 , 1 ] : ballot X X X strictly beats Y Y Y for sufficiently small positive p p p when ρ < θ ( q ) \rho< \theta(q) ρ < θ ( q ) , while Y Y Y strictly beats X X X when ρ > θ ( q ) \rho> \theta(q) ρ > θ ( q ) . The threshold is read directly from the first coefficient that is not the zero expression. If this coefficient has a zero in ( 0 , 1 ) (0, 1) ( 0 , 1 ) , that zero is the threshold. A threshold of zero means that Y Y Y beats X X X for every ρ ∈ ( 0 , 1 ) \rho\in(0, 1) ρ ∈ ( 0 , 1 ) ; a threshold of one means that X X X beats Y Y Y . At ρ = θ ( q ) \rho= \theta(q) ρ = θ ( q ) , later coefficients may decide the comparison. Thus a strict top response requires ρ ≤ θ ( q ) \rho\le\theta(q) ρ ≤ θ ( q ) , and a strict middle response requires ρ ≥ θ ( q ) \rho\ge\theta(q) ρ ≥ θ ( q ) .
Condition (C.4) gives threshold zero. At the first contributing tremble order, ballot X X X still cannot make X X X a winner, whereas ballot Y Y Y can replace a unique Z Z Z -winner by a Y Y Y –Z Z Z tie, or replace that tie by a unique Y Y Y -winner. By (C.3), the leading X − Y X-Y X − Y coefficient is therefore a positive multiple of − ρ -\rho − ρ , so θ ( q ) = 0 \theta(q) = 0 θ ( q ) = 0 .
For threshold one, suppose q Y > q X q_Y > q_X q Y > q X and either q X > q Z q_X > q_Z q X > q Z or q X = q Z q_X = q_Z q X = q Z with q Y − q X q_Y - q_X q Y − q X odd. Put η = ⌊ ( q Y − q X ) / 2 ⌋ \eta= \lfloor(q_Y - q_X)/2\rfloor η = ⌊( q Y − q X ) /2 ⌋ . After at most η \eta η trembles,
v Y − v Z ≥ q Y − q Z − 2 η ≥ 1. v_Y-v_Z \ge q_Y-q_Z-2\eta\ge1. v Y − v Z ≥ q Y − q Z − 2 η ≥ 1.
Thus Z Z Z cannot win under either contemplated ballot. With fewer than η \eta η trembles, Y Y Y also remains at least two above X X X , so both ballots leave Y Y Y as the unique winner. At order η \eta η , every payoff difference is a nonnegative multiple of 1 − ρ 1-\rho 1 − ρ , and the flow η ( Y ↦ X ) \eta(Y \mapsto X) η ( Y ↦ X ) gives a strictly positive contribution. The leading coefficient is therefore a positive multiple of 1 − ρ 1-\rho 1 − ρ , giving θ ( q ) = 1 \theta(q) = 1 θ ( q ) = 1 .
We now calculate the remaining thresholds. All private vectors below use ( X , Y , Z ) (X,Y,Z) ( X , Y , Z ) -coordinates. One tremble changes the two gaps as follows:
(C.5)
Each tremble reduces either lead of Y Y Y by at most two. For each row below, before the stated order Y Y Y remains the unique winner under both contemplated ballots, so every earlier coefficient vanishes. At the stated order, the gap changes in (C.5) give exactly the contributing flows listed below. Summing their multiplicities and payoff differences using Lemma A.1 gives the displayed coefficients. Each coefficient is shown up to a strictly positive factor independent of ρ \rho ρ .
Here h ∈ N 0 h \in\mathbb{N}_0 h ∈ N 0 . The first three rows have k ≥ 2 k \ge2 k ≥ 2 , and the fourth has k ≥ 1 k \ge1 k ≥ 1 .
Table C.6.
The contributing flows for these four rows are, respectively:
k ( Y ↦ Z ) k(Y \mapsto Z) k ( Y ↦ Z ) , ( k − 1 ) ( Y ↦ Z ) + ( X ↦ X ) (k-1)(Y \mapsto Z)+(X \mapsto X) ( k − 1 ) ( Y ↦ Z ) + ( X ↦ X ) , k ( Y ↦ X ) k(Y \mapsto X) k ( Y ↦ X ) , ( k − 1 ) ( Y ↦ Z ) + ( X ↦ Z ) (k-1)(Y \mapsto Z)+(X \mapsto Z) ( k − 1 ) ( Y ↦ Z ) + ( X ↦ Z ) .
( k + 1 ) ( Y ↦ Z ) (k+1)(Y \mapsto Z) ( k + 1 ) ( Y ↦ Z ) , k ( Y ↦ Z ) + ( Y ↦ X ) k(Y \mapsto Z)+(Y \mapsto X) k ( Y ↦ Z ) + ( Y ↦ X ) , k ( Y ↦ X ) + ( Z ↦ X ) k(Y \mapsto X)+(Z \mapsto X) k ( Y ↦ X ) + ( Z ↦ X ) , ( k + 1 ) ( Y ↦ X ) (k+1)(Y \mapsto X) ( k + 1 ) ( Y ↦ X ) , k ( Y ↦ Z ) + ( X ↦ Z ) k(Y \mapsto Z)+(X \mapsto Z) k ( Y ↦ Z ) + ( X ↦ Z ) , ( k + 1 ) ( Y ↦ X ) (k+1)(Y \mapsto X) ( k + 1 ) ( Y ↦ X ) , k ( Y ↦ Z ) + ( X ↦ Z ) k(Y \mapsto Z)+(X \mapsto Z) k ( Y ↦ Z ) + ( X ↦ Z ) .
k ( Y ↦ Z ) k(Y \mapsto Z) k ( Y ↦ Z ) , ( k − 1 ) ( Y ↦ X ) + ( Z ↦ X ) (k-1)(Y \mapsto X)+(Z \mapsto X) ( k − 1 ) ( Y ↦ X ) + ( Z ↦ X ) , ( k − 1 ) ( Y ↦ X ) + ( Y ↦ Z ) (k-1)(Y \mapsto X)+(Y \mapsto Z) ( k − 1 ) ( Y ↦ X ) + ( Y ↦ Z ) , k ( Y ↦ X ) k(Y \mapsto X) k ( Y ↦ X ) .
( k − 1 ) ( Y ↦ Z ) (k-1)(Y \mapsto Z) ( k − 1 ) ( Y ↦ Z ) , k − 1 ( Y ↦ X ) k-1(Y \mapsto X) k − 1 ( Y ↦ X ) .
A flow requiring a ballot from a candidate with zero support is omitted. In the fourth row with k = 1 k=1 k = 1 , both listed expressions describe the same empty flow, which is counted once; its margin is ( 1 − 2 ρ ) / 3 (1-2\rho)/3 ( 1 − 2 ρ ) /3 .
To illustrate the calculation, the four flows in the first row have multiplicities
( h + 2 k + 1 k ) , k ( h + 2 k + 1 k ) , ( h + 2 k + 1 k ) , h ( h + 2 k + 1 k − 1 ) , \binom{h+2k+1}{k}, \qquad k\binom{h+2k+1}{k}, \qquad\binom{h+2k+1}{k}, \qquad h\binom{h+2k+1}{k-1}, ( k h + 2 k + 1 ) , k ( k h + 2 k + 1 ) , ( k h + 2 k + 1 ) , h ( k − 1 h + 2 k + 1 ) ,
and respective payoff differences
− ρ 2 , − ρ 2 , 1 − ρ 2 , − ρ 2 . -\frac{\rho}{2}, \qquad-\frac{\rho}{2}, \qquad\frac{1-\rho}{2}, \qquad-\frac{\rho}{2}. − 2 ρ , − 2 ρ , 2 1 − ρ , − 2 ρ .
Multiplying by the common probability factor 2 − k 2^{-k} 2 − k and adding gives the leading coefficient
( h + 2 k + 1 k ) 2 k + 1 ( h + k + 2 ) [ ( h + k + 2 ) − [ 2 ( k + 1 ) h + ( k + 2 ) 2 ] ρ ] , \frac{\binom{h+2k+1}{k}}{2^{k+1}(h+k+2)}
\left[(h+k+2)-[2(k+1)h+(k+2)^2]\rho\right], 2 k + 1 ( h + k + 2 ) ( k h + 2 k + 1 ) [ ( h + k + 2 ) − [ 2 ( k + 1 ) h + ( k + 2 ) 2 ] ρ ] ,
which is the first row of (C.6) with its positive factor restored.
For k = 1 k=1 k = 1 , the first three rows must be calculated separately because some terminal vectors give three-way ties. The coefficients, again up to positive factors independent of ρ \rho ρ , are
Table C.7.
The contributing flows in these three rows are:
Y ↦ Z Y \mapsto Z Y ↦ Z , Y ↦ X Y \mapsto X Y ↦ X , X ↦ Z X \mapsto Z X ↦ Z .
2 ( Y ↦ Z ) 2(Y \mapsto Z) 2 ( Y ↦ Z ) , ( Y ↦ X ) + ( Z ↦ X ) (Y \mapsto X)+(Z \mapsto X) ( Y ↦ X ) + ( Z ↦ X ) , ( Y ↦ X ) + ( Y ↦ Z ) (Y \mapsto X)+(Y \mapsto Z) ( Y ↦ X ) + ( Y ↦ Z ) , 2 ( Y ↦ X ) 2(Y \mapsto X) 2 ( Y ↦ X ) , ( X ↦ Z ) + ( Y ↦ Z ) (X \mapsto Z)+(Y \mapsto Z) ( X ↦ Z ) + ( Y ↦ Z ) .
Z ↦ X Z \mapsto X Z ↦ X , Y ↦ Z Y \mapsto Z Y ↦ Z , Y ↦ X Y \mapsto X Y ↦ X .
The first three rows of (C.6), using (C.7) when k = 1 k=1 k = 1 , therefore give
Table C.8.
These bounds can be checked by substituting ρ = 1 / 2 \rho=1/2 ρ = 1/2 and ρ = 2 / 3 \rho=2/3 ρ = 2/3 into the displayed coefficients. For k ≥ 2 k \ge2 k ≥ 2 , the first coefficient at 1 / 2 1/2 1/2 is
− k ( 2 h + k + 2 ) 2 < 0. -\frac{k(2h+k+2)}{2}<0. − 2 k ( 2 h + k + 2 ) < 0.
The second coefficient is positive at 1 / 2 1/2 1/2 and negative at 2 / 3 2/3 2/3 , with values
h + 2 k + 3 2 > 0 , − ( k + 1 ) ( 2 h + k + 1 ) 3 < 0. \frac{h+2k+3}{2}>0, \qquad-\frac{(k+1)(2h+k+1)}{3}<0. 2 h + 2 k + 3 > 0 , − 3 ( k + 1 ) ( 2 h + k + 1 ) < 0.
The third coefficient at 2 / 3 2/3 2/3 is
k ( 2 h + k + 3 ) 3 > 0. \frac{k(2h+k+3)}{3}>0. 3 k ( 2 h + k + 3 ) > 0.
For k = 1 k=1 k = 1 , the corresponding values are
− 6 h + 9 2 , 3 h + 15 2 , − 10 h + 6 3 , 7 h + 15 3 , -\frac{6h+9}{2}, \qquad\frac{3h+15}{2}, \qquad-\frac{10h+6}{3}, \qquad\frac{7h+15}{3}, − 2 6 h + 9 , 2 3 h + 15 , − 3 10 h + 6 , 3 7 h + 15 ,
with the same respective signs. Every displayed coefficient decreases as ρ \rho ρ increases, proving (C.8).
Lemma C.4. Let c ∈ { Y , Z } c \in\{Y,Z\} c ∈ { Y , Z } and q c ≥ 1 q_c \ge1 q c ≥ 1 . With q ′ = q + e X − e c q'=q+e_X-e_c q ′ = q + e X − e c , it is impossible that
BR ( q ) = X , BR ( q ′ ) = Y . \operatorname{BR}(q)=X,\qquad\operatorname{BR}(q')=Y. BR ( q ) = X , BR ( q ′ ) = Y .
Proof. The middle response and Lemma C.2 imply q Y ′ > q X ′ q'_Y>q'_X q Y ′ > q X ′ . Put q = ( h , h + g , h + δ ) q=(h,h+g,h+\delta) q = ( h , h + g , h + δ ) . If c = Z c=Z c = Z , then g ≥ 2 g\ge2 g ≥ 2 and
(C.9)
If c = Y c=Y c = Y , then g ≥ 3 g\ge3 g ≥ 3 and
(C.10)
For a zero entry with δ ≥ 3 \delta\ge3 δ ≥ 3 , one of the two score conditions in Lemma C.3 holds and hence so does (C.4). For a zero entry with δ = 2 \delta=2 δ = 2 and even g g g , condition (C.4) holds with η = ( g − 2 ) / 2 \eta=(g-2)/2 η = ( g − 2 ) /2 . Every one entry has q X ′ > q Z ′ q'_X>q'_Z q X ′ > q Z ′ , or q X ′ = q Z ′ q'_X=q'_Z q X ′ = q Z ′ with an odd q Y ′ − q X ′ q'_Y-q'_X q Y ′ − q X ′ , so the preceding comparison applies. The remaining bounds follow from (C.6)–(C.8). The cases are disjoint and exhaustive. If θ ( q ) = 0 \theta(q)=0 θ ( q ) = 0 , the top response at q q q is impossible because ρ > 0 \rho>0 ρ > 0 . If θ ( q ′ ) = 1 \theta(q')=1 θ ( q ′ ) = 1 , the middle response at q ′ q' q ′ is impossible because ρ < 1 \rho<1 ρ < 1 . In every remaining row, θ ( q ) < θ ( q ′ ) \theta(q)<\theta(q') θ ( q ) < θ ( q ′ ) . A top response at q q q would require ρ ≤ θ ( q ) \rho\le\theta(q) ρ ≤ θ ( q ) , while a middle response at q ′ q' q ′ would require ρ ≥ θ ( q ′ ) \rho\ge\theta(q') ρ ≥ θ ( q ′ ) , which is impossible even if a leading coefficient vanishes at one of the thresholds. □
We require one final comparison. The only new leading coefficients are those at, for h ∈ N 0 h\in\mathbb{N}_0 h ∈ N 0 ,
( h , h + 2 j + 1 , h + 1 ) , ( h , h + 2 j + 2 , h ) . (h,h+2j+1,h+1),\qquad(h,h+2j+2,h). ( h , h + 2 j + 1 , h + 1 ) , ( h , h + 2 j + 2 , h ) .
Their thresholds are respectively 1 / 2 1/2 1/2 and
11 h + 16 13 h + 20 ( j = 0 ) , 2 ( j + 2 ) h + ( j + 2 ) ( j + 3 ) ( 2 j + 5 ) h + ( j + 2 ) ( j + 4 ) ( j ≥ 1 ) . \frac{11h+16}{13h+20}\quad(j=0),\qquad
\frac{2(j+2)h+(j+2)(j+3)}{(2j+5)h+(j+2)(j+4)}\quad(j\ge1). 13 h + 20 11 h + 16 ( j = 0 ) , ( 2 j + 5 ) h + ( j + 2 ) ( j + 4 ) 2 ( j + 2 ) h + ( j + 2 ) ( j + 3 ) ( j ≥ 1 ) .
(C.11)
For the first vector, when j ≥ 1 j\ge1 j ≥ 1 , the complete first contributing order consists of j ( Y Z ) j(YZ) j ( Y Z ) and j ( Y X ) j(YX) j ( Y X ) ; for j = 0 j=0 j = 0 , the order-zero coefficient is ( 1 − 2 ρ ) / 3 (1-2\rho)/3 ( 1 − 2 ρ ) /3 . For the second it consists, when j ≥ 1 j\ge1 j ≥ 1 , of ( j + 1 ) ( Y Z ) (j+1)(YZ) ( j + 1 ) ( Y Z ) , j ( Y X ) + Z X j(YX)+ZX j ( Y X ) + Z X , j ( Y X ) + Y Z j(YX)+YZ j ( Y X ) + Y Z , and ( j + 1 ) ( Y X ) (j+1)(YX) ( j + 1 ) ( Y X ) ; when j = 0 j=0 j = 0 it consists of Y X YX Y X , Y Z YZ Y Z , Z X ZX Z X . The flow formula gives (C.11). Subtracting 1 / 2 1/2 1/2 has positive numerator 9 h + 12 9h+12 9 h + 12 for j = 0 j=0 j = 0 and ( 2 j + 3 ) h + ( j + 2 ) 2 (2j+3)h+(j+2)^2 ( 2 j + 3 ) h + ( j + 2 ) 2 for j ≥ 1 j\ge1 j ≥ 1 .
Lemma C.5. If q Y ≥ max { q X , q Z } q_Y\ge\max\{q_X,q_Z\} q Y ≥ max { q X , q Z } and q Z ≥ 1 q_Z\ge1 q Z ≥ 1 , it is impossible that
BR ( q ) = X , BR ( q + e Y − e Z ) = Y . \operatorname{BR}(q)=X,\qquad\operatorname{BR}(q+e_Y-e_Z)=Y. BR ( q ) = X , BR ( q + e Y − e Z ) = Y .
Proof. Put q = ( h , h + g , h + δ ) q=(h,h+g,h+\delta) q = ( h , h + g , h + δ ) and q ′ = q + e Y − e Z q'=q+e_Y-e_Z q ′ = q + e Y − e Z . The hypotheses give g ≥ max { 0 , δ } g\ge\max\{0,\delta\} g ≥ max { 0 , δ } and h + δ ≥ 1 h+\delta\ge1 h + δ ≥ 1 . The preceding calculations give
(C.12)
When δ = 2 \delta=2 δ = 2 and g = 2 k + 1 g=2k+1 g = 2 k + 1 , we have k ≥ 1 k\ge1 k ≥ 1 and the thresholds are the first and second rows of (C.8). When δ = 1 \delta=1 δ = 1 and g g g is odd, (C.11) applies, including its separate g = 1 g=1 g = 1 value. For δ ≥ 3 \delta\ge3 δ ≥ 3 , both Y , Z Y,Z Y , Z are at least three above X X X , giving threshold zero. For δ = 2 \delta=2 δ = 2 and even g g g , condition (C.4) gives threshold zero at q q q , and the first family preceding (C.11) gives threshold 1 / 2 1/2 1/2 at q ′ q' q ′ . Each threshold-one entry has q X ′ > q Z ′ q'_X>q'_Z q X ′ > q Z ′ , or q X ′ = q Z ′ q'_X=q'_Z q X ′ = q Z ′ with an odd q Y ′ − q X ′ q'_Y-q'_X q Y ′ − q X ′ .
If θ ( q ) = 0 \theta(q)=0 θ ( q ) = 0 , the top response is impossible because ρ > 0 \rho>0 ρ > 0 . If θ ( q ′ ) = 1 \theta(q')=1 θ ( q ′ ) = 1 , the middle response is impossible because ρ < 1 \rho<1 ρ < 1 . Otherwise θ ( q ) ≤ 1 / 2 < θ ( q ′ ) \theta(q)\le1/2<\theta(q') θ ( q ) ≤ 1/2 < θ ( q ′ ) , whereas the prescribed responses require ρ ≤ θ ( q ) \rho\le\theta(q) ρ ≤ θ ( q ) and ρ ≥ θ ( q ′ ) \rho\ge\theta(q') ρ ≥ θ ( q ′ ) . This is impossible. In particular, the zero-count boundary q = ( 0 , 1 , 1 ) q=(0,1,1) q = ( 0 , 1 , 1 ) is included: (C.11) gives thresholds 1 / 2 1/2 1/2 and 4 / 5 4/5 4/5 . □
Excluding the Two Stay Patterns
Now we turn to the remaining stay patterns and show that also they indeed cannot happen.
Proof. Suppose a period-three cycle has at most three active voters. Lemma C.1 excludes fewer than three and leaves only the stay patterns ( 1 , 1 , 1 ) (1,1,1) ( 1 , 1 , 1 ) and ( 2 , 1 , 0 ) (2,1,0) ( 2 , 1 , 0 ) . These numbers count the active voters who keep their ballots in each of the three transitions.
Let z = ( z A , z B , z C ) z=(z_A,z_B,z_C) z = ( z A , z B , z C ) be the fixed counts of the inactive voters. Write s i s_i s i for the candidate voter i i i supports twice and o i o_i o i for the candidate she supports once. These are her favorite and middle candidate, in some order. Each table entry lists the other two active ballots and the required next ballot. For example, { A , B } → C \{A,B\}\to C { A , B } → C means that the voter must respond with C C C to the private vector z + e A + e B z+e_A+e_B z + e A + e B . All braces denote multisets, and column t t t gives the response from time t t t to time t + 1 t+1 t + 1 , with time read modulo three.
Consider first the stay pattern ( 1 , 1 , 1 ) (1,1,1) ( 1 , 1 , 1 ) . Label the voters so that voters 1, 2, 3 stay in transitions 0, 1, 2, respectively. Their ballot paths are
( s 1 , s 1 , o 1 ) , ( o 2 , s 2 , s 2 ) , ( s 3 , o 3 , s 3 ) . (s_1,s_1,o_1),\qquad(o_2,s_2,s_2),\qquad(s_3,o_3,s_3). ( s 1 , s 1 , o 1 ) , ( o 2 , s 2 , s 2 ) , ( s 3 , o 3 , s 3 ) .
The required responses are
(C.13)
The pairs ( s i , o i ) (s_i,o_i) ( s i , o i ) must be distinct. If ( s 2 , o 2 ) = ( s 3 , o 3 ) (s_2,o_2)=(s_3,o_3) ( s 2 , o 2 ) = ( s 3 , o 3 ) , the first two entries of voter 1’s row have identical other ballots but different required responses. Equality of the pairs of voters 1, 3 or 1, 2 gives the same contradiction for voter 2 or 3.
The exhaustive reduction in Subsection C.4 applies Lemma C.4 to these responses. After relabeling candidates, it leaves only
In the first case, the middle responses of voters 1, 2, 3 face { C , C } \{C,C\} { C , C } , { A , A } \{A,A\} { A , A } , and { B , B } \{B,B\} { B , B } , respectively. Lemma C.2 therefore requires
z A > z B , z B > z C , z C > z A . z_A > z_B,\qquad z_B > z_C,\qquad z_C > z_A. z A > z B , z B > z C , z C > z A .
which is impossible. In the second case, their middle responses face { C , C } \{C,C\} { C , C } , { B , B } \{B,B\} { B , B } , and { A , A } \{A,A\} { A , A } , giving
z B > z A , z A > z C , z C > z B . z_B > z_A,\qquad z_A > z_C,\qquad z_C > z_B. z B > z A , z A > z C , z C > z B .
This is also impossible, excluding ( 1 , 1 , 1 ) (1,1,1) ( 1 , 1 , 1 ) .
It remains to consider ( 2 , 1 , 0 ) (2,1,0) ( 2 , 1 , 0 ) . Label the voters so that voters 1, 2 stay in transition 0 and voter 3 stays in transition 1. Their paths are
( s 1 , s 1 , o 1 ) , ( s 2 , s 2 , o 2 ) , ( o 3 , s 3 , s 3 ) , (s_1,s_1,o_1),\qquad(s_2,s_2,o_2),\qquad(o_3,s_3,s_3), ( s 1 , s 1 , o 1 ) , ( s 2 , s 2 , o 2 ) , ( o 3 , s 3 , s 3 ) ,
and their required responses are
Table C.14.
Suppose s 1 s_1 s 1 is the favorite. If s 1 = s 3 s_1=s_3 s 1 = s 3 , changing the other ballot o 3 o_3 o 3 to s 3 s_3 s 3 takes voter 1 from a favorite response in column 0 to a middle response in column 1. If s 1 = s 2 s_1=s_2 s 1 = s 2 , changing o 2 o_2 o 2 to s 2 s_2 s 2 gives the same forbidden comparison from column 2 to column 1. Lemma C.4 excludes both possibilities. If s 1 s_1 s 1 is the middle candidate, the reverse comparisons give the corresponding restrictions on o 1 o_1 o 1 . Thus
s 1 favorite ⟹ s 1 ∉ { s 2 , s 3 } , s_1\text{ favorite}\implies s_1\notin\{s_2,s_3\}, s 1 favorite ⟹ s 1 ∈ / { s 2 , s 3 } ,
s 1 middle ⟹ o 1 ∉ { o 2 , o 3 } . s_1\text{ middle}\implies o_1\notin\{o_2,o_3\}. s 1 middle ⟹ o 1 ∈ / { o 2 , o 3 } .
The same restrictions hold with voters 1, 2 exchanged.
Voter 3 requires different responses to { s 1 , s 2 } \{s_1,s_2\} { s 1 , s 2 } and { o 1 , o 2 } \{o_1,o_2\} { o 1 , o 2 } , so these multisets must differ. If s 3 s_3 s 3 is her favorite, Lemma C.4 also forbids obtaining { o 1 , o 2 } \{o_1,o_2\} { o 1 , o 2 } from { s 1 , s 2 } \{s_1,s_2\} { s 1 , s 2 } by changing one ballot to s 3 s_3 s 3 . If s 3 s_3 s 3 is her middle candidate, it forbids the reverse change by moving one ballot to o 3 o_3 o 3 . In each comparison, the replaced ballot is present, so the lemma’s positive-source-count condition is satisfied.
Finally, every prescribed middle response requires q Y ≥ q X + 1 q_Y\ge q_X+1 q Y ≥ q X + 1 by Lemma C.2. Applying this inequality to the private counts in (C.14) gives restrictions on z z z . Together, these conditions leave the following six cases, up to candidate relabeling and exchange of voters 1, 2. Subsection C.5 proves this reduction exhaustive. Candidate pairs and rankings are listed in voter order; for example, B A C BAC B A C means B ≻ A ≻ C B\succ A\succ C B ≻ A ≻ C .
Table C.15.
Four cases are excluded directly by Lemma C.3. The following entries of (C.14) require a favorite response. Private vectors are written in the focal voter’s ( X , Y , Z ) (X,Y,Z) ( X , Y , Z ) order.
Table 3.
The inequalities in (C.15) give q Z ≥ q Y ≥ q X + 2 q_Z\ge q_Y\ge q_X+2 q Z ≥ q Y ≥ q X + 2 in rows 1, 3, 4 and min { q Y , q Z } ≥ q X + 3 \min\{q_Y,q_Z\}\ge q_X+3 min { q Y , q Z } ≥ q X + 3 in row 5. In each case, the required favorite response is therefore impossible.
In row 2, voter 2 ranks C ≻ B ≻ A C\succ B\succ A C ≻ B ≻ A . Columns 0 and 1 of (C.14) require
{ A , A } ↦ C , { A , B } ↦ B . \{A,A\}\mapsto C,\qquad\{A,B\}\mapsto B. { A , A } ↦ C , { A , B } ↦ B .
The first private vector, in ( C , B , A ) (C,B,A) ( C , B , A ) order, is
q = ( z C , z B , z A + 2 ) . q=(z_C,z_B,z_A+2). q = ( z C , z B , z A + 2 ) .
The inequalities in (C.15) give q Y ≥ max { q X , q Z } q_Y\ge\max\{q_X,q_Z\} q Y ≥ max { q X , q Z } and q Z = z A + 2 > 0 q_Z=z_A+2>0 q Z = z A + 2 > 0 . Changing one other ballot from A to B increases the middle score and decreases the bottom score. The required change from the favorite response C to the middle response B contradicts Lemma C.5 .
In row 6, voter 2 ranks C ≻ A ≻ B C\succ A\succ B C ≻ A ≻ B . Columns 1 and 0 require
{ A , B } ↦ C , { A , A } ↦ A . \{A,B\}\mapsto C,\qquad\{A,A\}\mapsto A. { A , B } ↦ C , { A , A } ↦ A .
The first private vector, in ( C , A , B ) (C,A,B) ( C , A , B ) order, is
q = ( z C , z A + 1 , z B + 1 ) . q=(z_C,z_A+1,z_B+1). q = ( z C , z A + 1 , z B + 1 ) .
Again, (C.15) gives q Y ≥ max { q X , q Z } q_Y\ge\max\{q_X,q_Z\} q Y ≥ max { q X , q Z } and q Z = z B + 1 > 0 q_Z=z_B+1>0 q Z = z B + 1 > 0 . Changing one other ballot from B to A contradicts the same lemma.
Thus all six cases are impossible, excluding ( 2 , 1 , 0 ) (2,1,0) ( 2 , 1 , 0 ) . Neither three-active stay pattern can occur, and Lemma C.1 already excludes fewer active voters. Every period-three cycle therefore has at least four active voters. We remark that no restriction was placed on the inactive counts z z z .
We now verify that the proof covers all possible choice of candidate pairs and rankings: first for the stay pattern ( 1 , 1 , 1 ) (1,1,1) ( 1 , 1 , 1 ) , then for ( 2 , 1 , 0 ) (2,1,0) ( 2 , 1 , 0 ) .
The (1,1,1) Reduction
Use the paths and required responses in (C.13). For size-two multisets, P → c Q P\xrightarrow{c}Q P c Q means that Q Q Q is obtained from P P P by replacing one ballot not equal to c c c by a ballot for c c c . This arrow describes a change of another voter’s ballot, not the focal voter’s response. The comparison need not follow the chronological order of the trajectory. If s i s_i s i is the favorite, Lemma C.4 forbids a change toward s i s_i s i from a multiset prescribing s i s_i s i to one prescribing o i o_i o i . If s i s_i s i is the middle candidate, it forbids a change toward o i o_i o i from a multiset prescribing o i o_i o i to one prescribing s i s_i s i . The replaced ballot is present in the source multiset, as the lemma requires. Relabel candidates so that ( s 1 , o 1 ) = ( A , B ) (s_1,o_1)=(A,B) ( s 1 , o 1 ) = ( A , B ) . Since the three ordered pairs are distinct, there are five choices for ( s 2 , o 2 ) (s_2,o_2) ( s 2 , o 2 ) and then four for ( s 3 , o 3 ) (s_3,o_3) ( s 3 , o 3 ) . Cyclically rotating voters together with time, and then relabeling candidates to restore ( s 1 , o 1 ) = ( A , B ) (s_1,o_1)=(A,B) ( s 1 , o 1 ) = ( A , B ) , groups these 20 choices as follows. Every entry lists the ordered pairs ( ( s 2 , o 2 ) , ( s 3 , o 3 ) ) ((s_2,o_2),(s_3,o_3)) (( s 2 , o 2 ) , ( s 3 , o 3 )) ; braces will be reserved for multisets of ballots.
Table C.16.
The first six classes are excluded by the following comparisons in their representatives. In each row, the first change is forbidden if s i s_i s i is the favorite and the second if s i s_i s i is the middle candidate. The required responses are those in (C.13).
Table 4.
For example, in class 1, voter 1 must respond with A A A to { A , B } \{A,B\} { A , B } and with B B B to { A , A } \{A,A\} { A , A } . If A A A is her favorite, replacing the other ballot B B B by A A A gives a forbidden favorite-to-middle response change. If B B B is her favorite, the reverse comparison gives the same contradiction. Thus neither ranking is possible. The remaining five rows work in the same way.
In class 7, the pairs are ( ( A , B ) , ( B , C ) , ( C , A ) ) ((A,B),(B,C),(C,A)) (( A , B ) , ( B , C ) , ( C , A )) . If any repeated candidate is the corresponding voter’s favorite, the forbidden changes for voters 1, 2, 3 are, respectively, { B , C } ⟶ A { A , B } \{B,C\}\mathrel{\mathop{\longrightarrow}^{A}}\{A,B\} { B , C } ⟶ A { A , B } , { A , C } ⟶ B { B , C } \{A,C\}\mathrel{\mathop{\longrightarrow}^{B}}\{B,C\} { A , C } ⟶ B { B , C } , and { A , B } ⟶ C { A , C } \{A,B\}\mathrel{\mathop{\longrightarrow}^{C}}\{A,C\} { A , B } ⟶ C { A , C } . Hence every s i s_i s i must be the middle candidate.
In class 8, the pairs are ( ( A , B ) , ( C , A ) , ( B , C ) ) ((A,B),(C,A),(B,C)) (( A , B ) , ( C , A ) , ( B , C )) . If any repeated candidate is the corresponding voter’s middle candidate, the forbidden changes for voters 1, 2, 3 are, respectively, { C , C } ⟶ B { B , C } \{C,C\}\mathrel{\mathop{\longrightarrow}^{B}}\{B,C\} { C , C } ⟶ B { B , C } , { B , B } ⟶ A { A , B } \{B,B\}\mathrel{\mathop{\longrightarrow}^{A}}\{A,B\} { B , B } ⟶ A { A , B } , and { A , A } ⟶ C { A , C } \{A,A\}\mathrel{\mathop{\longrightarrow}^{C}}\{A,C\} { A , A } ⟶ C { A , C } . Hence every s i s_i s i must be the favorite.
The first six classes contain three choices each, and the last two contain one each. All 20 choices therefore appear in (C.16), and the only possibilities not excluded by Lemma C.4 are the two used in the proof above.
Exhaustiveness of Table C.15
Use the paths and restrictions from (C.14) and retain the multiset-change notation above. If exactly one of s 1 , s 2 s_1,s_2 s 1 , s 2 is the favorite, exchange voters 1, 2 so that s 1 s_1 s 1 is the middle candidate and s 2 s_2 s 2 is the favorite. Then relabel candidates so that ( s 1 , o 1 ) = ( A , B ) (s_1,o_1)=(A,B) ( s 1 , o 1 ) = ( A , B ) . Every prescribed middle response gives an integer inequality through Lemma C.2.
Every choice not excluded below appears in the following ten rows. The second column lists the ordered pairs ( ( s 2 , o 2 ) , ( s 3 , o 3 ) ) ((s_2,o_2),(s_3,o_3)) (( s 2 , o 2 ) , ( s 3 , o 3 )) . The last three columns indicate whether each repeated candidate is the voter’s favorite or middle candidate.
Table C.17.
We check that no choice is missing. Suppose first that s 1 , s 2 s_1,s_2 s 1 , s 2 are both favorites. The restrictions on voters 1, 2 force { s 2 , s 3 } = { B , C } \{s_2,s_3\}=\{B,C\} { s 2 , s 3 } = { B , C } . If ( s 2 , s 3 ) = ( B , C ) (s_2,s_3)=(B,C) ( s 2 , s 3 ) = ( B , C ) , then o 2 = C o_2=C o 2 = C , since otherwise voter 3 would face identical private counts in columns 0 and 2 of (C.14), with different required responses. If s 3 s_3 s 3 is the favorite, voter 3 is excluded by { A , B } ⟶ C { B , C } \{A,B\}\mathrel{\mathop{\longrightarrow}^{C}}\{B,C\} { A , B } ⟶ C { B , C } . If s 3 s_3 s 3 is the middle candidate, the choice o 3 = A o_3=A o 3 = A is excluded by { B , C } ⟶ A { A , B } \{B,C\}\mathrel{\mathop{\longrightarrow}^{A}}\{A,B\} { B , C } ⟶ A { A , B } . Thus o 3 = B o_3=B o 3 = B , giving row 1.
If ( s 2 , s 3 ) = ( B , C ) (s_2,s_3)=(B,C) ( s 2 , s 3 ) = ( B , C ) , then o 2 ∈ { A , B } o_2\in\{A,B\} o 2 ∈ { A , B } and o 3 ∈ { A , C } o_3\in\{A,C\} o 3 ∈ { A , C } . If s 3 s_3 s 3 is the favorite, the four choices ( o 2 , o 3 ) = ( A , A ) , ( B , A ) , ( A , C ) , ( B , C ) (o_2,o_3)=(A,A),(B,A),(A,C),(B,C) ( o 2 , o 3 ) = ( A , A ) , ( B , A ) , ( A , C ) , ( B , C ) give, respectively,
Table 5.
The first three contradict z B ≥ z A z_B\ge z_A z B ≥ z A , which follows from voter 1’s middle response. The fourth itself is clearly impossible. If s 3 s_3 s 3 is the middle candidate, the choice ( o 2 , o 3 ) = ( A , C ) (o_2,o_3)=(A,C) ( o 2 , o 3 ) = ( A , C ) is excluded by { A , B } ⟶ C { A , C } \{A,B\}\mathrel{\mathop{\longrightarrow}^{C}}\{A,C\} { A , B } ⟶ C { A , C } for voter 3, leaving rows 2–4.
Suppose next that s 1 , s 2 s_1,s_2 s 1 , s 2 are both middle candidates. Their restrictions force { o 2 , o 3 } = { C , A } \{o_2,o_3\}=\{C,A\} { o 2 , o 3 } = { C , A } . If ( o 2 , o 3 ) = ( C , A ) (o_2,o_3)=(C,A) ( o 2 , o 3 ) = ( C , A ) and s 3 s_3 s 3 is the middle candidate, the four choices for ( s 2 , s 3 ) (s_2,s_3) ( s 2 , s 3 ) give
Table 6.
All four are impossible. If s 3 s_3 s 3 is the favorite, the choice ( s 2 , s 3 ) = ( B , C ) (s_2,s_3)=(B,C) ( s 2 , s 3 ) = ( B , C ) is excluded by { A , B } ⟶ C { B , C } \{A,B\}\mathrel{\mathop{\longrightarrow}^{C}}\{B,C\} { A , B } ⟶ C { B , C } for voter 3. The other choices give rows 5–7.
If ( o 2 , o 3 ) = ( A , C ) (o_2,o_3)=(A,C) ( o 2 , o 3 ) = ( A , C ) , then s 2 = C s_2=C s 2 = C , since choosing s 2 = B s_2=B s 2 = B would make voter 3 face identical private counts in columns 0 and 2 of (C.14), with different required responses. If s 3 s_3 s 3 is the middle candidate, the two choices s 3 = A s_3=A s 3 = A and s 3 = B s_3=B s 3 = B give, respectively,
Table 7.
Both are impossible. If s 3 s_3 s 3 is the favorite, the choice s 3 = B s_3=B s 3 = B is excluded by { A , C } ⟶ B { A , B } \{A,C\}\mathrel{\mathop{\longrightarrow}^{B}}\{A,B\} { A , C } ⟶ B { A , B } for voter 3. Only s 3 = A s_3=A s 3 = A remains, giving row 8.
Finally, suppose s 1 s_1 s 1 is the middle candidate and s 2 s_2 s 2 is the favorite. The restrictions give s 2 ∈ { B , C } s_2 \in\{B,C\} s 2 ∈ { B , C } . If s 2 = B s_2=B s 2 = B , then o 2 = C o_2=C o 2 = C , since choosing o 2 = B o_2=B o 2 = B would make voter 3 face identical private counts in columns 0 and 2 of (C.14), with different required responses, and the remaining restrictions give { s 3 , o 3 } = { A , C } \{s_3,o_3\}=\{A,C\} { s 3 , o 3 } = { A , C } . The choice ( s 3 , o 3 ) = ( C , A ) (s_3,o_3)=(C,A) ( s 3 , o 3 ) = ( C , A ) is excluded by { A , B } → { B , C } \{A,B\} \to\{B,C\} { A , B } → { B , C } when s 3 s_3 s 3 is the favorite and by { B , C } → A { A , B } \{B,C\} \mathrel{\mathop{\to}^{A}} \{A,B\} { B , C } → A { A , B } when it is the middle candidate. The other choice, ( s 3 , o 3 ) = ( A , C ) (s_3,o_3)=(A,C) ( s 3 , o 3 ) = ( A , C ) , gives rows 9 and 10.
If s 2 = C s_2=C s 2 = C , the restrictions force o 2 = A o_2=A o 2 = A and leave ( s 3 , o 3 ) ∈ { ( A , C ) , ( B , A ) , ( B , C ) } (s_3,o_3)\in\{(A,C),(B,A),(B,C)\} ( s 3 , o 3 ) ∈ {( A , C ) , ( B , A ) , ( B , C )} . Each possibility is excluded as follows. Every displayed ballot change concerns voter 3.
Table C.
This exhausts all choices and proves that every remaining case appears in (C.17).
The ten rows reduce to the six rows of (C.15) by the following relabelings. The first and last columns give the row numbers in (C.17) and (C.15), respectively. Perform any indicated exchange of voters before renaming candidates. Candidate renaming applies simultaneously to the candidate pairs, rankings, and inactive counts.
Table C.18.
Applying Lemma C.2 to the required middle responses gives the forced inactive gaps in (C.15). Thus every possible choice of paths and rankings is either excluded above or reduces to one of its six rows, whose contradictions were proved in the preceding subsection.
Proof of Theorem 5.3
We check that every ballot prescribed by Theorem 5.3 is a strict best response at its source profile. This includes voters who keep their ballot in a round, as well as those who switch it.
At sources S 0 S^0 S 0 , S 1 S^1 S 1 , S 2 S^2 S 2 , the polls are ( 2 , 2 , 2 ) (2,2,2) ( 2 , 2 , 2 ) , ( 1 , 1 , 4 ) (1,1,4) ( 1 , 1 , 4 ) , and ( 0 , 0 , 6 ) (0,0,6) ( 0 , 0 , 6 ) , respectively. For one representative of each symmetry class, the table compares the prescribed ballot with the other of her favorite and middle candidates. Private vectors use ( A , B , C ) (A,B,C) ( A , B , C ) coordinates. The side voters have utilities ( 1 , ρ , 0 ) (1,\rho,0) ( 1 , ρ , 0 ) in ranking order, where 9 / 11 < ρ < 1 9/11<\rho<1 9/11 < ρ < 1 ; the two C C C -types have utilities ( 1 , γ , 0 ) (1,\gamma,0) ( 1 , γ , 0 ) in ranking order, where 1 / 2 < γ < 1 1/2<\gamma<1 1/2 < γ < 1 . Every displayed coefficient is strictly positive throughout these intervals.
Table D.
The B B B -side comparisons follow by exchanging A A A and B B B . Lemma 4.3 makes the favorite ballot strictly better than the least-preferred ballot. A prescribed favorite therefore beats both alternatives, and a prescribed middle ballot that beats the favorite also beats the least-preferred ballot. The table establishes every voter’s unique response at all three profiles.
Proof of Example 5.4
We verify Example 5.4 with the normalized utilities and ballot paths in fig:1 . The complete profiles, in voter order, are
S 0 = ( A , A , B , B , C , C ) , S^0=(A,A,B,B,C,C), S 0 = ( A , A , B , B , C , C ) ,
S 1 = ( B , B , B , A , B , C ) , S^1=(B,B,B,A,B,C), S 1 = ( B , B , B , A , B , C ) ,
S 2 = ( A , A , B , B , C , A ) , S^2=(A,A,B,B,C,A), S 2 = ( A , A , B , B , C , A ) ,
S 3 = ( A , A , B , A , B , C ) , S 4 = S 0 . S^3=(A,A,B,A,B,C),\qquad S^4=S^0. S 3 = ( A , A , B , A , B , C ) , S 4 = S 0 .
At each source profile, voter i i i removes her current ballot and uses q i t = n t − e s i t q_i^t=n^t-e_{s_i^t} q i t = n t − e s i t . Each private vector has total mass five. Table 2 compares her prescribed next ballot with the other of her favorite and middle candidates. Voters 1 and 2 have identical utilities and ballots, so their comparisons coincide.
Table 2. All favorite–middle comparisons for the truthful period-four orbit. Private counts are in ( A , B , C ) (A,B,C) ( A , B , C ) order. The last column gives the first nonzero order and coefficient ( d , a ) (d,a) ( d , a ) of the chosen-minus-alternative margin, so the margin is a p d + O ( p d + 1 ) a p^d + O(p^{d+1}) a p d + O ( p d + 1 ) . Every preceding coefficient is zero.
Apply Lemma A.1 to each displayed private vector and margin. An entry ( d , a ) (d,a) ( d , a ) means that H t ( c , c ′ ; q i t ) = 0 H_t(c,c';q_i^t)=0 H t ( c , c ′ ; q i t ) = 0 for every η < d \eta<d η < d and i 2 H d ( c , c ′ ; q i t ) = a > 0 i^2H_{d}(c,c';q_i^t)=a>0 i 2 H d ( c , c ′ ; q i t ) = a > 0 . Thus the margin has first nonzero term a p d a p^d a p d . Each sum includes all feasible directed flows at its order, with their multinomial multiplicities and uniform averages over winner sets, including mixed trembles and ties.
Every displayed coefficient is positive. Lemma 4.3 makes the favorite ballot strictly better than the least-preferred ballot. Hence a prescribed favorite beats both alternatives; a prescribed middle ballot that beats the favorite also beats the least-preferred ballot. The table therefore verifies every voter’s unique limiting response at all four source profiles. The initial ballots are the respective favorites, the four complete profiles are distinct, and the initial count vector ( 2 , 2 , 2 ) (2,2,2) ( 2 , 2 , 2 ) occurs only once in the four-round block. Both the complete profile and the sequence of polls consequently have period four. Exactly five voters are active, and the winner sets are { A , B , C } \{A,B,C\} { A , B , C } , { B } \{B\} { B } , { A } \{A\} { A } , { A } \{A\} { A } .
The comparisons do not require the exact utility values in the figure. With each voter’s favorite and least-preferred utilities normalized to 1 and 0, let ρ i \rho_i ρ i be her middle utility. The same enumeration verifies the same strict responses throughout the nonempty open region
1 2 < ρ i < 9 11 ( i = 1 , 2 , 5 ) , 0 < ρ 3 < 1 2 , \frac{1}{2}<\rho_i<\frac{9}{11}\quad(i=1,2,5),\qquad0<\rho_3<\frac{1}{2}, 2 1 < ρ i < 11 9 ( i = 1 , 2 , 5 ) , 0 < ρ 3 < 2 1 ,
9 11 < ρ 4 < 1 , 0 < ρ 6 < 2 7 . \frac{9}{11}<\rho_4<1,\qquad0<\rho_6<\frac{2}{7}. 11 9 < ρ 4 < 1 , 0 < ρ 6 < 7 2 .
Indeed, each first coefficient is affine in the relevant middle utility, nonnegative at both stated interval bounds, and positive at at least one of them; every preceding coefficient vanishes throughout the interval. It is therefore positive throughout the open interval. The specified normalized utilities lie strictly inside these intervals. For each utility profile in this region, Lemma 3.1 also gives the same cycle under F p F_p F p for all sufficiently small positive p p p .
Proof of Lemma 5.6
This Appendix gives the complete flow calculations for Lemma 5.6. Only signs of leading coefficients matter, so common strictly positive factors are suppressed throughout. All coordinates are in ( A , B , C ) (A,B,C) ( A , B , C ) order.
Proof of Lemma 5.6. Let h = 2 s + 1 ≥ 7 h=2s+1\ge7 h = 2 s + 1 ≥ 7 . A split pair casts ( A , B ) (A,B) ( A , B ) and a pooled pair casts ( C , C ) (C,C) ( C , C ) . Let x x x pairs be split and put d = h − x d=h-x d = h − x . Including the h h h added C C C -voters, the poll is
( x , x , 2 ( h − x ) + h ) = ( x , x , x + 3 d ) . (x,x,2(h-x)+h)=(x,x,x+3d). ( x , x , 2 ( h − x ) + h ) = ( x , x , x + 3 d ) .
By symmetry, it is enough to consider a voter with ranking A ≻ C ≻ B A\succ C\succ B A ≻ C ≻ B and normalized utilities
( u ( A ) , u ( C ) , u ( B ) ) = ( 1 , ρ , 0 ) , 1 2 < ρ < 1. (u(A),u(C),u(B))=(1,\rho,0),\qquad\frac{1}{2}<\rho<1. ( u ( A ) , u ( C ) , u ( B )) = ( 1 , ρ , 0 ) , 2 1 < ρ < 1.
Her private vector is
q A = ( x − 1 , x , x + 3 d ) if split, so x > 0 , q^A=(x-1,x,x+3d)\qquad\text{if split, so }x>0, q A = ( x − 1 , x , x + 3 d ) if split, so x > 0 ,
q C = ( x , x , x + 3 d − 1 ) if pooled, so x < h . (7) q^C=(x,x,x+3d-1)\qquad\text{if pooled, so }x<h. \tag*{(7)} q C = ( x , x , x + 3 d − 1 ) if pooled, so x < h . (7)
Voting for A A A strictly dominates voting for B B B by Lemma 4.3, so only A A A and C C C need to be compared.
At terminal private counts v v v , both contemplated ballots leave C C C the unique winner whenever
v A ≤ v C − 2 , v B ≤ v C − 1. v_A\le v_C-2,\qquad v_B\le v_C-1. v A ≤ v C − 2 , v B ≤ v C − 1.
A nonzero contribution therefore requires
v A ≥ v C − 1 or v B ≥ v C . (8) v_A\ge v_C-1\qquad\text{or}\qquad v_B\ge v_C. \tag*{(8)} v A ≥ v C − 1 or v B ≥ v C . (8)
The decrease in each lead of C C C caused by one directed tremble is
C ↦ A C ↦ B B ↦ A A ↦ B A ↦ C B ↦ C v C − v A 2 1 1 − 1 − 2 − 1 v C − v B 1 2 − 1 1 − 1 − 2 (9) \begin{array}{c|cccccc}
& C\mapsto A & C\mapsto B & B\mapsto A & A\mapsto B & A\mapsto C & B\mapsto C\\
v_C-v_A & 2 & 1 & 1 & -1 & -2 & -1\\
v_C-v_B & 1 & 2 & -1 & 1 & -1 & -2 \tag*{(9)}
\end{array} v C − v A v C − v B C ↦ A 2 1 C ↦ B 1 2 B ↦ A 1 − 1 A ↦ B − 1 1 A ↦ C − 2 − 1 B ↦ C − 1 − 2 (9)
No tremble reduces either lead by more than two. A required reduction of 2 r 2r 2 r therefore takes at least r r r trembles, and at that order every tremble must reduce the lead by two. For a required reduction of 2 r − 1 2r-1 2 r − 1 , either all r r r trembles reduce the lead by two or exactly one reduces it by one. Together with (F.3), this gives the complete first contributing flow lists below and excludes every earlier order pointwise.
If x x x is odd, d d d is even. When d = 0 d=0 d = 0 , every pair is split and the no-tremble A − C A-C A − C margin at q A = ( x − 1 , x , x ) q^A=(x-1,x,x) q A = ( x − 1 , x , x ) is ( 1 − 2 ρ ) / 3 < 0 (1-2\rho)/3<0 ( 1 − 2 ρ ) /3 < 0 , so all pairs pool.
For even d ≥ 2 d\ge2 d ≥ 2 , put t = 3 d / 2 t=3d/2 t = 3 d /2 . At q C q^C q C , the first contributing order is t − 1 t-1 t − 1 , with the single flow ( t − 1 ) ( C ↦ A ) (t-1)(C\mapsto A) ( t − 1 ) ( C ↦ A ) and payoff difference ( 1 − ρ ) / 2 > 0 (1-\rho)/2>0 ( 1 − ρ ) /2 > 0 . A pooled pair therefore splits. At q A q^A q A , the first contributing order is t t t , with flows
t ( C ↦ A ) , t ( C ↦ B ) . t(C\mapsto A),\qquad t(C\mapsto B). t ( C ↦ A ) , t ( C ↦ B ) .
Their multiplicities are equal and their payoff differences are ( 1 − ρ ) / 2 (1-\rho)/2 ( 1 − ρ ) /2 and − ρ / 2 -\rho/2 − ρ /2 , respectively. The sum has sign 1 − 2 ρ < 0 1-2\rho<0 1 − 2 ρ < 0 , so a split pair pools. Thus every pair changes configuration when x x x is odd.
Now let x = 2 k x=2k x = 2 k , so d d d is odd. For d ≥ 3 d\ge3 d ≥ 3 , put
t : = 3 d − 1 2 . t:=\frac{3d-1}{2}. t := 2 3 d − 1 .
At q C = ( x , x , x + 2 t ) q^C=(x,x,x+2t) q C = ( x , x , x + 2 t ) , the first contributing order is t t t . Dividing multiplicities by ( x + 2 t ) t (x+2t)^t ( x + 2 t ) t gives
caption:
:::
The sum is a positive multiple of κ h − k − ρ \kappa_{h-k}-\rho κ h − k − ρ , where
κ h − k : = 2 + t + t x x + t + 1 3 + t + t x x + t + 1 . (10) \kappa_{h-k}:=\frac{2+t+\dfrac{tx}{x+t+1}}{3+t+\dfrac{tx}{x+t+1}}. \tag*{(10)} κ h − k := 3 + t + x + t + 1 t x 2 + t + x + t + 1 t x . (10)
Thus a pooled pair splits exactly when ρ < κ h − k \rho<\kappa_{h-k} ρ < κ h − k , provided equality is excluded. A row of zero multiplicity is absent.
If x > 0 x>0 x > 0 , the split voter’s private counts are q A = ( x − 1 , x , x + 2 t + 1 ) q^A=(x-1,x,x+2t+1) q A = ( x − 1 , x , x + 2 t + 1 ) and the first contributing order is t + 1 t+1 t + 1 . Dividing multiplicities by x + 2 t + 1 t + 1 \frac{x+2t+1}{t+1} t + 1 x + 2 t + 1 gives
{#eq:6}
This sum is a positive multiple of κ k − ρ \kappa_k-\rho κ k − ρ , where
κ k : = t + 3 + x ( t + 1 ) x + t + 1 2 t + 5 + ( 2 x − 1 ) ( t + 1 ) x + t + 1 . (11) \kappa_k:=\frac{t+3+\frac{x(t+1)}{x+t+1}}{2t+5+\frac{(2x-1)(t+1)}{x+t+1}}. \tag*{(11)} κ k := 2 t + 5 + x + t + 1 ( 2 x − 1 ) ( t + 1 ) t + 3 + x + t + 1 x ( t + 1 ) . (11)
Thus a split pair remains split exactly when ρ < κ k \rho<\kappa_k ρ < κ k , provided equality is excluded. When x = 0 x=0 x = 0 , no split-pair comparison exists; κ 0 = 1 / 2 \kappa_0=1/2 κ 0 = 1/2 is only the lower utility bound.
When d = 1 d=1 d = 1 , some generic flow expressions coincide and three-way ties change the payoffs. Each distinct flow must be counted once. The complete calculations at q C = ( x , x , x + 2 ) q^C=(x,x,x+2) q C = ( x , x , x + 2 ) and q A = ( x − 1 , x , x + 3 ) q^A=(x-1,x,x+3) q A = ( x − 1 , x , x + 3 ) are
q C q^C q C : order 1
{#eq:8}
$q^A$: order 2
| Flow | Multiplicity | Payoff difference |
| $2(C\mapsto B)$ | $\binom{x+3}{2}$ | $-\rho/2$ |
| $(C\mapsto A)+(C\mapsto B)$ | $(x+3)(x+2)$ | $(1-2\rho)/3$ |
| $2(C\mapsto A)$ | $\binom{x+3}{2}$ | $1-\rho$ |
| $(B\mapsto A)+(C\mapsto A)$ | $x(x+3)$ | $(1-\rho)/2$ |
| $(A\mapsto B)+(C\mapsto B)$ | $(x-1)(x+3)$ | $-\rho/2$ | \tag*{(12)}
Their sums are positive multiples of κ h − k − ρ \kappa_{h-k}-\rho κ h − k − ρ and κ k − ρ \kappa_k-\rho κ k − ρ , respectively. Here x = 2 k = h − 1 x=2k=h-1 x = 2 k = h − 1 , and
κ h − k : = 11 x + 16 13 x + 20 , κ k : = 16 x + 20 29 x + 28 . (13) \kappa_{h-k}:=\frac{11x+16}{13x+20},\qquad\kappa_k:=\frac{16x+20}{29x+28}. \tag*{(13)} κ h − k := 13 x + 20 11 x + 16 , κ k := 29 x + 28 16 x + 20 . (13)
Equations (F.7) and (F.10) define κ k \kappa_k κ k for 1 ≤ k ≤ s 1\le k\le s 1 ≤ k ≤ s , while (F.5) and (F.10) define κ h − k \kappa_{h-k} κ h − k for 0 ≤ k ≤ s 0\le k\le s 0 ≤ k ≤ s . These disjoint index ranges contain all h h h switching values.
Replacing x x x by x + 2 x+2 x + 2 also replaces d d d by d − 2 d-2 d − 2 and t t t by t − 3 t-3 t − 3 . Substitution into (F.7) gives, for x = 2 k > 0 x=2k>0 x = 2 k > 0 and d ≥ 5 d\ge5 d ≥ 5 ,
κ k + 1 − κ k = 4 ( 9 d x + 3 d + 6 x 2 + 1 ) ( 9 d 2 + 12 d x − 14 x − 13 ) ( 9 d 2 + 12 d x + 12 d + 10 x + 3 ) > 0. \kappa_{k+1}-\kappa_k=
\frac{4(9dx+3d+6x^2+1)}
{(9d^2+12dx-14x-13)(9d^2+12dx+12d+10x+3)}>0. κ k + 1 − κ k = ( 9 d 2 + 12 d x − 14 x − 13 ) ( 9 d 2 + 12 d x + 12 d + 10 x + 3 ) 4 ( 9 d x + 3 d + 6 x 2 + 1 ) > 0.
Similarly, substitution into (F.5) gives, for x = 2 k ≥ 0 x=2k\ge0 x = 2 k ≥ 0 and d ≥ 5 d\ge5 d ≥ 5 ,
κ h − k − κ h − k − 1 = 4 ( 9 d 2 + 36 d x + 36 d + 24 x 2 + 36 x + 11 ) ( 9 d 2 + 12 d x + 6 d − 16 x − 27 ) ( 9 d 2 + 12 d x + 18 d + 8 x + 5 ) > 0. \kappa_{h-k}-\kappa_{h-k-1}=
\frac{4(9d^2+36dx+36d+24x^2+36x+11)}
{(9d^2+12dx+6d-16x-27)(9d^2+12dx+18d+8x+5)}>0. κ h − k − κ h − k − 1 = ( 9 d 2 + 12 d x + 6 d − 16 x − 27 ) ( 9 d 2 + 12 d x + 18 d + 8 x + 5 ) 4 ( 9 d 2 + 36 d x + 36 d + 24 x 2 + 36 x + 11 ) > 0.
The two denominator factors that are not visibly positive are 9 d 2 − 13 + ( 12 d − 14 ) x 9d^2-13+(12d-14)x 9 d 2 − 13 + ( 12 d − 14 ) x and 9 d 2 + 6 d − 27 + ( 12 d − 16 ) x 9d^2+6d-27+(12d-16)x 9 d 2 + 6 d − 27 + ( 12 d − 16 ) x ; both are positive for d ≥ 5 d\ge5 d ≥ 5 . At the two d = 3 d=3 d = 3 boundaries, with x > 0 x>0 x > 0 for the first comparison, the corresponding differences are
κ k + 1 − κ k = 2 x 2 + 109 x + 110 ( 23 x + 60 ) ( 29 x + 86 ) > 0 , \kappa_{k+1}-\kappa_k=\frac{2x^2+109x+110}{(23x+60)(29x+86)}>0, κ k + 1 − κ k = ( 23 x + 60 ) ( 29 x + 86 ) 2 x 2 + 109 x + 110 > 0 ,
and
κ h − k − κ h − k − 1 = 2 x 2 + 47 x + 50 ( 11 x + 35 ) ( 13 x + 46 ) > 0. \kappa_{h-k}-\kappa_{h-k-1}=\frac{2x^2+47x+50}{(11x+35)(13x+46)}>0. κ h − k − κ h − k − 1 = ( 11 x + 35 ) ( 13 x + 46 ) 2 x 2 + 47 x + 50 > 0.
The split thresholds lie in ( 1 / 2 , 2 / 3 ) (1/2,2/3) ( 1/2 , 2/3 ) . For (F.7), the coefficient sum at ρ = 1 / 2 \rho=1/2 ρ = 1/2 has sign 1 + ( t + 1 ) / ( x + t + 1 ) > 0 1+(t+1)/(x+t+1)>0 1 + ( t + 1 ) / ( x + t + 1 ) > 0 , whereas at ρ = 2 / 3 \rho=2/3 ρ = 2/3 it has sign − t − 1 − ( x − 2 ) ( t + 1 ) / ( x + t + 1 ) < 0 -t-1-(x-2)(t+1)/(x+t+1)<0 − t − 1 − ( x − 2 ) ( t + 1 ) / ( x + t + 1 ) < 0 ; here a split voter has even x ≥ 2 x\ge2 x ≥ 2 . The pooled threshold in (F.5) equals 1 − 1 / ( 3 + t + t x / ( x + t + 1 ) ) 1-1/(3+t+tx/(x+t+1)) 1 − 1/ ( 3 + t + t x / ( x + t + 1 )) and lies in ( 2 / 3 , 1 ) (2/3,1) ( 2/3 , 1 ) . The two roots in (F.10) have the respective ranges because x = h − 1 ≥ 6 x=h-1\ge6 x = h − 1 ≥ 6 . Thus κ s < 2 / 3 < κ s + 1 \kappa_s<2/3<\kappa_{s+1} κ s < 2/3 < κ s + 1 , completing the ordering. Consequently,
1 2 < κ 1 < κ 2 < ⋯ < κ h < 1. (14) \frac{1}{2}<\kappa_1<\kappa_2<\cdots<\kappa_h<1. \tag*{(14)} 2 1 < κ 1 < κ 2 < ⋯ < κ h < 1. (14)
We can now read off the update. The odd-x x x calculation already showed that every pair changes configuration. If x = 2 k x=2k x = 2 k , a split pair remains split exactly when ρ < κ k \rho<\kappa_k ρ < κ k , and a pooled pair becomes split exactly when ρ < κ h − k \rho<\kappa_{h-k} ρ < κ h − k . Giving both members of pair i i i utilities in ( κ τ i , κ τ i + 1 ) (\kappa_{\tau_i},\kappa_{\tau_i+1}) ( κ τ i , κ τ i + 1 ) therefore gives
Φ ( I ) = P ∖ I ( x odd ) , \Phi(I)=P\setminus I \qquad(x\ \text{odd}), Φ ( I ) = P ∖ I ( x odd ) ,
and
Φ ( I ) = { i ∈ I : τ i < k } ∪ { i ∈ P ∖ I : τ i < h − k } ( x = 2 k ) . \Phi(I)=\{i\in I:\tau_i<k\}\cup\{i\in P\setminus I:\tau_i<h-k\}\qquad(x=2k). Φ ( I ) = { i ∈ I : τ i < k } ∪ { i ∈ P ∖ I : τ i < h − k } ( x = 2 k ) .
All inequalities are strict. If A A A is selected, then U P ( A ) > U P ( C ) U^P(A)>U^P(C) U P ( A ) > U P ( C ) for all sufficiently small ρ \rho ρ , while U P ( A ) > U P ( B ) U^P(A)>U^P(B) U P ( A ) > U P ( B ) by Lemma 4.3. If C C C is selected, then U P ( C ) > U P ( A ) > U P ( B ) U^P(C)>U^P(A)>U^P(B) U P ( C ) > U P ( A ) > U P ( B ) . Exchanging A A A and B B B proves the corresponding statement for the other member of every pair. Thus paired profiles map to paired profiles.
Finally, consider an added voter with ranking C ≻ A ≻ B C\succ A\succ B C ≻ A ≻ B and normalized utilities ( 1 , γ , 0 ) (1,\gamma,0) ( 1 , γ , 0 ) in ranking order, where 0 < γ < 1 / 2 0<\gamma<1/2 0 < γ < 1/2 . Her private vector is q C q^C q C for every x x x , including x = h x=h x = h . The same flow sums give her C − A C-A C − A margin the signs 1 − 2 γ 1-2\gamma 1 − 2 γ for d = 0 d=0 d = 0 , 1 − γ 1-\gamma 1 − γ for positive even d d d , and ( 13 x + 20 ) − ( 11 x + 16 ) γ (13x+20)-(11x+16)\gamma ( 13 x + 20 ) − ( 11 x + 16 ) γ for d = 1 d=1 d = 1 . For odd d ≥ 3 d\ge3 d ≥ 3 , with t = ( 3 d − 1 ) / 2 t=(3d-1)/2 t = ( 3 d − 1 ) /2 , its sign is ( 2 + t + t x / ( x + t + 1 ) ) ( 1 − γ ) + 1 (2+t+tx/(x+t+1))(1-\gamma)+1 ( 2 + t + t x / ( x + t + 1 )) ( 1 − γ ) + 1 . All four expressions are positive. Lemma 4.3 excludes B B B , so every added voter stays at C C C . □ \square □