Department of Policy and Planning Sciences
Discussion Paper Series

No.1367

The Evolution of Collective Choice Under Majority Ruleby
Akira OKADA, Ryoji SAWA

January 2020
Revised February 2021

UNIVERSITY OF TSUKUBA
Tsukuba, Ibaraki 305-8573
JAPANThe Evolution of Collective Choice under Majority Rule*
Akira Okada† and Ryoji Sawa‡
February 24, 2021

Abstract We consider a dynamic process of collective choice under majority rule in whicha status quo policy evolves. The analysis is based on stochastic evolutionary game theory. The
Condorcet winner is uniquely a long-run equilibrium for all (super-)majority rules. When theCondorcet winner does not exist, the long-run equilibria under all majority voting rules belong to
the top cycle of policies under a simple majority. When the policy space is multidimensional andthe voting quota is larger than the min-max quota, the long-run equilibrium belongs to the minmax set. Finally, the Borda winner appears as a long-run equilibrium under unanimity if voters’
behavior is governed by a logit choice rule.

Keywords: Collective choice; Voting; Stochastic evolutionary game theory; Condorcet winner; Borda winner.

* The authors thank Munetomo Ando, Michael Bognanno, Yi-Chun Chen, Toshimasa Maruta, Jonathan Newton,

Daisuke Oyama, Satoru Takahashi, Dai Zusai, and seminar participants at the Japanese Economic Association 2015
Fall Meeting, SAET 2017 Conference, Learning, Evolution, and Games 2018 Conference, 284th Queueing Theory
Workshop of the Operations Research Society of Japan, Monash University, National University of Singapore, Nihon
University Population Research Institute, Osaka University, Tohoku University, University of Aizu, Keio University,
University of Melbourne, University of New South Wales, University of Sydney, and Yokohama National University
for their helpful comments and suggestions. We acknowledge financial support from the Japan Society for the Promotion of Science: JSPS KAKENHI Grants-in-Aid for Scientific Research (A) No. 26245024 (Okada), Young Scientists(B) No. 15K17023 (Sawa), and Early-Career Scientists No. 18K12740 (Sawa), and from Nomura Foundation (Grants
in Social Science) (Sawa). This paper was formerly circulated as “An evolutionary approach to social choice problems
with q-quota rules”.
† professor emeritus, Hitotsubashi University, 2-1 Naka, Kunitachi, Tokyo 186-8601, JAPAN. Email:aokada313@gmail.com.
‡ Department of Policy and Planning Sciences, University of Tsukuba, Tennoudai 1-1-1, Tsukuba, Ibaraki 3058573, JAPAN. E-mail: rsawa@sk.tsukuba.ac.jp.

11Introduction

We present a dynamic model of collective choice under majority rule in which a status quo policy
evolves, challenged by a new policy in every period. A challenging policy is drawn randomly froma finite set of policies. If the challenging policy wins the majority, then it becomes the status quo
policy in the next period. Otherwise, the current status quo policy remains in effect. In contrast
to the traditional literature on legislative bargaining, beginning with Baron and Ferejohn (1989),
our analysis is based on stochastic evolutionary game theory. Voters are boundedly rational in thesense that they are myopic, and they may make a mistake, probabilistically. A model of boundedly
rational behavior is suitable when voters do not have perfect foresight about voting outcomes, owing to uncertainty and complexity in the political environment and incomplete policy descriptions.
This study aims to characterize long-run equilibria in dynamic policy-making processes.
According to Baron (1996), many of the collective choices are continuous, rather than once-off.
Decisions made today may become the status quo in future and, thus, affect future decisions (e.g.,constitutional amendments, referendums, and national elections). Therefore, we focus on long-run,rather than short-run outcomes of collective choices. An example of our setting is dynamic legislative bargaining, where a policy becomes the status quo in the next period if it receives a qualified
majority. Legislators may make myopic decisions if their main concern is to be elected in a coming
election. We focus on the evolution of the public policies implemented in such environments.
This study relates the static solution concepts of social choice theory to a long-run equilibriumin a dynamic voting process. The Condorcet (1785) winner is a policy that defeats all other policies
under a simple majority rule. It is the median of the players’ ideal policies when the policy spaceis one-dimensional and voters’ preferences are single peaked (Black 1948). However, when thepolicy space has two or more dimensions, the set of undefeated policies under the simple majority(called the majority core) may be empty without strong assumptions; see Plott (1967), Tullock(1967), and Davis et al. (1972) for early studies on this topic. Furthermore, McKelvey (1976,1979) shows that when the majority core is empty, the “top cycle” (i.e., the set of policies thatcan be reached from any other policy through a finite chain of majority preferences) is the wholepolicy space.1 That is, any policy can be reached from any other through a process of pairwise
majority comparisons. This result is often interpreted as fragility or instability in majority voting(some call it chaos). Riker (1980) writes: “the sum of our new sophistication is, therefore, thatpolitical outcomes truly are unpredictable in the long run.”
Simpson (1969) proposed the min-max policy, which is weaker than the Condorcet winner.
For a policy a, let n(a) be the maximum number of voters who vote against a by voting for a
1 Plott (1967) provides the necessary and sufficient conditions for the non-empty majority core. McKelvey (1976)shows that under certain conditions, the top cycle is always the whole policy space when the majority core is empty.

2different policy. A min-max policy minimizes n(a) for all policies, and has “the property that the
maximum number of voters wishing to move in any direction is a minimum.” (Simpson, 1969).
The set of min-max policies is called the min-max set, and the min-max number of voters the minmax quota.2 A min-max policy always exists, and the Condorcet winner (if it exists) is a uniquemin-max policy (when preferences are strict).
We employ stochastic evolutionary game theory to characterize a long-run equilibrium. The
theory examines the robustness of each policy when voters’ behavior includes the possibility of rare
mistakes. Here, we assume a stochastic choice rule for voters in which, with a small positive probability, they may make a mistake by choosing a suboptimal policy. Specifically, we assume voters’
error probabilities are identical and independent across policies and individuals. The dynamic
process with the aforementioned choice rule is called the best-response dynamics with mutations(BRM). This dynamic process of collective choice generates a (irreducible and aperiodic) Markov
process with finite states. A policy is stochastically stable (or a long-run equilibrium) if the stationary distribution of the Markov process places a positive probability on it in the limit, such that theerror probability vanishes. Intuitively, a stochastically stable policy is the most likely equilibrium
when random perturbations to voters’ behavior are small. The set of stochastically stable policies
is independent of an initial status quo policy. Furthermore, it is known that a stochastically stablestate exists under a general choice rule satisfying a regularity condition (Sandholm, 2010).
Our results are summarized as follows. First, we prove that the Condorcet winner (if any) is
uniquely stochastically stable for every majority rule in which the majority quota q varies froma simple majority to unanimity. When the Condorcet winner does not exist, every stochasticallystable policy under every majority rule (including unanimity) belongs to the top cycle under asimple majority.
Second, even in settings with no Condorcet winner, we find conditions to further characterize
long-run equilibria among policies in the top cycle. The long-run equilibria under each majority
voting rule must belong to the min-max set when the majority quota q is larger than the min-max
quota, and the policy space is multidimensional and discretized sufficiently finely. This implies
that stochastic evolutionary theory mitigates the indeterminacy problem of majority voting for
multidimensional policy spaces. If the voting quota is less than the min-max quota, majority voting
may cause the intransitivity of social choice (the paradox of voting). If the quota is greater thanthe min-max quota, we confront the indeterminacy problem — the core includes many policies. In
particular, under unanimity, the core coincides with the set of Pareto efficient policies. Stochastic
evolutionary theory shows that policies stay in the min-max set in the long run, which is much
2 The min-max quota is the minimal majority size under which an undefeated policy exists. Caplin and Nalebuff(1988) show that when the policy space is multidimensional and the density of voters’ ideal points is concave over its
support, the min-max quota is less than 64% of voters.

3smaller than the set of Pareto efficient policies.
Third, to examine the influence of the voting behavior on long-run equilibria, we consider
another probabilistic voting model: a logit rule in which voters’ error probabilities are governedby the logit function. We prove that the Borda (1781) winner is the unique long-run equilibrium
under the unanimity rule. This has a positive implication for the normative (and old) debate concerning the Condorcet winner versus the Borda winner: either solution can emerge as a long-run
equilibrium of a dynamic unanimity voting process, depending on the voters’ behavioral model.
We discuss several strands of the literature related to this paper.3 Our result provides an evolutionary approach to recent literature on legislative bargaining with an endogenous status quo
policy, as proposed by Baron (1996); see Kalandrakis (2004), Battaglini and Coate (2007), Penn
(2009), Anesi (2010), Duggan and Kalandrakis (2012), Anesi and Seidmann (2015), Diermeier
et al. (2017), and Nunnari (2021), among others. Most studies in this literature employ the rational
choice paradigm, which assumes voters maximize their long-term utility, have perfect foresight,
and have perfect knowledge of others’ preferences. Baron (1996) presents a (now standard) modelof legislative bargaining with an endogenous status quo, where a legislator is selected randomly
to propose a policy. In the unidimensional case, he characterizes a stationary Markov perfectequilibrium in which the outcome converges to the median’s ideal point (the Condorcet winner).
Duggan and Kalandrakis (2012) establish the existence of a stationary Markov perfect equilibriumin a multidimensional case with general preferences, and prove the convergence to the Condorcet
winner under a weighted majority rule. In a three-person divide-the-dollar game under majority
voting, Kalandrakis (2004) shows that the proposer eventually exploits the whole dollar in all periods, irrespective of the common discount factor. Nunnari (2021) extends the model of Kalandrakis(2004) to the one with a veto player and shows, both theoretically and experimentally, that there isalways an equilibrium where the veto player eventually exploits the whole dollar. Anesi and Seidmann (2015) extend the result of Kalandrakis (2004) to an n-person divide-the-dollar game. They
focus on a special class of no-delay stationary Markov perfect equilibria in which the first proposal
is accepted and remains effective in all future rounds. In the case of a finite policy space, Anesi(2010) and Diermeier et al. (2017) characterize a von-Neumann and Morgenstern stable set as thelimit set of a stationary Markov perfect equilibrium. Battaglini and Coate (2007) examine the efficiency of legislative bargaining as it relates to public spending and taxation. Penn (2009) considers
a model of legislative bargaining with logit choice rules, where a proposal is chosen according to a
fixed probability distribution, similarly to ours. She proves the existence and uniqueness of a valuefunction that expresses voters’ long-term preferences over policies, but she does not characterize
3 For applications of stochastic evolutionary game theory in cooperative settings, see Agastya (1999), Jackson
and Watts (2002), Arnold and Schwalbe (2002), Klaus et al. (2010), Newton (2012), Sawa (2014), Newton and Sawa
(2015), Nax and Pradelski (2015), Boncinelli and Pin (2018), and Bilancini et al. (2020). See also Section 2 of Newton(2018).

4the long-run equilibrium.
Other related studies are those that consider evolutionary dynamics in voting settings; see
Kanazawa (1998), Bendor et al. (2003), Fowler (2006), Conley et al. (2006), and Landi and Sodini (2012), for example. Their main concern is the paradox of voter turnout — people do voteeven if the cost of voting is seemingly greater than the benefit of the chance of being pivotal.
Kanazawa (1998) considers adaptive learning dynamics with voters who learn from the past correlations between their choices and the outcomes. Bendor et al. (2003) and Fowler (2006) consider
evolutionary dynamics where voters adjust their aspiration levels that determine whether outcomesare satisfactory or not. Conley et al. (2006) adopt a model of preference evolution, where preferences associated with propensities to vote evolve. Landi and Sodini (2012) consider best response
dynamics with conformist voters, i.e., voters prefer to do what others do. These studies offer someevolutionary model that can explain the paradox.
There are several papers that consider social dynamics in different contexts from ours. Lagunoff and Matsui (1995) consider dynamic processes under a class of decision mechanisms, including majority voting, that map players’ yes/no strategies to their (mandatory) contribution forprovision of a public good. Gomes and Jehiel (2005), Acemoglu et al. (2011), and Acemoglu
et al. (2012) consider dynamic settings with farsighted players where a winning coalition chooses
the next state in each period. It is shown that in general, the state that such dynamic processes
converge to may or may not be Pareto efficient. Nax and Rigos (2016) and Wu (2016) consider
dynamic settings where players endogenously make the choice of assortative mechanism underdemocratic processes, e.g. majority voting. Belloc and Bowles (2017) consider the simultaneous
evolution of preferences and institutions, and Wu (2017) considers the evolution of character traits
under different political institutions.
Besides legislative bargaining problems, evolutionary and learning models of collective choice
can be applied to many social and economic problems. Among them, the theory of social contract
is an important application. While there are many works which consider justice and social contract
in the framework of evolutionary game theory (Binmore 1994 and 2005, Skyrms 1996 and Young
1993 and 1998, etc.), most works are restricted to the two-person case. Our evolutionary result oncollective choice is an attempt to incorporate the notion of a coalition into the literature. Anotherinteresting application is a dynamic opinion formation process. When players receive noisy private
signals about a true state, gather their neighbors’ opinions, and update their own views repeatedly,
Golub and Jackson (2010) show that all players’ opinions may converge to a truth under a naı̈ve
learning process. See Grabisch and Rusinowska (2020) for a survey on the recent developments.
To conclude the introduction, it may be useful to compare the rational choice approach and our
evolutionary approach to the collective choice problem in three aspects. The first is the assumptionof rationality. In the rational choice approach, voters are assumed to be rational, make no mistakes,
5and have perfect knowledge of others’ preferences. In contrast, the evolutionary approach assumes
that voters may make a mistake, with small probability, and does not rely on the assumption ofcommon knowledge about others’ preferences. In our view, both approaches are complementary,
providing a better understanding of complex real-world voting processes.
The second aspect is related to the modelling. A standard model of legislative bargaining
randomly selects a legislator to make a proposal in each round. In contrast, the proposal process inour evolutionary model (and in Penn (2009)) is probabilistic and exogenous. In reality, a proposal
process is determined by institutional factors, including formal recognition protocols, negotiations
over proposal rights, and social norms (e.g., seniority). To minimize the dependence on the detailsof the model, we take an institution-free approach: rather than formulating an institutional process
explicitly, we assume a proposal occurs through an unknown random process. The set of long-run
equilibria is invariant with respect to a probability distribution over proposals.
The third aspect is the sensitivity to model parameters. Legislative bargaining results are often sensitive to the model parameters, e.g. voting rules, cardinal utilities, discount factors, and aprobability distribution when choosing a proposer. In contrast, the long-run equilibrium of ourevolutionary model depends on a smaller set of parameters, such as ordinal preferences and voting
rules, given a stochastic choice rule for voters.
The remainder of the paper is organized as follows. Section 2 presents the collective choicemodel. Section 3 formulates the dynamic policy-making process. Section 4 characterizes the longrun equilibrium under the BRM. Section 5 extends the analysis to the case of multidimensional
policy spaces, and Section 6 considers the logit choice rule under unanimity. Section 7 concludes
the paper. All proofs are given in the Appendix.

2

The Collective Choice Model

Let N = {1, . . . , n} be the set of players, and let A be a finite set of policies. Each player i has
a strict preference over A (indifference is not allowed). The utility function of player i is a realvalued function ui : A → R. In what follows, N, A , and {ui }i∈N are fixed. Players collectively
choose a policy under majority voting. We consider a class of majority voting rules with different
quotas. Here, a quota is denoted as q ∈ {1, . . . , n}, which is the minimum number of votes required
for a challenging policy to win against a status quo policy. The quota for a simple majority is givennby q = n+1
2 for odd n, and by q = 2 + 1 for even n. For our analysis, we introduce the following
notation: n+1 for odd n,2q=n
for even n.
2

6

Briefly, q is the largest integer not greater than (n + 1)/2. The quota for a simple majority is equal
to q for odd n, and to q + 1 for even n. When q = n, the majority voting is unanimity. We focus on
the case in which the quota q is greater than or equal to q. In what follows, a majority voting rulewith a q-quota is referred to simply as a q-majority.
For any pair of policies a, a0 ∈ A , let N(a, a0 ) denote the set of players who prefer a0 to a, andn(a, a0 ) be the number of such players. We say that a0 defeats a under a q-majority if n(a, a0 ) ≥ q,
and that a is undefeated under a q-majority if it is not defeated by any other policy under theq-majority.
Given a quota q, the q-majority core is the set of undefeated policies under a q-majority. We
denote the q-majority core by C(q), which may be empty. For two policies a, a0 ∈ A and two
quotas q and q0 , with q < q0 , a0 defeats a under a q-majority if a0 defeats a under the q0 -majority;
thus, C(q) ⊂ C(q0 ). The q-majority core expands as q increases. The n-majority core C(n) is equal
to the set of Pareto efficient policies. Definen(a) =

max n(a, a0 ),a0 ∈A \{a}which is the maximum number of voters who prefer some policy a0 to a. A policy a is defeatedby some other policy under a q-majority if and only if n(a) ≥ q. Thus, the q-majority core C(q) is
equal to the set {a ∈ A : n(a) < q}.
A Condorcet winner, denoted as aCW , is a policy that defeats any other policy under a simple
majority. By definition, aCW ∈ A is a Condorcet winner if n(a, aCW ) > n/2, for all a 6= aCW .
A Condorcet winner aCW (if any) is unique and belongs to the simple majority core. Under theassumption of strict preferences, it holds that n(a, a0 ) + n(a0 , a) = n, for a 6= a0 . Thus, a policya ∈ A is a Condorcet winner if and only if n(a) < n/2. For any a 6= aCW , n(a, aCW ) > n/2, andthus n(a) > n/2. Therefore, the Condorcet winner aCW minimizes n(a) for all policies a ∈ A .
The literature on social choice theory has proposed two generalized notions of the Condorcet
winner: the top cycle (Miller, 1977), and the min-max set (Simpson, 1969).
A policy a ∈ A is said to indirectly defeat b ∈ A under a q-majority, denoted as a ∗q b, if
there exists a sequence (a1 , . . . , am ) of policies with a1 = b and am = a, such that ai+1 defeats ai
for every i = 1, · · · , m − 1. The top cycle under a q-majority is a set of policies, each member ofwhich indirectly defeats every other policy in A . Let Aqtc denote the top cycle under a q-majority.
Formally, Aqtc is defined as the set {a ∈ A : ∀a0 ∈ A , a0 6= a, a ∗q a0 }. There are noteworthy
properties of the top cycle. The Condorcet winner (if any) is the top cycle under a simple majority.
The top cycle Aqtc exists for every q ≤ q, but may be empty for q > q. If the q-majority core C(q)is nonempty, then the top cycle Aqtc must be a subset of the core.4 Furthermore, Aqtc is empty
4 Any policy not in C(q) does not indirectly defeat policies in C(q) and, thus, is not in A tc .
q7

if C(q) contains more than one policy.5 In addition, C(q) is empty if the top cycle Aqtc contains
more than one policy.6 The top cycle plays a role only when the q-majority core is empty.7 Miller(1977, Theorem 7) shows the following characterization of the top cycle under a q-majority. The
top cycle Aqtc is the minimal undefeated set: (i) no policy in Aqtc is defeated by any policy not in
Aqtc under the q-majority; and (ii) no proper subset of Aqtc satisfies (i).
A min-max policy is a policy that minimizes n(a) over A . The minimum number of n(a)for a ∈ A is called the min-max quota, denoted by n. It is the maximum number of voters who
prefer some policy to a min-max policy. The set of min-max policies is called the min-max set,
and is denoted as A mm . The min-max set A mm is always nonempty. If the Condorcet winner aCW
exists, then aCW is a unique min-max policy. The relationship of the min-max set A mm to the qmajority core C(q) is as follows. By definition, a min-max policy is undefeated under a q-majority
rule if q > n. Thus, A mm ⊆ C(q) if q > n. When q = n + 1, every policy a in C(n + 1) satisfiesn(a) < n + 1. From the definition of n, it must hold that n(a) = n for every policy a in C(n + 1).
Thus, A mm = C(q) if q = n + 1. When q ≤ n, A mm 6= C(q) = 0.
/
A myopic stable set (MSS) is a general solution concept for cooperative settings (Demuynck
et al. 2019). In our context, it is the set of all voting cycles under a given q-majority. Formally,a set MSSq ⊆ A is a myopic stable set under a q-majority if it satisfies the three conditions: (i)for all a ∈ MSSq , a0 ∈ MSSq if a0 ∗q a, (ii) for all a ∈ A \ MSSq , there is a0 ∈ MSSq such thata0 ∗q a, and (iii) MSSq is the minimal set satisfying (i) and (ii). The first condition implies that a
MSSq is closed under better replies of coalitions of size q. The second condition implies that forany policy outside MSSq , there is a sequence of (coalitional) better replies that leads to MSSq . For
every q ∈ {q, . . . , n}, MSSq exists and is unique. For a q-majority, MSSq = Aqtc .
The next example illustrates the above concepts.
Example 1. Consider a collective choice problem with 25 voters and 4 policies. q = 25+1
2 = 13.
The voters’ preferences are summarized in Table 1. Each cell in the right matrix gives the total
number of voters who prefer a row policy to a column policy. For example, 25 voters prefer a2 to
a3 . The Condorcet winner is a1 , because it wins 13 votes against any other policy. The q-majority
core is {a1 } for q = 13, and is {a1 , a2 } for all q ≥ 14. Policy a2 is in the q-majority core for q ≥ 14
since it does not lose 14 votes against any policy (to see this, check the column of ’a2 ’, whichshows that a2 loses at most 13 votes). The top cycle is {a1 } for q = 13, and is empty for all q ≥ 14.
The min-max set is {a1 }, and the min-max quota is n = 12 since the number of voters who preferanother policy to the Condorcet winner a1 is at most 12. The myopic stable set coincides with theq-majority core for every q ≥ 13.
5 Consider a, a0 ∈ C(q). Policies a and a0 are not in the top cycle either, because a ∗ a0 and a0 ∗ a.
qq
6 If a, a0 ∈ A tc , then a ∗ a0 and a0 ∗ a, which implies that a and a0 can be defeated. Because all policies outsideqqq
Aqtc are defeated, every policy is defeated. That is, the q-majority core is empty.
7 If both concepts are nonempty, then they reduce to a common single element.

8

Table 1: Preference and voting matrices of 25 voters and four policies
Preferencesa1  a2  a3  a4a2  a4  a3  a1Status quoaᵗ

A challenger a’drawn from paᵗ# of players
13
12Vote between
a’ and aᵗ

a1
a2
a3
a4

a1 a2
− 13
12 −
12 0
12 0

a3 a4
13 13
25 25
− 13
12 −

a’ wins Status quo
aᵗ⁺¹ = a’A challenger â
drawn from paᵗ⁺¹

Status quo
aᵗ⁺¹ = aᵗ

A challenger ã
drawn from paᵗ⁺¹

aᵗ wins
Period t

Period t+1

Figure 1: Path of play3

A Dynamic Policy-Making Process

We consider a dynamic political process in which players vote recurrently using pairwise comparisons under a q-majority. The status quo policy in period t is denoted as at ∈ A . A policy a ∈ A
is drawn against the status quo policy at according to a (predetermined) probability distribution
pat . Every policy has a positive chance of being selected as a challenging policy.8 All players votesimultaneously between a and at , according to their choice rules, which are defined below. If thechallenging policy a wins at least q votes, it will become the status quo policy in the next period.
Otherwise, at remains as the status quo policy. Figure 1 illustrates the process.
We consider a probabilistic voting behavior that has been well studied in the literature (e.g.,
see Coughlin (1992), Banks and Duggan (2005), Schofield (2005), McKelvey and Patty (2006),
and Penn (2009)). Specifically, we assume every player might, with a small probability, vote fora suboptimal policy. Such stochastic behavior can occur for several reasons. First, players are
not perfectly rational, and thus may choose a suboptimal policy by mistake. Second, players are
uncertain about the outcomes of policies, owing to random shocks to the political environment.
Third, incomplete descriptions of policies may result in stochastic voting. In what follows, weinterpret stochastic voting as occurring owing to voters’ mistakes.
For all a, a0 ∈ A , let Ψi (a, a0 ) denote the probability that player i votes for a0 against a. When
8 The probability distribution over policies can be arbitrary. Our results are not affected in any critical way by the

choice of distribution, as long as each policy has a positive probability of being selected.

9

player i makes no error, Ψi (a, a0 ) is given by91 if u (a0 ) > u (a),ii
Ψ0i (a, a0 ) =0 if u (a0 ) ≤ u (a).
i
i

(1)

Each player votes for the best policy with probability one. Under the possibility of making mistakes, each player i’s choice is given by the following: for all a, a0 ∈ A ,1 − εΨεi (a, a0 ) =ε

if ui (a0 ) > ui (a),if ui (a0 ) ≤ ui (a).

(2)

where ε > 0 is the probability of making a mistake. Each player votes for the optimal policy withprobability 1 − ε, and votes for a suboptimal policy with probability ε. This stochastic choice ruleis called the BRM. The formal transition probabilities of the process can be found in Appendix A.
The aim of our analysis is to characterize the long-run equilibrium of a dynamic process ofmajority voting when ε is sufficiently small. The perturbed process with ε > 0 is a Markov chainqqqwith a unique stationary distribution, denoted as πε . Let πε (a) denote the probability that πε placesqq
on policy a ∈ A . Let πε (A1 ) = ∑a∈A1 πε (a) for a subset A1 ⊆ A . Then, the players’ behavior isqsummarized asymptotically by the stationary distribution — πε (a) represents the fraction of timein which policy a is enacted over a long time horizon. In what follows, we refer to a policy in A a
state of the process, if no confusion arises.
Definition. A state z ∈ A is stochastically stable under a q-majority ifqlimε→0 πε (z) > 0.
In general, a stochastically stable state is the policy most likely to be enacted in the long termwhen voters’ behavior is probabilistic, but the mistake rate is small. Theorem 3.16 of Demuynck
et al. (2019) show that the set of recurrent states of the unperturbed process (ε = 0) coincides withMSSq . This means that all stochastically stable policies under a q-majority must be in MSSq (seeTheorem A.1 and its implication).
We provide the computation method, established in the literature on stochastic evolutionary
game theory, for a stochastically stable state in Appendix A. Here, we present the essence of themethod. For a policy z ∈ A , the notion of a z-tree plays a critical role in the computation. From thestandard definition in graph theory, a (directed) tree on A is a set of |A | − 1 transitions (directededges) with three properties: (i) exactly one policy, called the root of the tree, has no exitingtransition; (ii) all policies but the root have exactly one exiting transition; and (iii) for any policy
9 Players prefer the status quo a if u(a) = u(a0 ). Note that the assumption of strict preferences implies that u (a) =iui (a0 ) if and only if a = a0 . Our result is not affected by the choice in this case.

10

a₁

a₁

13

a₃ 0 a₂

0

12

a₄

13

a₃ 0 a₂(a) a2 -tree0a₄(b) a1 -tree

Figure 2: A non-q-majority a2 -tree and a q-majority a1 -tree
there is a unique path to the root.10 If a tree has a root z ∈ A , we call it a z-tree. For each transitionof the z-tree, we determine the minimum number of mistakes needed for the transition to occur.
This number is called the transition cost, and is a measure of how unlikely the transition is to occur.
The cost of a z-tree is defined as the sum of all transition costs within the tree. A policy z ∈ A is
stochastically stable if and only if it has a z-tree with the smallest cost over A .

4

The Long-Run Equilibrium: Condorcet Winner and TopCycle

In this section, we characterize stochastically stable policies under a q-majority. The analysis isrestricted to an interesting case of q ∈ {q, . . . , n}. It is useful to introduce the notion of a qmajority tree.11 A q-majority tree is a tree on the policy space A , where each transition has zero
cost under the q-majority. That is, z-tree for z ∈ A , say τz , is a q-majority tree if n(a0 , a00 ) ≥ q, forall (a0 , a00 ) ∈ τz . Every transition of a q-majority tree is preferred by at least q voters. The root of aq-majority tree can be reached from any other policy, with no mistakes, by repeating the q-majority
voting. We focus on q-majority trees with q = q. The next example illustrates q-majority trees.
Example 2. Recall the collective choice problem in Example 1, where 25 voters choose from 4
policies {a1 , . . . , a4 }. Recall also that q = 13, and a1 is the Condorcet winner. Figure 2(a) shows an
a2 -tree, and Figure 2(b) shows an a1 -tree. An arrow from a j to ah denotes a transition from a j toah . A number associated with an arrow indicates the number of voters who oppose the transition.
The a2 -tree in Figure 2(a) is not a q-majority tree because the edge (a1 , a2 ) has n(a1 , a2 ) =12 < q. The a1 -tree in Figure 2(b), obtained by replacing (a1 , a2 ) with (a2 , a1 ) in Figure 2(a), is aq-majority tree. The number of opposing voters is less than q for every edge in Figure 2(b).
The following lemma provides a necessary condition for a policy to be stochastically stable.
Lemma 1. Let q ≥ q. Every stochastically stable policy z∗ ∈ A under a q-majority must be theroot of some q-majority tree.
10 For example, Figure 2(a) shows a tree with four policies.
11 Our notion of a majority tree is similar to that of a complete path in Miller (1977).

11

Lemma 1 implies that, for every q-majority rule, a policy z∗ is stochastically stable only if z∗
can be reached from any policy z under the q-majority rule through a sequence of pairwise voting.
Let q ∈ {q, . . . , n}. Intuitively, suppose z∗ is not the root of any q-majority tree. Then, there is somepolicy, say z, from which z∗ cannot be reached, with no mistakes, under the q-majority using any
sequence of pairwise voting. It can be shown that z is more likely to be enacted than z∗ . To see this,choose a z∗ -tree that minimizes the cost among all possible z∗ -trees. The chosen z∗ -tree must havea transition, say (z, z0 ), that is not supported by the majority, i.e. n(z, z0 ) < q. Its transition cost isq − n(z, z0 ) > q − q. Note that the transition cost of (z, z∗ ) is greater than or equal to that of (z, z0 );that is, q − n(z, z∗ ) ≥ q − n(z, z0 ). Otherwise, we can form a z∗ -tree with a strictly smaller cost by
replacing (z, z0 ) with (z, z∗ ). We construct a z-tree by replacing (z, z0 ) with (z∗ , z). The transition
cost of (z∗ , z) is at most q − q. Then, the cost of the z-tree is strictly smaller than that of the z∗ -tree,
which contradicts that z∗ is stochastically stable under a q-majority.
We can now state our main result. The proof is given in Appendix B.
Theorem 1. The Condorcet winner is uniquely stochastically stable under the BRM for all q ≥q.1213
The theorem is straightforward for the simple majority voting, where the Condorcet winner canbe reached, without error, from any other policy under the simple majority. In contrast, every otherpolicy can be reached from the Condorcet winner only when at least one voter makes a mistake.
Thus, the Condorcet winner is the unique long-run equilibrium under a simple majority.
An important finding of Theorem 1 is that the Condorcet winner is uniquely stochasticallystable for all majority rules, including unanimity. When q is a super-majority rule, the Condorcet
winner may not always win the super majority. For example, the core C(q) may include policies
other than the Condorcet winner; that is, many policies may be undefeated under the q-majority.
If enacted, such a policy remains as the status quo, as long as voters make no errors. However, theCondorcet winner aCW is the only policy to be a long-run equilibrium, even under a super majority
rule. Intuitively, any a-tree for a 6= aCW has a transition exiting from aCW . The transition is notpreferred by a majority and, thus, it is impossible for any a 6= aCW to be the root of a q-majority
tree. Therefore, by Lemma 1, any policy other than the Condorcet winner cannot be a long-run
equilibrium under any q-majority rule.
Theorem 1 implies the following. In the literature on social choice theory, the core has frequently been studied as a set of stable majority voting outcomes. The core expands as the voting
12 When the Condorcet winner does not exist, we can prove a weak version of Theorem 1: When n is even, a weak
Condorcet winner a∗ satisfying n(a0 , a∗ ) ≥ n/2, for all a0 6= a∗ , is stochastically stable under every q-majority.
13 If we allow q < q, such majority voting rules actually describe minority rules in which a challenging policy is
selected if a minority group of players prefer it. The Condorcet winner is uniquely stochastically stable even undersuch minority rules as long as q > n.

12

Probability distribution on the Condorcet winner and a₂
ε=0.01ε=0.03ε=0.03ε=0.01Time

Figure 3: Probability of the Condorcet winner a1 (solid line) and a2 (dashed line)
quota increases. In particular, the core under the unanimity rule (the largest quota) coincides withthe set of Pareto efficient policies. When the core includes multiple policies, the outcome of majority voting is indeterminate. This is sometimes called the indeterminacy problem (Caplin andNalebuff 1988). Theorem 1 shows that the stochastic evolutionary theory resolves the indeterminacy problem in that the Condorcet winner is uniquely selected as a long-run equilibrium in a
dynamic voting process.
Example 3. Recall the collective choice problem in Example 1, where 25 voters choose from 4
policies {a1 , . . . , a4 }. Recall also that q = 13. Thereom 1 implies that the Condorcet winner a1 is
the unique long-run equilibrium under every q-majority rule with q ≥ 13.
The intuitive reasoning behind the result for unanimity (q = 25) is as follows. Recall Figure
2 in Example 2, where the number associated with an arrow indicates the number of voters who
oppose the transition. This number is actually the transition cost under unanimity (i.e., the numberof mistakes required for the transition to occur). The likelihood of a transition decreases as thenumber of opposing voters increases. A long-run equilibrium policy must be the root of a tree thatminimizes, among all trees, the sum of the opposing voters associated with its transitions.
The a2 -tree in Figure 2(a) minimizes the number of the opponents among all a2 -trees. It is,however, not a q-majority tree as discussed in Example 2. The a1 -tree in Figure 2(b) is a q-majority
tree that minimizes the number of opponents among all trees.
Figure 3 shows the dynamics of the probability of the Condorcet winner a1 and another policy
a2 for ε ∈ {0.01, 0.03}. The quota is q = 15. All four policies are equiprobable in the initial
distribution. The probability of a1 increases over time for both error rates while the probability of13

a2 first increases rapidly and then gradually decreases. It is more likely for the process to moveto a2 when the initial state is a3 or a4 . It explains the initial increase of the probability of a2 .
The probability of a2 , however, decreases afterwards because more voters prefer a1 to a2 — thetransition from a2 to a1 is more likely than the opposite transition. Figure 3 illustrates that society
eventually implements the Condorcet winner a1 for both error rates. Note that the probabilityof a1 will never reach one, owing to the error probability ε > 0. As implied by Theorem 1, theprobability converges to one as ε vanishes.
Theorem 1 assumes the Condorcet winner exists. We now consider a general case where theCondorcet winner may not exist. The set of long-run equilibria depends on a voting quota q. Let
Aqtc be the top cycle under the q-majority, and let Mq (Aqtc ) be the set of stochastically stablepolicies when the policy space is restricted to Aqtc and the voting rule is the q-majority.
Proposition 1. For all q ≥ q, a policy z∗ is stochastically stable under a q-majority if and only ifz∗ ∈ Mq (Aqtc ).
According to this proposition, we can restrict the policy space to Aqtc to characterize the longrun equilibrium for every q-majority with q ≥ q. When q = q, every policy in the top cycle Aqtc canbe reached without error from any other policy. Thus, all policies in Aqtc are long-run equilibria,
whereas those outside Aqtc are not. When q > q, policies in Aqtc may not be reached without error
from policies outside Aqtc . For example, some policies outside Aqtc may be in the core C(q) whenq > q. Replacing such polices will incur positive transition costs. Nevertheless, we can ignore
such policies to compute a stochastically stable policy, as shown in the following example.
Example 4. Consider a collective choice problem with 25 voters and four policies. The voters’
preferences are summarized in Table 2. Observe that q = 13 and Aqtc = {a1 , a2 , a3 }. Suppose
Table 2: Preference and voting matrices of 25 voters and four policies
Preferencesa1  a4  a2  a3a2  a3  a4  a1a3  a1  a2  a4

# of players
8
6
11

a1
a2
a3
a4

a1 a2
− 19
6 −
17 11
6 8

a3 a4
8 19
14 17
− 17
8 −

q = 20, i.e. four-fifth majority votes. The cost of a transition is given by 20 minus the numberof voters supporting the transition. The stochastically stable policy with the state space Aqtc is
a3 . Proposition 1 implies that a3 is the stochastically stable policy with the original state space
A = {a1 , . . . , a4 }.
To see this, observe that {(a2 , a1 ), (a3 , a2 ), (a4 , a1 )} is the a1 -tree with the minimum costamong all a1 -trees. Similarly, {(a1 , a3 ), (a3 , a2 ), (a4 , a1 )} is the a2 -tree with the minimum cost14

ε=.02, a3
ε=.01, a1

ε=.01, a3

ε=.02, a1

Figure 4: Probability of stochastically stable policy a3 (solid line) and other policies (dashed line)
for q = 20
among all a2 -trees, and {(a1 , a3 ), (a2 , a1 ), (a4 , a1 )} is the a3 -tree with the minimum cost among
all a3 -trees. Because all trees include the same transition (a4 , a1 ), the difference in costs between
these minimum-cost trees does not change, even if we remove policy a4 from the state space. For
example, the costs of the a1 -tree and the a3 -tree are 8 and 5, respectively. If we exclude a4 , thecosts change to 7 and 4, respectively, but the difference remains the same.
Figure 4 shows the dynamics of the probability of the four policies for q = 20 and ε ∈{0.1, 0.2}. a3 (solid line) is uniquely stochastically stable for q = 20. All four policies areequiprobable in the initial distribution. The probability of a1 has a rapid increase in initial periods. This is due to that the transitions from a2 and a4 to a1 are the most likely. The probabilityof a1 , however, keeps decreasing after that, and the probability eventually accumulates on thestochastically stable policy a3 for both error probabilities.
Proposition 1 has two implications. First, it shows the robustness of the long-run equilibria.
The top cycle Aqtc does not change, even if we add policies to A that are defeated by every a ∈Aqtc . Second, it simplifies the computation of a long-run equilibrium. In general, it is bothersome
but necessary to consider transition costs for all policies outside Aqtc . However, this proposition
implies that it is sufficient for us to compute transitions between policies in Aqtc .

15

5Multidimensional Policy SpaceWe assume a collective choice problem where policies are in the h-dimensional Euclidean space
Rh . With this additional assumption, we can further characterize stochastically stable policies
beyond Proposition 1. For a policy a ∈ Rh and i = 1, · · · , h, the i-th coordinate of a represents
its position on the i-th issue. Every voter has a Euclidean preference over policies; each playeri ∈ N has an ideal point, denoted as si ∈ Rh , and he/she prefers policies closer to the ideal point.
Formally, player i’s utility function ui satisfies ui (a) > ui (a0 ) if and only if d(a, si ) < d(a0 , si ), whered(a, b) denotes the (Euclidean) distance between a and b. The Euclidean preference generalizes
the “single-peaked” preference of Black (1948). Here, n and C∗ denote the min-max quota andthe min-max set, respectively, in Rh . That is, n = minr∈Rh maxr0 ∈Rh n(r, r0 ) and C∗ = {r ∈ Rh :maxr0 ∈Rh n(r, r0 ) = n}.
To apply our stochastic evolutionary theory, we approximate Rh by a finite subset of itself. Let
A 0 ⊂ Rh be a bounded convex set. Let A δ ⊂ A 0 be a finite approximation of A 0 , with maximum distance δ > 0; that is, for every r ∈ A 0 , there exists some a ∈ A δ such that d(a, r) < δ .
We consider a long-run equilibrium when the finite space A δ approximates Rh well. Specifically, we characterize stochastically stable policies over A δ when A 0 is sufficiently large and theapproximation δ converges to zero.
In our analysis, we assume that (i) si ∈ A 0 , for all i ∈ N; and (ii) A δ ∩ C∗ 6= 0.
/ The
∗
h
0
first assumption ensures that the min-max set C defined over R is included in A . The second assumption means that the approximation is sufficiently fine that some point of the minmax set C∗ is included in A δ . For A δ , we define the min-max quota and the min-max set asnδ = mina∈A δ maxa0 ∈A δ n(a, a0 ) and A mm,δ = {a ∈ A δ : maxa0 ∈A δ n(a, a0 ) = nδ }, respectively.
Lemma B.4 in the Appendix shows that any pair of policies can be connected via a sequence of
pairwise voting under a q-majority if A 0 is sufficiently large and δ is sufficiently small. This suggests that the top cycle Aqtc can be arbitrarily large, and that Proposition 1 barely helps characterizestochastically stable policies. Nevertheless, the next theorem characterizes the set of stochasticallystable policies for all q-majority rules, where q ∈ {q, · · · , n}.
Theorem 2. Fix any ρ > 0, and let Bδ (ρ) = {a ∈ A δ : kak < ρ}.
(i) For q ≤ n, every a ∈ Bδ (ρ) is stochastically stable for every sufficiently small δ and every
sufficiently large A 0 .
q(ii) For q > n, limδ →0 limε→0 πε (A mm,δ ) = 1 for every sufficiently large A 0 .
The theorem shows the following properties of the long-run equilibrium when the policy spaceis multidimensional. The set of stochastically stable policies differs, depending on whether q ≤ n.
When q ≤ n, every policy in an arbitrarily large open ball Bδ (ρ) is stochastically stable, provided
that an approximation of the policy space is sufficiently large and fine. Intuitively, every policy
16inside such an open ball is in the top cycle under a q-majority, and thus can be connected via
zero-cost transitions. When q > n, the set of stochastically stable policies is approximately equal
to the min-max set A mm,δ . The result generalizes Theorem 1 to the context of multidimensional
policy spaces. If the Condorcet winner aCW exists, then n < n/2. Thus, A mm,δ = {aCW }, for everyq ≥ n/2 and every δ .
Theorem 2 has the following implications for the two issues of intransitivity and indeterminacy
related to majority voting. In general, there is a trade-off between intransitivity and indeterminacy.
When q ≤ n, the social preference order under the q-majority rule violates transitivity (McKelvey,1976). As a result, intransitivity occurs; the q-majority core does not exist and all policies are in the
top cycle under q-majority. When q > n, the intransitivity of majority voting is mitigated, because
the q-majority core includes at least the min-max policies. However, as the quota becomes larger,
we face indeterminacy, because the core may include many policies. In fact, the q-majority coreis, in general, larger than the min-max set for all q > n + 1. To overcome both issues, we shouldskillfully choose q = n + 1, such that the core exists and its size is a minimum; in this case, the core
coincides with the min-max set A mm,δ . Caplin and Nalebuff (1988) show that it is safe to choose
q = .64n to avoid intransitivity. The problem is that n/n ≈ .64 is the worst case, and the min-max
quota n may be much lower than 64% of n. As a result, many consider that, in such cases, choosing
q = .64n will aggravate indeterminacy. Theorem 2 (ii) implies that stochastic evolutionary theory
resolves the indeterminacy of majority voting in that only policies in the min-max set can be longrun equilibria for all q ≥ n + 1.
The next corollary follows immediately when Theorem 2 is applied to the unidimensional case.
The result corresponds to the mean voter’s theorem of Black (1948).
Corollary 1. Let s∗ be the mean voter’s ideal point in a unidimensional problem (h = 1), and letqn be an odd number. Then, limδ →0 limε→0 πε (s∗ ) = 1, for every q ≥ q and every sufficiently large
A 0.
Finally, we give an example that shows the min-max set for a multidimensional policy space.
Example 5 (min-max sets). Figure 5(a) shows the min-max set (the gray area) for a collective
choice problem with three players and a policy space on R2 . The players’ ideals points are depictedby s1 , s2 , and s3 . Note that the min-max quota is n = 2. The min-max set coincides with the convex
hull of the ideal points. For any policy outside the min-max set, there is a policy that n + 1 players
strictly prefer. For example, three players strictly prefer a2 to a1 in Figure 5(a). By contrast, atleast n − n players vote against any move from a policy within the min-max set. For example, theplayer with s1 votes against the move from a3 to a4 .
Figures 5(b) and 5(c) show the min-max sets for settings with four and five players, respectively. Note that n = 2 for the four-player setting, and n = 3 for the five-player setting. These
17

a₁

S₁

a₂

a₃
S₂

S₁

S₃
a₄

S₁

S₄

S₄
S₃

S₃
S₂

(a) 3 players

minmax set

S₂(b) 4 players

S₅(c) 5 players

Figure 5: The min-max sets
min-max sets are the intersection of the convex hulls of all n + 1 players’ ideal points. In the fourplayer setting, the min-max set is the intersection of the diagonals. This point is not a Condorcet
winner, but is undefeated under the simple majority q = 3. Our result shows that a dynamic processof majority voting with q ≥ 3 will choose this unique undefeated policy in the long run.

6

Logit Choice and Borda WinnerThus far, we have characterized stochastically stable policies of the BRM. However, because thebehavior of boundedly rational players is diverse, and cannot be described by a unique choicemodel, it is important that we examine how the choice rule affects the set of stochastically stablepolicies. Here, we examine the well-documented logit choice as an alternative choice rule forboundedly rational individuals.
Following Blume (1993), suppose that players employ the logit choice rule with noise levelη > 0. Given the status quo a and a proposal a0 , the choice probability of voting for a0 is given byΨηj (a, a0 ) =exp(η −1 u j (a0 )).
exp(η −1 u j (a0 )) + exp(η −1 u j (a))(3)

The logit choice rule can be derived from a random utility model in which the utility for eachpolicy is perturbed by i.i.d. random variables with the Gumbel distribution. The distribution isbell-shaped, and is similar to a normal distribution. This choice rule is amenable to computation,
and approximates a random utility model with normally distributed noise.
For two policies a and a0 , the transition probability from a to a0 under the logit choice ruleη,qis given by replacing the BRM choice rule Ψεj with the logit function Ψηj . Let Pa,a0 denote theqη,qtransition probability with Ψηj (a, a0 ), and let πη be the stationary distribution under P·,· . We
define the stochastic stability for the logit choice rule in the same manner as that for the BRM. A
qpolicy z is stochastically stable under a q-majority with the logit choice if limη→0 πη (z) > 0.

18

For the logit choice, it is known that the unlikeliness of a player i’s choice is given by14ci (a, a0 ) = − lim η log Ψηi (a, a0 ) = max{ui (a) − ui (a0 ), 0}.
η→0The transition cost from a to a0 under a q-majority is given asq

caa0 = min ∑ max{ui (a) − ui (a0 ), 0},J∈Nq i∈J(4)qwhere Nq denotes the set of subsets of N with size q. The cost caa0 represents the unlikeliness ofthe transition (a, a0 ). That is, the unlikeliness is the smallest sum of the payoff deficits for q players
whose acceptance is needed for proposal a0 to win.
Stochastic stability under the logit choice favors the utilitarian social welfare function. The next
theorem shows that every stochastically stable policy of the logit choice rule under the unanimity
rule maximizes the social welfare function P(a) (i.e., the sum of all players’ utilities).15
Theorem 3. Let P(a) ≡ ∑i∈N ui (a), for all a ∈ A . A policy is stochastically stable under theunanimity rule with the logit choice if and only if it maximizes P(·) among all policies.
We introduce the Borda winner, which is based on a voting scoring method. Each player
ranks the policies in order of his/her preferences. The rankings are converted into points; a policy
receives one point for being ranked last, two for being next-to-last, and so on, up to |A | points forbeing ranked first. The Borda winner is the policy with the highest total score.
A maximizer of the social welfare function may correspond to the winner in some voting
scoring methods, depending on the players’ preferences. Specifically, when the players’ utility
scores for policies are linearly increasing with their rankings, a policy is a long-run equilibrium if
and only if it is a Borda winner.
Corollary 2. Suppose that every player has linear preferences over all policies, in increments ofone, according to his preference order; that is, ui (a) ∈ {1, 2, . . . , |A |}, for all i ∈ N and a ∈ A .
The set of stochastically stable policies of the logit choice under the unanimity rule coincides withthe set of Borda winners.
This contrasts with the result of Theorem 1, which shows the stochastic stability of the Condorcet winner under the BRM for all majority rules. The Borda winner can emerge as a long-run
equilibrium if the logit choice better captures the behavior of boundedly rational voters. This result provides a dynamic foundation for the Borda winner. Suppose a society in which policies are
14 See Alós-Ferrer and Netzer (2010), for example. See also Sawa (2014) for the unlikeliness of joint deviations.
15 The result resembles that of Kandori et al. (2008), who study exchange economies. They show that an allocationthat maximizes the sum of utility functions is stochastically stable under the logit choice.

19

formed under the unanimity rule; that is, everyone has an equal right of veto. Here, the Borda
winner would be selected in the long run in this hypothetical society, provided that those withlinear preferences follow the logit choice. The Borda method can be viewed as a mechanism for
implementing such a long-run equilibrium.

7

Conclusion

We have considered a dynamic policy-making process, where a status quo policy is repeatedly
challenged by an opposing policy. Our analysis is based on stochastic evolutionary game theory.
We have shown that the Condorcet winner is a unique long-run equilibrium for all majority rules.
When the policy space is multidimensional, a long-run equilibrium under (super-)majority voting
must belong to the min-max set if the voting quota q is larger than the min-max quota. The stochastic evolutionary game theory provides new insight into the theory of social choice. Specifically,
the theory mitigates the indeterminacy problem of majority voting.
To conclude the paper, we comment on the limitations of our research, and offer possible
directions for future work. A voting rule is given exogenously in our model. Thus, it would be interesting to study an endogenous choice of voting rules from an evolutionary perspective.16 Voters
are myopic and their choices do not include strategic considerations. Although these assumptions
are common in the literature on evolutionary game theory, they are restrictive. A more elaboratemodel of boundedly rational voting should be developed in collaboration with behavioral and experimental economics. It may be worthwhile combining our model with empirical behavioral error
models, such as those of Lim and Neary (2016), Mäs and Nax (2016), and Hwang et al. (2018).
Finally, a further comparative study of normative and evolutionary approaches to the theory ofsocial choice is worth studying.

Appendix A
Transition Probabilities in the Dynamic Process
Recall that Eq. (1) is the players’ choice rule when they make no error, and Eq. (2) is their rule0,qwhen their choices are stochastic. Let Pa,a0 denote the transition probability from a to a0 under aq-majority when the choice rule is Eq. (1). Let pa,a0 be the probability that a proposal a0 ∈ A is
16 A few studies have examined endogenous voting rules (see Barbera and Jackson (2004) and Aghion et al. (2004)).

20

0,q

made against the status quo policy a. Then, Pa,a0 can be expressed as follows:
0,q

Pa,a0 =


p

a,a0

0

if n(a, a0 ) ≥ q,∀a, a0 ∈ A with a 6= a0 .

otherwise.
0,q

(A.1)

0,q

The probability of remaining with the status quo a is Pa,a = 1 − ∑a0 6=a Pa,a0 . We call the Markov
0,qchain P0,q = (Pa,a0 ) an unperturbed process under a q-majority.
Let θ ⊆ A . Here, θ is a recurrent class of the unperturbed process P0,q under a q-majority if
it satisfies the following conditions:0,q1. For all a1 , ak ∈ θ , there exists a sequence of policies {a1 , . . . , ak } ⊆ θ , such that Pai ,ai+1 > 0,
for all i ∈ {1, . . . , k − 1}.
0,q2. For all a ∈ θ and a0 ∈ A \ θ , Pa,a0 = 0.
As mentioned in the text, the set of recurrent classes coincides with the myopic stable set MSSq
(Theorem 3.16 of Demuynck et al. 2019). We have the following result for top cycles (the proof isomitted).
Lemma A.1 (Top cycle and recurrent class).
(i) A top cycle under a q-majority is a unique recurrent class of the unperturbed process P0,q .
(ii) For every q ≤ q, the unperturbed process P0,q has a unique recurrent class.
Let Pa,a0 denote the transition probability from a to a0 under a q-majority when the choice ruleε,qis Eq. (2). We call the Markov chain Pε,q = (Pa,a0 ) a perturbed process under a q-majority. Let mbe the number of voters who prefer a policy a0 to the status quo a. Then, the transition probabilities
are expressed as follows:
ε,q

n

m

Pa,a0 = pa,a0 ∑ ∑ C(m, j)C(n − m, k − j)(1 − ε) j ε m− j ε k− j (1 − ε)n−m−(k− j) ,
ε,q

(A.2)

k=q j=0

where C(K, k) denotes the number of k-combinations from K elements. We use the convention that
C(K, k) = 0 if k < 0. Because every player votes for a proposal with positive probability, we needto sum the probabilities of all events in which at least q players vote for the proposal. Rather thanconsidering the exact probabilities, we focus on the highest power of ε for each probability.

The Computation Method
The key computation method for long-run equilibria was developed as part of stochastic evolutionary game theory (Foster and Young, 1990; Kandori et al., 1993; Young, 1993). We first define
21the notion of a transition cost from one policy to another, which measures the unlikeliness of thetransition occurring. The transition cost from a to a0 under a q-majority is defined asq

caa0 = max{q − n(a, a0 ), 0}.

(A.3)
q

Recall that n(a, a0 ) is the number of players who prefer a0 to a. The transition cost caa0 frompolicy a to a0 under a q-majority is the minimum number of mistakes (“mutations,” in evolutionary
terminology) required for at least q players to vote for a0 . Some of these players may not prefera0 to the status quo a, but they may accept proposal a0 “by mistake.” If this is the case, then theqtransition cost caa0 will be positive, and equal to the minimum necessary number of mistakes. If qqplayers who prefer a0 to a exist, then caa0 is zero.
For two policies a and a0 , we denote the transition from a to a0 as notation (a, a0 ). We call a setof transitions {(a1 , a2 ), (a2 , a3 ), . . . , (aL−1 , aL )} a path from a1 to aL on A if ai 6= a j , for all i 6= j.
Note that any transition (ai , ai+1 ) may occur with a positive probability under a perturbed process.
For a ∈ A , we call a set of transitions, denoted as τa , an a-tree if there exists a unique path froma0 to a for all a0 ∈ A , with a0 6= a. Let ϒa denote the set of all a-trees. Given an a-tree τa and amajority quota q, we define the cost of the a-tree τa as
cq (τa ) =∑ cqvw.

(A.4)(v,w)∈τa

We define c∗q (a) as the lowest cost from among all a-trees, and define m∗q as the minimum of c∗q (a)from among all policies a in A . That is,c∗q (a) = min cq (τa ),m∗q = min c∗q (a).

τa ∈ϒaa∈A(A.5)

Define
Mq = a ∈ A : c∗q (a) = m∗q .

(A.6)

The following theorem is proved by Kandori et al. (1993) and Young (1993) in our context.
Theorem A.1. A policy a ∈ A is stochastically stable if and only if a ∈ Mq .
The theorem states that a policy is stochastically stable if and only if a tree with itself as theroot has the minimum cost among all trees. An implication of this is that a stochastically stablepolicy a ∈ A under a q-majority must belong to a recurrent class of the unperturbed process. If a
is not in any recurrent class, then there exists a path from a to some recurrent class with zero cost.
The cost of any a-tree must be greater than that of a b-tree, for every policy b in the recurrent class.
22

Appendix B
Proofs of Analytic Results
Recall that a tree τa for a ∈ A is q-majority tree if n(a0 , a00 ) ≥ q, for all (a0 , a00 ) ∈ τa .
Proof of Lemma 1. Fix q ≥ q. Assume that a ∈ A is stochastically stable under a q-majority. By
way of contradiction, suppose that a has no q-majority a-tree. Then, for every a-tree τa , there
exists some transition (a0 , a00 ) ∈ τa , such that n(a0 , a00 ) < q. If n(a0 , a) ≥ q, for all such transitions(a0 , a00 ) in τa . Then, one can construct a q-majority a-tree by replacing all such (a0 , a00 ) with (a0 , a).
This contradicts the supposition. If there exists some transition (a0 , a00 ) ∈ τa such that n(a0 , a00 ) < q
and n(a0 , a) < q, then remove (a0 , a00 ) from τa , and add (a, a0 ). The resulting set of edges must be
an a0 -tree, denoted as τa0 . From (7), its cost is given bycq (τa0 ) = cq (τa ) − (q − n(a0 , a00 )) + max{q − n(a, a0 ), 0}.
Note that q − n(a0 , a00 ) > 0, because q ≥ q > n(a0 , a00 ). Observe thatq − n(a0 , a00 ) > q − q ≥ q − n(a, a0 ).
The final inequality holds because n(a0 , a) < q implies n(a, a0 ) ≥ q. Then, we have cq (τa0 ) < cq (τa ).
This contradicts that a is stochastically stable under the q-majority.
Proof of Theorem 1. Suppose that a Condorcet winner aCW exists. It is easy to see that any a 6= aCW
has no q-majority a-tree. Any a-tree must include a transition from aCW , say (aCW , a0 ). Becausen(aCW , a0 ) < q, any a 6= aCW has no q-majority a-tree. Then, Lemma 1 implies the claim.
We prove Proposition 1. Lemma A.1 shows that if a quota q is not greater than q, then theunperturbed process has a unique recurrent class that coincides with the top cycle. This proves theclaim of Proposition 1 for q = q. Thus, we focus on the claim of Proposition 1 for q > q. Recall
that Aqtc is the top cycle under a q-majority. Let ϒa (Aqtc ) denote the set of a-trees over Aqtc , anddefinec∗q,Aqtc (a) =minτa ∈ϒa (Aqtc )cq (τa ),c∗q,Aqtc = mintc c∗q,Aqtc (a),a∈Aq

Mq (Aqtc ) = {a ∈ Aqtc : c∗q,Aqtc (a) = c∗q,Aqtc }.
We first prove Lemmas B.1 and B.2. The former shows that if a policy a is stochastically stablefor quota q > q, a must be in the top cycle under the q-majority; that is, a ∈ Aqtc . The latter shows23

that any minimum cost tree of stochastically stable policies has no edge emanating from somepolicy in Aqtc to one not in Aqtc .
qLemma B.1. limε→0 πε (a) > 0 for q > q only if a ∈ Aqtc .
qProof. By way of contradiction, suppose that πε (a) > 0 for a ∈/ Aqtc . Note that n(a, a0 ) = n −n(a0 , a) > n − q, for all a0 ∈ Aqtc , because a ∈/ Aqtc implies that n(a0 , a) < q, for a0 ∈ Aqtc .
Let τa be an a-tree minimizing its cost; that is, cq (τa ) = m∗q . Choose (a0 , a00 ) ∈ τa such thata0 ∈ Aqtc and a00 ∈/ Aqtc . Such an edge must exist because the root of τa is not in Aqtc . Remove(a0 , a00 ) from τa . This will reduce the cost of τa by at least q − (q − 1), because n(a0 , a00 ) < q fora0 ∈ Aqtc and a00 ∈/ Aqtc . Then, add an edge (a, a0 ) to τa . This will increase the cost by q − n(a, a0 ),which is at most q − q. The resulting tree is an a0 -tree with a cost strictly less than cq (τa ). This
contradicts that cq (τa ) = m∗q .
Lemma B.2. Suppose that a ∈ A is stochastically stable with q > q. Let τa be such that cq (τa ) =m∗q . If a0 ∈ Aqtc and (a0 , a00 ) ∈ τa , then a00 ∈ Aqtc .
Proof. Observe that Lemma B.1 implies that a ∈ Aqtc . By way of contradiction, suppose there
exists (a0 , a00 ) ∈ τa , such that a0 ∈ Aqtc and a00 ∈/ Aqtc . Because a00 ∈/ Aqtc , n(a0 , a00 ) < q. Removeedge (a0 , a00 ) from τa . This will reduce the cost of τa by at least q − q + 1. Let τa1 denote theresulting set of edges.
If n(a0 , a) ≥ q, add edge (a0 , a) to τa1 . This will increase the cost by at most q − q. The resulting
set is an a-tree, say τa2 . Observe that cq (τa2 ) ≤ cq (τa ) − (q − q + 1) + q − q = cq (τa ) − 1.
If n(a0 , a) < q, it must be that n(a, a0 ) ≥ q. Add edge (a, a0 ) to τa1 . This will increase the costby at most q − q. The resulting set is an a0 -tree, say τa0 . Observe that cq (τa0 ) ≤ cq (τa ) − (q − q +1) + q − q = cq (τa ) − 1. These observations contradict that cq (τa ) = m∗q .
Now, we are ready to prove Proposition 1.
Proof of Proposition 1. Let τa be an a-tree over A . We say that τa has an a-subtree over a subset
A 0 ⊂ A if, for all a1 ∈ A 0 , there exists a path {a1 , . . . , ak } ⊆ τa , such that ak = a and ai ∈ A 0 ,for all i ∈ {1, . . . , k}. Lemma B.1 implies that a ∈/ Aqtc cannot be stochastically stable. Lemma B.2
implies that if a is stochastically stable, for q > q, then τa minimizing cq (·) must have an a-subtree
over Aqtc . The proof for each part is conducted by way of contradiction.
“only if” part: Suppose that a ∈ Aqtc \ Mq (Aqtc ) is stochastically stable. Let τa be the minimum
cost tree for a. Lemma B.2 implies that τa has an a-subtree over Aqtc , say τa] .
Let b ∈ Mq (Aqtc ), with τb] a b-subtree over Aqtc , such that cq (τb] ) = c∗q,A tc . Replace τa] with τb]qin τa . The resulting set of edges, say τb∗ , must be a b-tree. Observe thatcq (τb∗ ) = cq (τa ) − cq (τa] ) + cq (τb] ) < cq (τa ).
24

The inequality comes from the fact that a ∈/ Mq (Aqtc ). This contradicts that cq (τa ) = m∗q .
“if” part: Suppose that a ∈ Mq (Aqtc ) is not stochastically stable. Let τa] be an a-subtree over Aqtc ,such that cq (τa] ) = c∗q,A tc . Let a0 be some stochastically stable policy with a minimum cost tree τa0 .
q

Lemmas B.1 and B.2 imply that τa0 has an a0 -subtree over Aqtc , say τa]0 . Replace τa]0 with τa] in τa0 .
The resulting set of edges is an a-tree, say τa∗ . Observe thatcq (τa∗ ) = cq (τa0 ) − cq (τa]0 ) + cq (τa] ) ≤ cq (τa0 ) = m∗q .
Then, Theorem A.1 suggests that a is stochastically stable, which is a contradiction.
For the multidimensional choice problems in Section 5, let d(a, A0 ) = infa0 ∈A0 d(a, a0 ), for a ∈A 0 and A0 ⊂ A 0 , that is, the distance between a point and a set. Let C∗,σ denote a σ -neighborhoodof C∗ ; that is, C∗,σ = {r ∈ Rh : infr0 ∈C∗ d(r, r0 ) < σ }.
The following lemma describes the limiting properties of the min-max quota and the min-max
set as the approximation δ goes to zero. The min-max set in the approximation space is includedin the neighborhood of the min-max core for sufficiently small δ .
Lemma B.3. (i) limδ →0 nδ = n. (ii) Fix σ > 0. A mm,δ ⊂ C∗,σ for all sufficiently small δ .
Proof of Lemma B.3. (i): By definition of n, it holds that n(a, a0 ) ≤ n, for a ∈ A δ ∩ C∗ and alla0 ∈ A δ \ {a}. This implies that nδ ≤ n. Suppose that limδ →0 nδ < n. Choose a ∈ A δ , suchthat limδ →0 n(a) = limδ →0 nδ < n. By the definition of n, there exists a0 ∈ A 0 , such that |i ∈ N :d(si , a0 ) < d(si , a)| ≥ n. Choose a00 ∈ A δ , with d(a0 , a00 ) < δ . By the continuity of d, we must havethat |i ∈ N : ui (a00 ) > ui (a)| ≥ n, for all sufficiently small δ . This contradicts that limδ →0 n(a) < n.
(ii): Because nδ takes only finite integers, (i) implies that n(a) = nδ = n, for all a ∈ A mm,δ andall sufficiently small δ . Suppose that δ is small enough that nδ = n.
It suffices to show that A mm,δ ∩(A 0 \C∗,σ ) = 0.
/ Choose r ∈ A 0 \C∗,σ . Note that d(r, C∗ ) ≥ σ .
Because r ∈/ C∗ , there exists some r∗ ∈ A 0 , such that |i ∈ N : ui (r∗ ) > ui (r)| ≥ n + 1. By thecontinuity of d, there exists aδ ∈ A δ , with d(r∗ , aδ ) < δ , such that |i ∈ N : ui (aδ ) > ui (r)| ≥n + 1, for all sufficiently small δ . Because the choice of r is arbitrary, this implies that, for all
r ∈ A 0 \ C∗,σ , r ∈/ A mm,δ , for all sufficiently small δ .
In what follows, we assume that δ is sufficiently small such that nδ = n. Lemma B.4 below
shows that any pair of policies can be connected via a sequence of pairwise voting under a qmajority if q ≤ n and A 0 is sufficiently large. McKelvey (1976) shows a similar result for an
infinite state space and the simple majority rule. We prove the result for a finite state space, where
opposing policies are selected only from A δ , and extend it to a q-majority for all q ≤ n.

25

Lemma B.4. For any ρ > 0, let B(ρ) = {r ∈ Rh : krk < ρ} and Bδ (ρ) = {a ∈ A δ : kak < ρ}.
Fix ρ > 0 such that it is sufficiently large that si ∈ B(ρ), for all i ∈ N. If A 0 is sufficiently largethat B(5ρ) ⊂ A 0 , then for all a1 , aL ∈ Bδ (ρ) and all sufficiently small δ , there exists a sequence{a1 , a2 , . . . , aL } ⊂ A δ , such that∀ j ∈ {1, . . . , L − 1}.

n(a j , a j+1 ) ≥ n

Proof of Lemma B.4. The algorithm of McKelvey (1976, Theorem 2) can be extended to all quotasq ≤ n. The algorithm implies that for every ak ∈ A δ , there exist ck > 0, rk+1 ∈ A 0 , yk ∈ Rh ,kyk k = 1, such that (i) krk+1 k2 − kak k2 ≥ c2k , (ii) u j (rk+1 ) > u j (ak ) if s0j · yk ≥ ck /2, and (iii) |{ j ∈N : s0j · yk ≥ ck }| ≥ q. Property (i) implies that rk+1 is further from the origin than ak is. Properties(ii) and (iii) together imply that at least q players prefer rk+1 to ak . Then, for all sufficiently small δ ,we can find ĉk ∈ (0, ck ) and ak+1 ∈ A δ , where krk+1 k − kak+1 k ≤ δ , such that kak+1 k2 − kak k2 ≥ĉ2k and u j (ak+1 ) > u j (ak ) if s0j · yk ≥ ĉk /2. This implies that ak+1 is preferred to ak by at least q
players. A successive application of the algorithm yields ak as far from the origin as required.
We show the upper bound of krk+1 k for given ak . Recall that rk+1 is preferred to ak by at leastq players. This implies that rk+1 ∈ B(3ρ) if ak ∈ B(ρ), and that rk+1 ∈ B(5ρ) if ak ∈ B(3ρ). For
the first case, observe that rk+1 will be at least 2ρ from si , for all i ∈ N, if rk+1 ∈/ B(3ρ). However,ak ∈ B(ρ) implies that ksi − ak k < 2ρ, for all i ∈ N. Then, for at least q players to prefer rk+1 , itmust be that rk+1 ∈ B(3ρ). Similarly, rk+1 will be at least 4ρ from all ideal points if rk+1 ∈/ B(5ρ),whereas ak ∈ B(3ρ) implies that ksi − ak k < 4ρ, for all i ∈ N.
Finally, we show that the process can reach aL ∈ A mm,δ . Let B∗ = B(5ρ) \ B(3ρ); that is, thedistance from any point in B∗ to any point in B(ρ) is at least 2ρ. Because the algorithm yields ak
as far as we need, we can pick a sequence {a1 , . . . , aL−1 }, such that aL−2 ∈ B(3ρ) and aL−1 ∈ B∗ .
The proof is complete by observing that n(aL−1 , aL ) ≥ q.
We next prove a result similar to Kramer (1977, Theorem 1’): Q(a) is the set of policies
that maximizes the number of votes against policy a, i.e., Q(a) denotes the set of the most likely
deviations from a. We first prove our version of Kramer (1977, Lemma 3).
Lemma B.5. Fix small δ > 0, such that nδ = n. Then, d(a, C∗ ) > d(a0 , C∗ ), for a ∈/ A mm,δ anda0 ∈ Q(a).
Proof of Lemma B.5. Suppose that a ∈/ A mm,δ and a0 ∈ Q(a). Let N(a, a0 ) = J. Let C(J) denotethe convex hull of the ideal points of the players in J. Because a is not in the min-max set,|J| ≥ n + 1. Define an open half space Va0 = {x ∈ Rh : d(x, a) > d(x, a0 )}. It must hold that
C(J) ⊂ Va0 . Otherwise, some player of J must prefer a to a0 , which contradicts the definition ofN(a, a0 ). If there exists b ∈ C∗ , such that b ∈/ C(J), then some policy in C(J) must be preferred to b
26

by all players in J, which contradicts that b ∈ C∗ . This implies that C∗ ⊆ C(J) ⊂ Va0 . This proves
the claim that d(a, C∗ ) > d(a0 , C∗ ).
The next lemma is our version of Kramer (1977, Theorem 1’).
Lemma B.6. For every a1 ∈/ A mm,δ , there exists a sequence {a1 , a2 , . . . , aL } ⊂ A δ with aL ∈A mm,δ , such that ai+1 ∈ Q(ai ), for all i = 1, . . . , L − 1.
Proof of Lemma B.6. Note that sequentially choosing ai+1 ∈ Q(ai ) must result in a cycle, owing
to the finiteness of A δ . Let {a1 , a2 , . . . , aL } denote such a cyclic sequence of policies; that is,ai+1 ∈ Q(ai ), for all i ∈ {1, . . . , L}, with a convention that aL+1 = a1 . We show that such a cycle
must include ai ∈ A mm,δ for some i.
By way of contradiction, suppose there exists a sequence {a1 , a2 , . . . , aL }, such that ai ∈/ A mm,δ ,for all i. Then, Lemma B.5 implies that d(ai , C∗ ) > d(ai+1 , C∗ ), for all i ∈ {1, . . . , L}; that is, thedistance between ai and C∗ is strictly decreasing as the sequence {a1 , a2 , . . .} progresses. Becaused(a1 , C∗ ) > . . . > d(aL+1 , C∗ ) implies that a1 6= aL+1 , which contradicts that the sequence is cyclic.
Note that the distance increases (d(ai , C∗ ) ≤ d(ai+1 , C∗ )) only if ai ∈ A mm,δ . By sequentiallychoosing ai+1 ∈ Q(ai ), the process must reach some ai ∈ A mm,δ .
Proof of Theorem 2. (i) : Suppose that q ≤ n. It suffices to show that the unperturbed dynamic
with state space A δ has a unique recurrent class that includes the open ball Bδ (ρ). Let C(N)denote the convex hull of all players’ ideal points. Lemma B.4 implies that all policies in Bδ (ρ)
are connected via zero-cost transitions, for all sufficiently small δ and all sufficiently large A 0 .
These policies must be in one recurrent class, say A ⊂ A δ . Assume that A 0 is sufficiently largethat C(N) ⊆ A. We show that there is no recurrent class other than A. Choose a0 ∈ A δ \ A. Leta∗ ∈ argminr∈C(N) d(a0 , r). Observe that ui (a∗ ) > ui (a0 ), for all i ∈ N. By the continuity of d, forsufficiently small δ , there exists â∗ ∈ A, with d(a∗ , â∗ ) < δ , such that ui (â∗ ) > ui (a0 ), for all i ∈ N.
The cost of the transition from a0 to â∗ is zero. Because the cost must be positive for transitions
between two recurrent classes, a0 cannot be in any recurrent class. This proves that A is the uniquerecurrent class.
(ii) : Suppose that q > n. Assume sufficiently small δ , such that nδ = n. By way of contradiction,
assume there exists a stochastically stable policy a1 ∈/ A mm,δ . Let τ1 denote the minimum costspanning tree rooted at a1 . We show that the minimum cost spanning tree rooted at some aL ∈A mm,δ has a strictly smaller cost than that of a1 .
Lemma B.6 implies that there exists a sequence {a1 , a2 , . . . , aL } ⊆ A δ , with aL ∈ A mm,δ , suchthat ai+1 ∈ Q(ai ), for all i ∈ {1, . . . , L − 1}. Construct a path of edges {(a1 , a2 ), . . . , (aL−1 , aL )}.

27

Add these edges to τ1 , replacing the existing edges exiting a2 , . . . , aL−1 . Remove the edge exiting
aL . The resulting set of edges must be an aL -tree, denoted as τL . Then, observe that
L−1L

cq (τL ) ≤ cq (τ1 ) + ∑ max{q − n(ai , ai+1 ), 0} − ∑ max{q − n(ai ), 0}
i=1

i=2

= cq (τ1 ) + max{q − n(a1 , a2 ), 0} − max{q − n(aL ), 0}(B.1)< cq (τ1 ) = m∗q .
The last term of the first inequality represents the cost reduction by removing the existing edges
a2 , . . . , aL−1 . The weak inequality holds because max{q − n(ai ), 0} is the smallest possible cost ofan edge exiting ai . The second equality holds because n(ai , ai+1 ) = n(ai ), from the definition of
the sequence {a1 , . . . , aL }. The last inequality holds because a1 ∈/ A mm,δ implies n(a1 , a2 ) > n =n(aL ). Thus, τL has a strictly smaller cost than τ1 , which contradicts that a1 is stochastically stable.
Therefore, no a1 ∈/ A mm,δ can be stochastically stable.
Proof of Theorem 3. Our setting for q = n is similar to the unanimity game studied in Sawa (2014).
The proof follows that of Proposition 4.6 in Sawa (2014). Using Eq. (4), define the cost of a treecq (·), cost of a policy c∗q (·), minimum cost m∗q , and set of policies with the minimum cost similarly
to Eq. (A.4)–(A.6), respectively. As with Theorem A.1 for the BRM, a policy is stochasticallystable under the logit choice if and only if it is in the set of policies with the minimum cost.
Observe that, for all a, a0 ∈ A ,P(a) − P(a0 ) = ∑ (ui (a) − ui (a0 )) = cnaa0 − cna0 a .

(B.2)

i∈N

It suffices to show that for every a1 and ak in A , P(a1 ) ≥ P(ak ) if and only if c∗n (a1 ) ≤ c∗n (ak ).
Let τk∗ be an ak -tree, such that cn (τk∗ ) = c∗n (ak ). Let d = {(a1 , a2 ), . . . , (ak−1 , ak )} be a path froma1 to ak in the tree τk∗ . We construct an a1 -tree, denoted as τ1 , from τk∗ by reversing the directionsof all edges on the path d, and keeping all other edges in τk∗ . Formally, let τ1 be such that(a0 , a00 ) if (a0 , a00 ) ∈ τ ∗ \ d,k
τ1 3
(a00 , a0 ) if (a0 , a00 ) ∈ d.
Observe thatc∗n (a1 ) ≤ cn (τ1 ) = cn (τk∗ ) +∑cnai+1 ai − cnai ai+1 = c∗n (ak ) + P(ak ) − P(a1 ).

(ai ,ai+1 )∈d

We use Eq. (B.2) in the second equality. The above equation shows that P(a1 ) ≥ P(ak ) implies28

c∗n (a1 ) ≤ c∗n (ak ).

References
Acemoglu, D., Egorov, G., and Sonin, K. (2011). Political model of social evolution. Proceedingsof the National Academy of Sciences, 108(Supplement 4):21292–21296.
Acemoglu, D., Egorov, G., and Sonin, K. (2012). Dynamics and stability of constitutions, coalitions, and clubs. American Economic Review, 102:1446–1476.
Agastya, M. (1999). Perturbed adaptive dynamics in coalition form games. Journal of Economic
Theory, 89:207–233.
Aghion, P., Alesina, A., and Trebbi, F. (2004). Endogenous political institutions. Quarterly Journalof Economics, 119:565–611.
Alós-Ferrer, C. and Netzer, N. (2010). The logit-response dynamics. Games and Economic Behavior, 68:413–427.
Anesi, V. (2010). Noncooperative foundations of stable sets in voting games. Games and Economic
Behavior, 70(2):pp.488–493.
Anesi, V. and Seidmann, D. J. (2015). Bargaining in standing committees with an endogenousdefault. Review of Economic Studies, 82:pp.825–867.
Arnold, T. and Schwalbe, U. (2002). Dynamic coalition formation and the core. Journal of Economic Behavior & Organization, 49:363–380.
Banks, J. S. and Duggan, J. (2005). Probabilistic Voting in the Spatial Model of Elections: The
Theory of Office-motivated Candidates, pages 15–56. Springer Berlin Heidelberg, Berlin, Heidelberg.
Barbera, S. and Jackson, M. O. (2004). Choosing how to choose: Self-stable majority rules andconstitutions. Quarterly Journal of Economics, 119:1011–1048.
Baron, D. P. (1996). A dynamic theory of collective goods programs. American Political Science
Review, 90:316–330.
Baron, D. P. and Ferejohn, J. A. (1989). Bargaining in legislatures. American Political Science
Review, 83:1181–1206.

29

Battaglini, M. and Coate, S. (2007). Inefficiency in legislative policymaking: A dynamic analysis.
American Economic Review, 97(1):pp.118–149.
Belloc, M. and Bowles, S. (2017). Persistence and change in culture and institutions underautarchy, trade, and factor mobility. American Economic Journal: Microeconomics, 9(4):245–
276.
Bendor, J., Diermeier, D., and Ting, M. (2003). A behavioral model of turnout. American Political
Science Review, 97(02):261–280.
Bilancini, E., Boncinelli, L., and Newton, J. (2020). Evolution and rawlsian social choice inmatching. Games and Economic Behavior, 123:68–80.
Binmore, K. G. (1994). Game Theory and the Social Contract. MIT Press, Cambridge, Mass.
Binmore, K. G. (2005). Natural Justice. Oxford University Press, New York.
Black, D. (1948). On the rationale of group decision-making. Journal of Political Economy,
56:23–34.
Blume, L. (1993). The statistical mechanics of strategic interaction. Games and Economic Behavior, 5:387–424.
Boncinelli, L. and Pin, P. (2018). The stochastic stability of decentralized matching on a graph.
Games and Economic Behavior, 108:239–244.
Borda, Jean Charles de. (1781). Mémoire sur les elections au scrutin. In Histoire de L’Academie
Royale des Sciences.
Caplin, A. and Nalebuff, B. (1988). On 64%-majority rule. Econometrica, 56:787–814.
Condorcet, Marquis de. (1785). Essai sur l’application de l’analyse à la probabilité des décisions
rendues à la probabilith des voix. Paris: De l’imprimerie royale.
Conley, J. P., Toossi, A., and Wooders, M. (2006). Memetics and voting: how nature may make us
public spirited. International Journal of Game Theory, 35(1):71–90.
Coughlin, P. J. (1992). Probabilistic Voting Theory. Cambridge University Press.
Davis, O. A., DeGroot, M. H., and Hinich, M. J. (1972). Social preference orderings and majority
rule. Econometrica, 40:147–157.

30

Demuynck, T., Herings, P. J.-J., Saulle, R. D., and Seel, C. (2019). The myopic stable set for social
environments. Econometrica, 87(1):111–138.
Diermeier, D., Egorov, G., and Sonin, K. (2017). Political economy of redistribution. Econometrica, 85(3):pp.851–870.
Duggan, J. and Kalandrakis, T. (2012). Dynamic legislative policy making. Journal of Economic
Theory, 147:1653–1688.
Foster, D. P. and Young, H. P. (1990). Stochastic evolutionary game dynamics. Theoretical Population Biology, 38:219–232.
Fowler, J. H. (2006). Habitual voting and behavioral turnout. The Journal of Politics, 68(2):335–
344.
Golub, B. and Jackson, M. O. (2010). Naı̈ve learning in social networks and the wisdom of crowds.
American Economic Journal: Microeconomics, 2(1):112–149.
Gomes, A. and Jehiel, P. (2005). Dynamic processes of social and economic interactions: On thepersistence of inefficiencies. Journal of Political Economy, 113:626–667.
Grabisch, M. and Rusinowska, A. (2020). A survey on nonstrategic models of opinion dynamics.
Games, 11(4):65.
Hwang, S.-H., Lim, W., Neary, P., and Newton, J. (2018). Conventional contracts, intentional behavior and logit choice: Equality without symmetry. Games and Economic Behavior, 110:273–
294.
Jackson, M. O. and Watts, A. (2002). The evolution of social and economic networks. Journal of
Economic Theory, 106:265–295.
Kalandrakis, A. (2004). A three-player dynamic majoritarian bargaining game. Journal of Economic Theory, 116:294–322.
Kanazawa, S. (1998). A possible solution to the paradox of voter turnout. The Journal of Politics,
60(4):974–995.
Kandori, M., Mailath, G. J., and Rob, R. (1993). Learning, mutation, and long run equilibria ingames. Econometrica, 61:29–56.
Kandori, M., Serrano, R., and Volij, O. (2008). Decentralized trade, random utility and the evolution of social welfare. Journal of Economic Theory, 140:328–338.
31

Klaus, B., Klijn, F., and Walzl, M. (2010). Stochastic stability for roommate markets. Journal of
Economic Theory, 145(6):2218 – 2240.
Kramer, G. H. (1977). A dynamical model of political equilibrium. Journal of Economic Theory,
16:310–334.
Lagunoff, R. D. and Matsui, A. (1995). Evolution in mechanisms for public projects. Economic
Theory, 6(2):195–223.
Landi, M. and Sodini, M. (2012). An evolutionary analysis of turnout with conformist citizens.
Journal of Economic Dynamics and Control, 36(10):1431–1447.
Lim, W. and Neary, P. R. (2016). An experimental investigation of stochastic adjustment dynamics.
Games and Economic Behavior, 100:208–219.
Mäs, M. and Nax, H. H. (2016). A behavioral study of “noise” in coordination games. Journal of
Economic Theory, 162:195–208.
McKelvey, R. D. (1976). Intransitivities in multidimensional voting models and some implications
for agenda control. Journal of Economic Theory, 12:472–482.
McKelvey, R. D. (1979). General conditions for global intransitivities in formal voting models.
Econometrica, 47:1085–1112.
McKelvey, R. D. and Patty, J. W. (2006). A theory of voting in large elections. Games andEconomic Behavior, 57(1):155–180.
Miller, N. R. (1977). Graph-theoretical approaches to the theory of voting. American Journal of
Political Science, 21:769–803.
Nax, H. H. and Pradelski, B. S. R. (2015). Evolutionary dynamics and equitable core selection inassignment games. International Journal of Game Theory, 44:903–932.
Nax, H. H. and Rigos, A. (2016). Assortativity evolving from social dilemmas. Journal of Theoretical Biology, 395:194–203.
Newton, J. (2012). Coalitional stochastic stability. Games and Economic Behavior, 75:842—-854.
Newton, J. (2018). Evolutionary game theory: A renaissance. Games, 9(2):31.
Newton, J. and Sawa, R. (2015). A one-shot deviation principle for stability in matching problems.
Journal of Economic Theory, 157:1–27.

32

Nunnari, S. (2021). Dynamic legislative bargaining with veto power: Theory and experiments.
Games and Economic Behavior, 126:186–230.
Penn, E. M. (2009). A model of farsighted voting. American Journal of Political Science, 53:36–
54.
Plott, C. R. (1967). A notion of equilibrium and its possibility under majority rule. American
Economic Review, 57:787–806.
Riker, W. H. (1980). Implications from the disequilibrium of majority rule for the study of institutions. American Political Science Review, 74:432–446.
Sandholm, W. H. (2010). Population Games and Evolutionary Dynamics. MIT Press, first edition.
Sawa, R. (2014). Coalitional stochastic stability in games, networks and markets. Games andEconomic Behavior, 88:90–111.
Schofield, N. (2005). Local Political Equilibria, pages 57–91. Springer Berlin Heidelberg, Berlin,
Heidelberg.
Simpson, P. B. (1969). On defining areas of voter choice: Professor tullock on stable voting.
Quarterly Journal of Economics, 83:478–490.
Skyrms, B. (1996). Evolution of the Social Contract. Cambridge University Press, Cambridge
New York.
Tullock, G. (1967). The general irrelevance of the general impossibility theorem. Quarterly Journal of Economics, 81:256–270.
Wu, J. (2016). Evolving assortativity and social conventions. Economics Bulletin, 36(2):936–941.
Wu, J. (2017). Political institutions and the evolution of character traits. Games and Economic
Behavior, 106:260–276.
Young, H. P. (1993). The evolution of conventions. Econometrica, 61:57–84.
Young, H. P. (1998). Conventional contracts. Review of Economic Studies, 65(4):773–792.

33