Deep and shallow thinking in the long run*Heinrich Nax† and Jonathan Newton‡
March 25, 2021

Abstract
Humans differ in their strategic reasoning abilities and in beliefs about others’ strategic reasoning abilities. Studying such cognitive hierarchies has produced new insights
regarding equilibrium analysis in economics. This paper investigates the effect of cognitive hierarchies on long run behavior. Despite short run behavior being highly sensitive
to variation in strategic reasoning abilities, this variation is not replicated in the long run.
In particular, when generalized risk dominant strategy profiles exist, they emerge in thelong run independently of the strategic reasoning abilities of players. These abilities
may be arbitrarily low or high, heterogeneous across players and evolve over time.
Keywords: bounded rationality, level-k thinking, evolution.
JEL Codes: C73, D81, D90.

1. Introduction“Coordination, when it occurs, is an almost accidental (though statistically predictable) by-product of non-equilibrium thinking”– Vincent Crawford (2007)
There is evidence that humans sometimes reason iteratively to predict the behavior ofothers and that the depth of such reasoning can vary according to person and situation (Crawford, 2019). Apart from some notable exceptions (e.g. Sáez-Martı and Weibull, 1999; Myatt* The authors gratefully acknowledge the comments of Xiaohong Chen, Vince Crawford, Ryota Iijima,

Rosemarie Nagel, María Sáez Martí and Larry Samuelson. Nax’s work was supported by a Swiss National Science Foundation Eccellenza Grant. Newton’s work was supported by a KAKENHI Grant-in-Aid for Research
Activity Start-Up funded by the Japan Society for the Promotion of Science (Grant 19K20882).
† ETH Zurich, 8092 Zurich, Switzerland, and University of Zurich, 8050 Zurich, Switzerland. e-mail:heinrich.nax@uzh.ch; website: nax.science.
‡ Institute of Economic Research, University of Kyoto, Yoshida-honmachi, Sakyo-ku, Kyoto 606-8501,
Japan. e-mail: newton@kier.kyoto-u.ac.jp; website: jonathannewton.net.

Level of rationality
k=1
2≤k<∞
k=∞

Risk dominance with two strategies
Generalized risk dominanceand uniform interaction
Blume (2003)∗
Myatt and Wallace (2003)

Peski (2010)∗∗

Figure 1: Summary of literature. Blume (2003) and Peski (2010) consider myopic (k = 1)
players that follow the general class of processes that we consider in Section 6. Myatt andWallace (2003) consider sophisticated (k = ∞) players who can iteratively reason to a Nashequilibrium every period. The current paper (denoted ∗) extends these results to any k in
the generalized setting and, a fortiori, to the two strategy uniform interaction setting. Other
work, discussed later, considers two player games under sample based processes (Sáez-Martı
and Weibull, 1999; Matros, 2003; Khan and Peeters, 2014).
and Wallace, 2003), the literature on long run outcomes in games played in populations usually abstracts from such considerations. An open question has been whether the best known
result in this literature, the emergence of (generalized) risk dominant Nash equilibria (seePeski, 2010) under broad classes of best response dynamics, is robust to such iterative reasoning. We answer this question in the affirmative. Even though short run behavior can bedramatically affected by such reasoning and convergence to Nash equilibrium may fail tooccur in the short run, long run predictions are robust to all levels of reasoning by players.
Moreover, these levels may be heterogeneous and may even be random, in which case they
can be correlated across players.
Let us describe our model in more detail. Every period, given the current strategy profile,each player formulates a conjecture about the behavior of the other players to which he willusually, but not always, best respond. A player of level k = 1 will conjecture that otherplayers remain at the current strategy profile. Higher levels of k are defined iteratively. A
player of level k will conjecture that all other players are of level k − 1. Level k = ∞ involves
reasoning to a Nash equilibrium strategy every period. We consider the long run behaviorof this process. The long run stability of risk dominance has been known in progressively
stronger forms since Young (1993a); Kandori et al. (1993). The strongest known results forvarious levels of k in specific and general settings are shown in Figure 1, with the remaining
entries in the table being contributions of the current paper. In addition, our results span thetable in the sense that if, as empirical work suggests (Stahl and Wilson, 1994; Nagel, 1995,
onwards) and is theoretically plausible (Stahl, 1993), players have different values of k, or if
levels of k are determined randomly from period to period, then the result still holds.1
1 Notably, in addition to epistemic considerations (Bacharach, 1992), the foundational literature on levelk thinking explicitly studies evolutionary forces (Stahl, 1993) and behavioral dynamics (Nagel, 1995; Selten,–2–For expositional reasons, we first state our main result for a level k version of logit choice(Theorem 1). Later, we expand our analysis to consider a broad class of dynamics in which
the probability of playing a non-best response is weakly decreasing in the payoff loss that
results, together with a broad class of conjectures that players can make about the behavior of other players (Theorem 3). Lastly, we consider randomness in players’ conjectures(Theorem 4). To prove these results, we use recent advances in the study of asymmetricdynamics. We break down the dynamic process of strategy updating into sub-processes foreach player and level of rationality and show that these sub-processes satisfy a certain typeof asymmetry towards the generalized risk dominant strategy profiles. We then combine
these processes using the methods of Newton (2020, 2019) to obtain an aggregate processthat is also asymmetric towards such profiles. This asymmetry implies that generalized risk
dominant strategy profiles are those that will be observed most often in the long run (Peski,2010).2
Applying our results to technology adoption in networked populations, we show that thestrategy profile at which every player plays a risk dominant technology remains the moststable outcome for arbitrary levels of rationality (Proposition 1). We then consider the possibility of entirely random (k = 0) players and show how their presence can cause multiplicity
in the number of long run stable outcomes (Theorem 2) in a way that depends subtly on
the levels of more rational (k ≥ 1) players (Proposition 2). Applying our results to the second price auction, we show that the strategy profile at which every player bids his valuation
emerges in the long run (Proposition 3) for a broad range of conjectures that players canform about how other players choose their bids. This result is proven by showing that an
equilibrium in weakly dominant strategies is always generalized risk dominant (Theorem 5).
The paper is organized as follows. Section 2 discusses related literature. Section 3 describes level k logit dynamics and Section 4 gives the first iteration of our main result. Section
5 applies this result to technology adoption on networks. Section 6 gives our main result under a broad class of dynamics and a broad class of conjectures that players can make about
the behavior of other players. Section 7 applies this result to second price auctions. All
proofs are relegated to the appendix.
1991). The current study and those cited in Figure 1 follow in this tradition by studying long run behavior
under such models.
2 Theorem 1 on level k conjectures and logit choice is, in fact, a special case of the subsequent theorems
on general conjectures and general dynamics. However, given the accessibility and widespread use of level kmodels and logit choice, we present these results prior to the more abstract and general presentation.

–3–

2. Related literature
Economic experiments on static, sequential and repeated games have produced evidence
to support both level k modeling assumptions and the possibility of heterogeneity in k acrossplayers. See Crawford (2019) for a recent review of this literature. Moreover, there is evidence that short run convergence to equilibrium may depend on cognitive ability (Gill andProwse, 2016; Proto et al., 2019). However, there is also experimental evidence of a tendency
for subjects to reason at progressively higher levels over time (Nagel, 1995; Duffy and Nagel,1997). Indeed, changes in levels of k have been fitted to models of reinforcement learning
Stahl (1999, 2000) and Bayesian updating (Ho and Su, 2013). In contrast, the main resultsof the current paper concern long run behavior after levels of k have either reached a steadystate or persist above a given level. In such situations, our results predict a tendency towards
risk dominant equilibria, as has been observed in several experimental settings (Van Huyck
et al., 1990; Battalio et al., 2001; Heinemann et al., 2004; Cabrales et al., 2007).
There also exists a theoretical literature on the persistence of different levels of k in populations. The overall conclusion is that because “being right is just as good as being smart”(Stahl, 1993), heterogeneous levels of rationality can persist when players with those levels
play similar strategies (see also Mohlin, 2012). Other work discusses explicit weaknessesof iterated reasoning. Stennek (2000) shows how iterated deletion of strictly dominatedstrategies can lead to fitness losses unless probability weight redistributed from a dominatedstrategy when it is deleted is only transferred to those strategies that dominate it. Geanakoplos and Gray (1991) explain how errors in assessing the value of future continuation games
can lead to suboptimal play in the present. A striking way to be unable to assess the value ofthe future in such settings would be if a player did not use information about other player’s
payoffs when making decisions. As we might expect, such players will usually be eliminatedfrom the population (Robalino and Robson, 2016). Finally, heterogeneity in other traits may
interact with iterated reasoning. For example, Heller (2015) shows how being able to know
far in advance when a series of repeated prisoner’s dilemmas will end can be evolutionarily selected against, as when two such players are paired, it becomes impossible to sustain
cooperation for a considerable number of periods before the end of the game. Similarly, collaborative decision making may lead to cooperation in prisoner’s dilemmas in the absence offurther reasoning, but will fail to do so if subsequent reasoning lead to defection (Newton,
2017; Rusch, 2019).
The dynamic processes that we adapt for level k and broader conjectures about opponents’ behavior are common in the evolutionary literature. Theorem 1 concerns logit dynamics (Blume, 1993). For a detailed discussion of logit dynamics, the reader is directed to
Alós-Ferrer and Netzer (2010). The general idea is that the probability of playing a non-best–4–response action decreases log-linearly in the payoff loss from playing that action relative tothe payoff from playing a best response. If log-linearity is dropped, we obtain a much larger
class of dynamics. Theorems 3 and 4 concern this class, which is close to the classes of skewsymmetric rules (Blume, 2003) and payoff-based rules (Peski, 2010). Recent experimental
studies designed to explicitly test the properties of non-best response behavior finds evidencein support of such dynamics (Mäs and Nax, 2016; Lim and Neary, 2016; Hwang et al., 2018).
The survey of Newton (2018) covers recent work on trait evolution and dynamics, including
many of the papers discussed above.
The dynamics considered in the current paper have the current strategy profile as thestate variable. This has been popular in the literature following Kandori et al. (1993). A
parallel literature considers a sample based process, adaptive play (Young, 1993a), according to which members of populations are drawn to play a game against members of otherpopulations and respond to a sample of how the game has been played in the recent past.
This adds a degree of complication to the model that has been leveraged to obtain results
for level k thinking in two player games in which one player is drawn from each of two
populations. From a benchmark in which every player has k = 1, the focus of research has
been on conditions under which the presence of k = 2 players changes the implications of thebenchmark model. Sáez-Martı and Weibull (1999) consider the bargaining model of Young(1993b) in the presence of k = 2 players, Matros (2003) considers generic two player gamesin the presence of k = 2 players, and Khan and Peeters (2014) consider generic two player
games in the presence of players with any finite k. The general conclusion of this literatureis that k > 1 makes a difference if and only if a low sample size for clever players in one
population causes them to foresee a change in the behavior of the opposing population thenext period that does not in fact happen. However, having acted to preempt the predictedchange, the clever players put in motion a sequence of transitions that moves the process toanother equilibrium.
Finally, we note that there is a literature that considers possible non-convergence of certain processes to mixed Nash equilibria (see Crawford, 1974) and the role that k = 2 players
can have in overcoming this non-convergence (Selten, 1991; Conlisk, 1993b,a; Tang, 2001).
In contrast, the dynamics of the current paper may fail to converge to Nash equilibrium inthe short run due to the presence of k = 2 players. However, our main results regarding longrun predictions turn out to be unaffected by whether or not short run convergence occurs.

–5–3. Model
3.1 The game
Consider a normal form game G = (N, {Si }i∈N , {Ui }i∈N ). The set of players is N. Each
player i ∈ N has a finite strategy set Si and a strategy for player i is denoted si ∈ Si . The setof strategy profiles is S = ×i∈N Si with generic element s ∈ S. Let s−i denote s restricted to
N r {i}. The payoff to player i at strategy profile s is given by Ui (s) = Ui (si , s−i ). Assume
that Ui (si , s−i ) , Ui (s0i , s−i ) for any si , s0i , s−i , which holds generically in payoffs. Cases inwhich it does not hold will be considered later in Sections 6 and 7.

3.2 Level k best responses
We assume that each player i ∈ N has a level of rationality given by an integer k ≥ 1.
Different players are allowed to have different values of k. We refer to a player with agiven value of k as a level k player. A player’s level will determine the conjecture he makes
about the behavior of other players. In Section 6 we will allow players’ levels to be random,
correlated and changing over time. For now, we assume that any given player’s level remains
fixed and unchanging.
For a given strategy profile s, we denote the profile of best responses by(1)
B1 (s) = B1i (s)

i∈N

,



where B1i (s) ∈ arg max Ui si , s−i .
si ∈Si

We will refer to B1 (s) as the profile of level 1 best responses to s. Note that, by our genericity
assumption on payoffs, best responses are uniquely determined. We also wish to consider
best responses to best responses, best responses to these in turn, and so on. To do this, werecursively define level k best responses as(2)
Bk (s) = B1 Bk−1 (s)fork ∈ N, k ≥ 2.

Note that the difference between different levels of best response lies in the conjectured
strategy profiles to which a player best responds. These conjectures are based on the iterationof the best response correspondence. More general conjectures that are not based on iterated
best response will be considered in Section 6.
If the best response correspondence converges, that is if there exists k such that Bk (s) =Bk−1 (s) for all s ∈ S, then we say that the game G is Nash convergent.
Remark 1. If G is Nash convergent, then for all s ∈ S, B∞ (s) := limk→∞ Bk (s) is a Nash
–6–

i is



active w.p. q

and plays s0i w.p.

iinactive w.p. (1 − qi )(P r1 (s0i |st ) if i is level 1
P rk (s0i |st ) if i is level k ≥ 2

and plays st+1
= stii−−−−−−−→ −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−→
Period t

Period t+1−−−−−−−→
Period t+2

Figure 2: Strategy updating. Revision probabilities in period t + 1 for different levels ofrationality of player i.

equilibrium (Nash, 1950).

3.3 Level k logit choice
For our principal analysis we will adopt the logit choice rule. We do this as it is the best
known and most commonly used stochastic behavioral rule. However, our results extend
to a family of payoff dependent behavioral rules, which we shall discuss in Section 6. The
standard logit choice rule (Cox, 1958; Block and Marschak, 1959) is as follows. Given acurrent strategy profile st , the probability of player i choosing strategy s0i is given by1(3)

Pr (s0i |st ) =1

0 t

e η Ui (si ,s−i ),1te η Ui (si ,s−i )∑for some η > 0.

si ∈SiThis is a perturbed best response rule parameterized by η > 0. For small values of η, a player
following this rule will usually play a level 1 best response. Hence, we refer to the rule as
level 1 logit choice. However, sometimes the player will play a non-best response. For smallvalues of η, such non-best responses are rare and the level 1 best response is played almost
all of the time. Analogously, we define level k logit choice for k ≥ 2,
1

(4)

Pr (s0i |st ) =
k

0

k−1

e η Ui (si ,B−i (s ))
.
k−1 t
1
η Ui (si ,B−i (s ))e∑tsi ∈SiThat is, for small values of η, a player following the level k logit choice rule will usuallyplay a level k best response.
For η = 0, define level k logit choice probabilities as the limits of (3) and (4) as η → 0.
That is, a level k best response will be played with probability one.
The difference between the standard logit choice rule and the level k logit choice rule fork ≥ 2 is the conjectured play of the opposing players. Specifically, standard logit probabilities
for player i are calculated with respect to the conjecture that other players remain playing–7–their current strategies, whereas level k logit probabilities are calculated with respect to theconjecture that other players play level k − 1 best responses.3
It follows from (4) and the definition of Nash convergence that if the game G is Nashconvergent and players are sufficiently rational, then level k logit choice under small η willusually conform to the play of Nash equilibrium strategies.4
Remark 2. If the game G is Nash convergent then, for large enough k, for any current
strategy profile st ∈ S, level k logit choice by player i will choose the Nash equilibriumt
strategy B∞i (s ) with probability approaching one as η → 0.

3.4 Dynamic strategy updating
We define the level k logit dynamics on the state space of strategy profiles. The game isplayed repeatedly in discrete time and strategies are updated according to the level k logit
choice rule. Let the strategy profile played at period t be st . At time t + 1, any given player
i is, independently of the other players, active with probability qi ∈ (0, 1). If i is not active
at t + 1, then his strategy at t + 1 remains the same as his strategy at t. That is, st+1
= sti . Ifiplayer i is active at period t + 1 and is of level k, then he updates his strategy according to
the level k logit choice rule.
Remark 3. If k = 1 for every player, then this process is effectively the standard logit dynamic of Blume (1993).5 Players for whom k = 2 correspond to the ‘clever’ players of
Sáez-Martı and Weibull (1999); Matros (2003).
Remark 4. Let G be Nash convergent and every player have a level k high enough that
Bk−1 (·) = B∞ (·). Under the unperturbed (η = 0) dynamic, if the strategy profile at time t is
st , then with probability at least ∏i∈N qi , the strategy profile at time t + 1 will be the Nashequilibrium B∞ (st ). High rationality players that achieve such coordination correspond tothe ‘sophisticated’ players of Myatt and Wallace (2003).
Remarks 3 and 4 illustrate that the level k logit dynamics bridge the gap between perturbed best response dynamics in the style of Kandori et al. (1993); Young (1993a) andinstantaneously jumping to a Nash equilibrium. Indeed, an important implication of thecurrent paper is that certain results are robust across this entire class of models.
3 Note that players’ conjectures do not consider the possibility that other players’ choices are perturbed. This

is in contrast to, for example, the ‘noisy introspection’ model of Goeree and Holt (2004). For more general
conjectures about the behavior of others, see Section 6.
4 In fact, it can be checked that, given current strategy profile st , logit choice probabilities under a sequenceof decreasing values of η correspond to a sequence that identifies B∞ (st ) as a proper equilibrium under thedefinition of Myerson (1978).
5 See Alós-Ferrer and Netzer (2010) for an extended discussion of this process and Sandholm (2010); Newton (2018) for discussion of related processes.

–8–3.5 Stochastic stability
Under the level k logit dynamics with η > 0, any state can be reached from any otherstate. Therefore the process is irreducible and has a unique stationary distribution, which
we denote πη . The stationary distribution gives the proportion of time that the process will
spend at any strategy profile in the long run. We are interested in dynamics that are close tobest response dynamics, that is when η is small.
It can be shown by standard arguments (Foster and Young, 1990) that πη converges asη → 0. Denote this limiting stationary distribution by π0 . If π0 (s) > 0, we say that s isstochastically stable. If π0 (s) = 1, we say that s is uniquely stochastically stable. For smallvalues of η, the process will spend almost all of its time at stochastically stable strategy
profiles. Thus the identity of stochastically stable states tells us which strategy profiles wecan expect to be played most of the time in the long run.

4. Main result
Our main result is that results on the stability of risk dominant strategy profiles understandard (k = 1) perturbed best response dynamics are robust to level k updating. We shallwithhold discussion of why the result is novel, interesting and non-obvious until after presenting it. First, we shall define the concept of risk dominance that we use, generalized risk
dominance (Peski, 2010).
Consider any given strategy profile and label it sA . Without loss of generality, we label
the strategies of every player at sA as A, so that sAi = A for all i ∈ N. If a pair of strategy
profiles s, s0 are such that every player plays A at at least one of s and s0 , then we say that s
and s0 are A-associated (see Figure 3). Generalized risk dominance of sA holds when, for any
two A-associated strategy profiles, the incentives to play A at one of these profiles outweighs
any incentive not to play A at the other profile.6
Definition 1 (Generalized risk dominance).
Profile sA is generalized risk dominant (GR-dominant) if, for all A-associated strategy profiles s0 , s00 , for all i ∈ N,
(5)

Ui (A, s0−i ) +Ui (A, s00−i ) ≥ max Ui (si , s0−i ) + max Ui (si , s00−i ).
si ,A

si ,A

Substituting > for ≥ in (5) gives the definition of strict generalized risk dominance.

6 Peski (2010) defines ordinal and cardinal forms of GR-dominance. The definition we use corresponds tothe cardinal form.

–9–

sA s s0 sB
Alice A A B B
Bob A B A B
Figure 3: A-association. Consider the illustrated example with two players and two strategies, labeled A and B, for each player. It can be seen that sA is A-associated with every otherstrategy profile. Furthermore, s is A-associated with s0 , as every player plays A at at least
one of these two profiles. However, s is not A-associated with sB , as Bob plays A at neitherof these profiles. Finally, s0 and sB are not A-associated, as Alice plays A at neither of these
profiles.
Remark 5. With two players and two strategies, (strict) GR-dominance is equivalent to(strict) risk dominance of Harsanyi and Selten (1988). We consider this further in Section
5. For two players and more than two strategies, (strict) GR-dominance implies (strict) 21 dominance of Morris et al. (1995). Conversely, when there are many players but payoffs area linear sum of payoffs from two player interactions, a strong form of 12 -dominance implies
GR-dominance (Peski, 2010). In general, however, these concepts are independent (see also
Iijima, 2015).
We are now ready to state our main Theorem. Risk dominance is robustly selected forunder the entire class of level k logit dynamics.
Theorem 1. Under the level k logit dynamics• If sA is GR-dominant, then sA is stochastically stable.
• If sA is strictly GR-dominant, then sA is uniquely stochastically stable.
Remark 6. It is known that stochastic stability of GR-dominant profiles holds under a classof payoff dependent behavioral rules (see Section 6) that includes logit (Peski, 2010). This isa generalization of earlier results concerning the stochastic stability of risk dominant profilesin 2 by 2 games (Kandori et al., 1993; Young, 1993a; Blume, 1993, 2003). It is further known
that these results are robust to heterogeneity in behavioral rules (Newton, 2020). However,unlike the above work, the current work considers non-myopic conjectures. Specifically, theabove papers consider smoothed best responses to the current strategy profile st , whereas we
consider smoothed best responses to a variety of conjectures based on st . Furthermore, weallow heterogeneity in these conjectures across players.
Remark 7. The seminal papers of Kandori et al. (1993); Young (1993a); Blume (1993) can
be considered to have made two principal contributions. (I) The unperturbed (η = 0) dynamic eventually converges to a Nash equilibrium with probability one (under conditions of–10–

what Young calls weak acyclicity), and (II) in two strategy coordination games, risk dominant
Nash equilibria are stochastically stable. In the current model, (I) does not hold. Persistent
miscoordination may arise due to k > 1 and can prevent convergence of the unperturbed
dynamic to a Nash equilibrium (see Section 5 for an example). Nevertheless, result (II) continues to hold. That is, the long run stability of risk dominance does not rely on short run
convergence to Nash equilibrium.
Remark 8. Consider Nash convergent G, small η and qi close to 1. Under these conditions,from any non-Nash equilibrium profile, the process will reach a Nash equilibrium in a single
period with a probability close to 1. This instant convergence, often assumed in one-shotgames, does not change the stochastic stability of risk dominance. Taken together with
Remark 7, this implies that stochastic stability of risk dominance is unaffected by either ofthe contrasting cases of instant convergence or non-convergence of the unperturbed dynamic
to Nash equilibrium.
Remark 9. We show in Section 6 that our results our robust to the levels of players being
generated randomly in each period in a way that allows for correlation, both positive and negative, across players. Consider an alternative approach of adding a state variable that tracks
players’ levels, with levels increasing over time. Considering this state variable as part of thestate space, the process is no longer irreducible. However, if G is Nash convergent, then theprocess governing evolution of the strategy profile converges as best responses converge toB∞ (·). This implies that the behavioral implications of Theorem 1 continue to hold.
Sketch of Proof. The proof of Theorem 1 is given in Appendix A. A summary of theproof is as follows. First, we disaggregate the process and consider processes in which
only a single player of some given level k updates his strategy, with the strategies of otherplayers remaining fixed. Note that such processes are not irreducible. However, this does
not matter, as we can still show that they satisfy a particular property. Specifically, we show
in Lemma 2 that if sA is GR-dominant, then these processes satisfy a form of asymmetry
towards strategy A. This form of asymmetry was considered for processes by Peski (2010)
and applied to individual behavioral rules by Newton (2020). Second, we re-aggregate theprocess to once again consider the process in which every player updates independently as
described in our model. We show in Lemma 3 that asymmetry of the disaggregated processes
implies asymmetry of the aggregate process. This is done by applying Theorem 3 of Newton(2020, 2019). Finally, we apply Theorem 1 of Peski (2010), which states that asymmetry of
the aggregate process towards strategy A implies stochastic stability of sA .
We shall end this section with a brief consideration of the possible impact of players
who play completely randomly. Specifically, let a level 0 player be a player who chooses
–11–

A
B

A
aAA
aBA

B
aAB
aBB

Figure 4: Unweighted payoffs from each interaction. aAA > aBA and aBB > aAB . For eachcombination of A and B, entries give payoffs for the row player.
a strategy uniformly at random from his strategy set. That is, if player i is a level 0 player,then when he updates his strategy he will choose each strategy in Si with probability 1/|Si |.
In the presence of such players, the first part of Theorem 1 continues to hold. However, thesecond part of Theorem 1 does not. Even under strict GR-dominance of sA , there are always
multiple stochastically stable states when any level 0 player has more than one strategy.
Theorem 2. Let every player either follow the level k logit dynamics for k ≥ 1 or be a level0 player. If sA is GR-dominant, then sA is stochastically stable. If there exists a level 0 player
with more than one strategy, then there exist multiple stochastically stable strategy profiles.
The extent of the multiplicity caused by level 0 players is sensitive to model details. In
particular, it can depend on the levels of the non-level 0 players, as we will see in Example 2of Section 5.

5. Application: technology adoption on networks
Consider a situation in which each player may adopt one of two technologies. Specifically, let Si = {A, B} for all i ∈ N. Each player is influenced by other players and may be
influenced by some players more than others. Let wi j ∈ R≥0 be the influence of player j
on player i. Assume that every player i is influenced by at least one other player, so that∑ j∈Nr{i} wi j > 0, as is the case in the game illustrated in Figure 5. Each player wishes toadopt a similar strategy to those who influence him. Specifically, payoffs from each pairwiseinteraction are given by the game illustrated in Figure 4. The payoff to player i at strategy profile s is then the sum of the payoffs from his pairwise interactions weighted by theirinfluence. That is,(6)

Ui (s) = Ui (si , s−i ) =∑wi j asi s j ,j∈Nr{i}where asi s j ∈ R is the payoff to player i from his interaction with player j.
A classic result (Blume, 1993) is the stochastic stability of strategy profiles at which
every player plays the same risk dominant strategy (Harsanyi and Selten, 1988). In the two–12–

player game of Figure 4, a strategy is risk dominant if it maximizes payoff given that the
opposing player randomizes evenly across his two strategies.
Definition 2.
Strategy A is risk dominant if(7)

aAA + aAB ≥ aBA + aBB ,and is strictly risk dominant if the inequality holds strictly.
It is possible to show that (strict) risk dominance of A implies (strict) GR-dominance ofsA . We can then apply Theorem 1 to show that (strict) risk dominance of A implies (unique)stochastic stability of sA . The reverse implication then follows from the fact that at least oneof the two strategies must be risk dominant.
Proposition 1. For technology adoption on a network under the level k logit dynamics,• sA is stochastically stable if and only if A is risk dominant.
• sA is uniquely stochastically stable if and only if A is strictly risk dominant.
The special case of Proposition 1 in which all players are level 1 is known from Blume(1993, 1996). Proposition 1 shows that stochastic stability of risk dominance is robust tovarying levels of rationality. The result is not obvious. Level k thinking can lead to shortrun behavior that is completely different to that implied by level 1 thinking. However, in allcases, long run behavior tends to risk dominance (see Remark 7 earlier in the paper). We
illustrate these points with the following example.
Example 1. Let N = {i, j} and wi j = w ji = 1. If player i is of level 2, then he will neverchange his strategy as a result of playing a best response to his conjecture. To see this, let
the current strategy profile be st = (sti , stj ). Given this current strategy profile, player i will
conjecture that player j will play B1j (st ) = sti . That is, player i expects player j at time t + 1
to coordinate with the strategy of player i at time t. A best response for player i to thisconjecture is to remain playing the same strategy at time t + 1 as he plays at time t. That is,
he does not change his strategy. Consequently, if both player i and player j are level 2, thenneither of them will ever change his strategy as a result of a best response. It follows that all
strategy profiles are absorbing states of the process with η = 0. This is in stark contrast to thestandard case in which every player has level 1, where the process with η = 0 converges withprobability one in finite time to a Nash equilibrium of the game. Nevertheless, Proposition 1
tells us that level k does not affect stochastic stability predictions for the perturbed process.
The stability of risk dominance is robust to rationality.
–13–

j j

i

j

j'

I

II

i

Figure 5: Influence networks. Nodes are players. Dashes adjacent to nodes indicate players’
levels of rationality, here between zero (no line) and four. Left: Example cognitive hierarchy
and influence structure. Directed edges indicate non-zero influences and their direction. Thatis, an arrow from i to j indicates that the influence of player j on player i (i.e. wi j ) is strictly
positive. Right: Star network from Example 2 (‘even’ case). Links indicate mutual influence
between two players. Per Example 2, wik = wki = 1 for all k , i.

Theorem 2 showed that the presence of level 0 players who act randomly and unpredictably can lead to multiplicity of stochastically stable strategy profiles even when sA isstrictly GR-dominant. The following example shows how the extent of this multiplicity canbe sensitive to the levels of the non-level 0 players.
Example 2. Let there be |N| ≥ 3 players interacting on a star network (as illustrated on theright of Figure 5). That is, there is is some player i such that wi j = w ji = 1 for all j , i, andw jk = 0 for all j , i, k , i. Let player i be a level 0 player and let all j , i be level k∗ . Let A
be strictly risk dominant, hence sA is strictly GR-dominant by the proof of Proposition 1.
The first part of Theorem 2 implies that sA is stochastically stable. The second partof Theorem 2 implies that if there is at least one level 0 player, then there must also exist
stochastically stable profiles other than sA . Somewhat trivially, if sA is stochastically stable,
then the profile at which player i plays B and all other players play A must be stochasticallystable. However, the randomness in the behavior of player i may also be enough to change
the behavior of the other players.
Proposition 2. Consider Example 2. If k∗ is odd, then all strategy profiles are stochasticallystable. If k∗ is even, then there are two stochastically stable strategy profiles, (si , s−i ) = sA
and (si , s−i ) = (B, sA−i ).

To see the intuition behind Proposition 2, first consider k∗ = 1. Starting from sA , if playeri switches to B, then any other player j may subsequently switch to B as a best response. This
introduces enough disorder into the system that every strategy profile can be reached by theunperturbed dynamic (η = 0) and, as a consequence, every strategy profile is stochasticallystable. All odd values of k∗ follow similar reasoning.
–14–

Now consider k∗ = 2. From any initial strategy profile s, a player j , i will conjecture that
player i will play B1i (s) in the next period. Note that B1i (s) does not depend on si , therefore
the conjecture that j makes about the behavior of player i does not depend on player i’s
current strategy. Therefore, the behavior of player j does not depend on player i’s current
strategy. Consequently, the long run behavior of j is independent of the behavioral rule usedby i. Consider the hypothetical case in which player i has level k ≥ 1. We know by Theorem
1 that sA would then be uniquely stochastically stable. In particular, player j would play A
most of the time in the long run. As the behavior of player j is independent of the behaviorof player i, this must also be true when player i has level 0. Therefore, at any stochasticallystable profile it must be that all j , i play A. That is, sA and (B, sA−i ) are the only stochasticallystable profiles. All even values of k∗ follow similar reasoning.

6. Generalization
In this section we generalize the model in several dimensions. As before, we consider
players who do not best respond to the current strategy profile, but rather form conjectures
about play at t + 1 to which they best respond. However, now we do not restrict attention
to level k conjectures, but rather consider a more general class. In general, a conjecture forplayer i is a function fi : S → S. A profile of conjectures is given by f = { fi }i∈N .
We will show that an important class of conjectures are those that preserve A-association.
Given A-associated profiles s, s0 , this requires that the respective conjectures formed whenpresented with these strategy profiles are themselves A-associated.
Definition 3 (A-association preserving). Profile of conjectures f preserves A-association if,
for all i ∈ N, s, s0 A-associated, we have that fi (s), fi (s0 ) are A-associated.
The conjectures considered so far in the paper correspond to fi (s) = s and fi (s) = Bk (s)for k ≥ 1. The conjecture fi (s) = s always satisfies Definition 3 (see below). For fi (s) =Bk (s), if sA is GR-dominant and best responses are unique then Definition 3 is satisfied.
Given that this was our only use of the assumption of unique best responses, for the remainder of the paper we drop this assumption.
We present some examples of conjectures that satisfy Definition 3 irrespective of whether
GR-dominance holds.
Example 3 (Myopia). Consider the conjecture that all players remain playing their current
strategy. That is, fi (s) = s. It follows trivially that if s, s0 are A-associated, then fi (s), fi (s0 )are A-associated.

–15–

Example 4 (Majoritarianism). Let |N| be odd and consider the conjecture that all players
play the most popular current strategy, with some tie breaking rule employed. If s, s0 are
A-associated, it must be that a majority of players at s or s0 play A. Consequently, fi (s) = sAor fi (s0 ) = sA , therefore fi (s), fi (s0 ) are A-associated.
Example 5 (Imitate a friend). Consider the conjecture that each player imitates some otherplayer. That is, for all j ∈ N, we have ( fi (s)) j = sk for some k ∈ N. If s, s0 are A-associated,then for all k, sk = A or s0k = A. Consequently, for all j, ( fi (s)) j = A or ( fi (s0 )) j = A.
Therefore, fi (s), fi (s0 ) are A-associated.
Another dimension that we generalize is the behavioral rule that acts on the conjectured
strategy profile. So far, we have considered the logit choice rule. Now, we consider a large
class of regular behavioral rules (Young, 1993a) in which behavior depends on payoff differences.7
Adjust the behavioral rule given in Section 3 as follows. If player i is active at periodt + 1, then he forms a conjecture fi (st ) about behavior at time t + 1. Given his conjecture
about the behavior of other players, he then updates his strategy according to a perturbed best
response rule parameterized by η. Let ϒi (s0i , s00 ) denote the expected payoff loss, relative toa best response, incurred by player i when he plays s0i against s00−i . That is,(8)
ϒi (s0i , s00 ) = max Ui si , s00−i −Ui s0i , s00−i
si ∈Si= s0i at time t + 1 is then given by
The probability that st+1
i
(9)

 1
 
0
t
0 t
Pr st+1
=
s
|s
=
a
+
o(1)
e− η gi (ϒi (si , fi (s ))) ,iiwhere a is a strictly positive constant that can depend on s0i , st , fi , but not on η; o(1) is a termthat approaches zero as η → 0; gi is a nonnegative, weakly increasing function.
Note that larger values of gi (·) in (9) imply smaller probabilities. Together with (8), this
implies that the probability of choosing s0i decreases in the difference between the payofffrom best responding to the conjectured profile fi (st ) and the payoff from playing s0i againstfi (st ). The best response plus uniform deviations rule corresponds to gi (x) = sgn(x) and thelogit choice rule corresponds to gi (x) = x for appropriate choice of a and o(1).
We are now ready to present our generalization of Theorem 1. If conjectures preserve
A association, then under the class of perturbed best response rules described by (9), GRdominance implies stochastic stability. Thus, the results of the current paper extend to a wide
7 These behavioral rules roughly correspond to skew-symmetric rules (Blume, 2003), payoff-based rules(Peski, 2010) and self regarding payoff-difference based rules (Newton, 2020).

–16–

range of conjectures and behavioral rules.
Theorem 3. Let f preserve A-association. Under the dynamics (9)• If sA is GR-dominant, then sA is stochastically stable.
• If sA is strictly GR-dominant and, for all i ∈ N, we have gi strictly increasing andfi (sA ) = sA , then sA is uniquely stochastically stable.
We present one final generalization. It may be that player’s conjectures vary from period
to period. It may even be the case that player’s conjectures are correlated with each other. For
example, it may be that a player is more likely to exhibit low rationality behavior when otherplayers are exhibiting low rationality behavior. It turns out that randomness and correlationin conjectures does not affect our results.
Let F be a set of profiles of conjectures and let ϕ be an exogenously given distribution
over F. Adjust the model so that rather than there being a single fixed profile of conjectures,
every period a profile of conjectures f is chosen according to ϕ.
Theorem 4. Let all f ∈ F preserve A-association. Under the dynamics (9)• If sA is GR-dominant, then sA is stochastically stable.
• If sA is strictly GR-dominant and, for all i ∈ N, we have gi strictly increasing andfi (sA ) = sA for all f ∈ F, then sA is uniquely stochastically stable.

7. Application: Second price auctions
Consider a second price auction in which players bid for ownership of some good. Let
Vi ⊂ R, |Vi | ≥ 2, be a finite set of possible valuations that player i may have for the good.
Let vi denote a representative element of Vi . Similarly write V = ×i∈N Vi and denote a representative element of V by v = (vi )i∈N . That is, v denotes a possible profile of valuations.
The finite set of possible bids that player i can make is denoted Bi ⊇ Vi . The set of strategies
Si of player i is then the finite set of functions that map valuations to bids. That is, si ∈ Si if
and only if si is a function si : Vi → Bi . Given strategy profile s and valuations v, the payoffof player i is given by vi − max j,i s j (v j ) if i ∈ arg max j∈N s j (v j ),(10)
ui (s, v) := | arg max j∈N s j (v j )|0otherwise.
–17–

That is, the good is given to one of the players amongst those with the highest bids. If several
players make the same highest bid then one of them is chosen uniformly at random to receive
the good. The player who receives the good gets a payoff equal to the difference between his
valuation and the second highest bid. All other players pay nothing, do not obtain the good,
and therefore receive a payoff of zero. Letting V be an exogenously given distribution overvaluations V , we then have ex-ante expected payoffs given by(11)

Ui (s) = EV (·) ui (s, ·).

Before we proceed to analyze this problem, we require a further general result. Nashequilibria in weakly dominant strategies are GR-dominant and Nash equilibria in strictly
dominant strategies are strictly GR-dominant. Strategy A is weakly dominant when for all
s0i , A, we have Ui (A, s−i ) ≥ Ui (s0i , s−i ) for all s−i ∈ S−i .8 Strategy A is strictly dominant
when for all s0i , A, we have Ui (A, s−i ) > Ui (s0i , s−i ) for all s−i ∈ S−i .
Theorem 5. If sA is composed of weakly dominant strategies, then sA is GR-dominant. If sA
is composed of strictly dominant strategies, then sA is strictly GR-dominant.
For each player i, let sAi be such that sAi (vi ) = vi for all vi ∈ Vi . That is, A is the strategy
according to which the bid of player i always equals his valuation. We refer to sA as bidding
one’s own valuation. Note that A is a weakly dominant strategy. Combining Theorem 5 with
Theorem 4, we therefore conclude that bidding one’s valuation in the second price auction isstochastically stable under our general dynamics.
Proposition 3. When the second price auction is played under the dynamics (9) and allf ∈ F preserve A-association, then bidding one’s own valuation is stochastically stable.
Note that the best response correspondence in this game is multi-valued, so there is no
guarantee that a conjecture based on best responses will preserve A-association, even whensA is GR-dominant. However, if we restrict attention to best responses such that if s j is a best
response to s, then player j remains playing s j , then we do indeed preserve A-association.
This is easily verified using the definition of A-association and the fact that weak dominanceof A implies that A ∈ B1j (s).
Under some further assumptions we can obtain unique stochastic stability of bidding
one’s own valuation. Call a strategy si ∈ Si sensible if si (vi ) ≤ vi for all vi ∈ Vi . That is, asensible strategy is a strategy according to which a player never bids strictly more than his
valuation. Restrict attention to sensible strategies, to Bi = Vi and to valuations vi which are
8 Note that this is weaker than the usual definition of weak dominance which requires in addition that

Ui (A, s−i ) > Ui (s0i , s−i ) for some s−i ∈ S−i .

–18–

independent, identically distributed (iid) random variables with full support on Vi . Consider astrategy s∗i , A. As s∗i is sensible and s∗i , A, there must be some v∗i ∈ Vi such that s∗i (v∗i ) < v∗i .
Let us compare s∗i to A.
First, note that if all opposing players play sensible strategies and at least one (say playerj) of the opposing players plays A, then i will sometimes obtain a strictly lower realized
payoff when playing s∗i than he would have obtained by playing A. To see this, consider thecase when i has valuation v∗i and all other players have valuation s∗i (v∗i ). Player j follows
strategy A and so will bid s∗i (v∗i ) at these valuations. All players k , i, j play sensible strategies and so will bid no more than s∗i (v∗i ). Consequently, when player i follows strategy s∗i ,his bid will equal player j’s bid so that sometimes player i will fail to win the good and willobtain a realized payoff of zero. Had player i instead followed strategy A, he would have bidv∗i > s∗i (v∗i ), won the good for sure and obtained a realized payoff of v∗i − s∗i (v∗i ) > 0.
Second, note that if strategy profiles s0 and s00 are A-associated, then either s0j = A or
s00j = A. Combining these observations and assuming without loss of generality that s0j = A,
we have(12)

Ui (A, s0−i ) > Ui (s∗i , s0−i ).

Next, note that weak dominance of A implies that
(13)

Ui (A, s00−i ) ≥ Ui (s∗i , s00−i ).

Summing (12) and (13), we obtain the condition for strict GR-dominance in Definition 1.
Again applying Theorem 4, we see that bidding one’s own valuation is uniquely stochastically stable under these conditions.
Proposition 4. Let Bi = Vi for all i, valuations vi be iid with full support on Vi and strategies
be sensible. When the second price auction is played under the dynamics (9) with gi strictlyincreasing for all i ∈ N, and all f ∈ F preserve A-association and satisfy fi (sA ) = sA for alli ∈ N, then bidding one’s own valuation is uniquely stochastically stable.
In summary, bidding one’s own valuation in the second price auction is robust to a large
range of behavioral rules. Whether players are low rationality or high rationality, whether
they are homogeneous or diverse in their levels of rationality, the stability of bidding one’s
own valuation is preserved.
This concludes the main body of the paper.

–19–

Appendix
A. Proofs
A.1 Additional definitions and useful results
For parameter value η, strategy profiles s, s0 ∈ S, let Pη (s, s0 ) denote the probability that st+1 = s0
conditional on st = s.
Define a new Markov process on S, denoted Piη , by adjusting the original process by setting q j = 0
for all j , i. Let Piη (s, s0 ) denote the probability that st+1 = s0 conditional on st = s. Observe that, forall η > 0, s, s0 ∈ S, we have
(14)



Pη s, s0 = ∏ Piη s, (s0i , s−i ) .
i∈N

Define cost functions
(15)


η
η̂
lim
0
0
η→0 −η log Pi (s, s ) if Pi (s, s ) > 0 for some η̂ > 0,0ci (s, s ) :=∞otherwise .

and let c(s, s0 ) be the equivalent quantity after replacing Piη by Pη .

Simple algebra shows that, for the updating rule in our model, we have(16)

ci (s, s0 ) :=




0



if s0 = s,



k−1
k−1
maxxi ∈Si Ui xi , B−i(s) −Ui s0i , B−i(s) if s0i , si , s0−i = s−i ,∞otherwise .

We adopt the convention that ∞ > ∞.

We say that s00 A-dominates s0 if s00i = A for all i such that s0i = A.
Definition 4. c(·, ·) is asymmetric (towards A) if, for any s, s0 , s̃ such that s, s̃ are A-associated, there
exists s̃0 such that• s̃0 A-dominates s̃,• s0 , s̃0 are A-associated, and• c(s, s0 ) ≥ c(s̃, s̃0 ).
Definition 5. c(·, ·) is strictly asymmetric (towards A) if(a) for any s , sA , c(sA , s) > 0, and–20–

(b) for any s, s0 , s̃ such that s, s̃ are A-associated, there exists s̃0 such that– s̃0 A-dominates s̃,– s0 , s̃0 are A-associated, and– either c(s̃, s̃0 ) = 0 or c(s, s0 ) > c(s̃, s̃0 ).
Note that Definitions 4 and 5 can be applied to both c(·, ·) and to ci (·, ·).
Theorem N (Newton, 2020, 2019).
Let Pη , {Piη }i∈N satisfy (14). (i) If ci (·, ·) is asymmetric for all i ∈ N, then c(·, ·) is asymmetric(Newton, 2020, Theorem 3 ). (ii) If ci (·, ·) is strictly asymmetric for all i ∈ N, then c(·, ·) is strictly
asymmetric (Newton, 2019, Theorem 3).
Theorem P (Peski, 2010, Theorem 1).
(i) If c(·, ·) is asymmetric, then sA is stochastically stable. (ii) If c(·, ·) is strictly asymmetric, then sA
is uniquely stochastically stable.

A.2 Proofs for Section 4
Lemma 1. Let s, s̃ be A-associated. If sA is GR-dominant, then Bk (s), Bk (s̃) are A-associated for all
k ≥ 1.
Proof. If s, s̃ are A-associated, then by GR-dominance of sA , in particular expression (5), we have(17)

Ui (A, s̃−i ) − max Ui (xi , s̃−i ) ≥ max Ui (xi , s−i ) −Ui (A, s−i ).
xi ,A

xi ,A

If B1i (s) , A, we have(18)

max Ui (si , s−i ) −Ui (A, s−i ) > 0,si ,Aso combining (17) and (18) we obtain(19)

Ui (A, s̃−i ) − max Ui (xi , s̃−i ) > 0.
xi ,ATherefore, B1i (s̃) = A. This holds for all i such that B1i (s) , A, therefore B1i (s), B1i (s̃) are A-associated.
Iterating the above argument, we obtain that Bki (s), Bki (s̃) are A-associated for k = 2, 3, . . ..

Lemma 2. (i) If sA is GR-dominant, then, for all i ∈ N, ci is asymmetric towards A. (ii) If sA is strictly
GR-dominant, then, for all i ∈ N, ci is strictly asymmetric towards A.

–21–

Proof. Note that as sA is A-associated with itself, GR-dominance of sA and uniqueness of best responses implies that(20)

Bk (sA ) = sA

for all k ≥ 0.

If s , sA , then either s−i , sA−i , in which case ci (sA , s) = ∞, or s−i = sA−i , si , A, in which case
(21)

A
k−1 A
ci (sA , s) |{z}= max Ui (xi , Bk−1−i (s )) −Ui (si , B−i (s ))by (16)xi ∈Si= max Ui (xi , sA ) −Ui (si , sA )|{z}
xi ∈Siby (20)= Ui (A, sA ) −Ui (si , sA )> 0.

Therefore, the condition in Definition 5a is satisfied.
Now consider s, s0 , s̃ ∈ S such that s, s̃ are A-associated. If sA is GR-dominant, it follows from Lemma
1 that(22)

Bk (s), Bk (s̃) are A-associated for all k ≥ 1.

Case 1: s = s0 or s0i = A or ci (s, s0 ) = ∞ or s̃i = A.
If ci (s, s0 ) = ∞, let s̃0 = sA . The conditions in Definitions 4 and 5b are satisfied.
If ci (s, s0 ) is finite, let s̃0 = s̃. (16) implies ci (s̃, s̃0 ) = 0, therefore the conditions in Definitions 4 and5b are satisfied.
Case 2: s , s0 and s0i , A and ci (s, s0 ) is finite and s̃i , A.
(16) together with finiteness of ci (s, s0 ) implies s−i = s0−i . s , s0 and s0i , A then imply that si = A. Lets̃0 be such that s̃0−i = s̃−i , s̃0i = A.
If ci (s̃, s̃0 ) = 0, then the conditions in Definitions 4 and 5b are satisfied.

If ci (s̃, s̃0 ) > 0, then
(23)

0 k−1
ci (s, s0 ) |{z}= max Ui (xi , Bk−1−i (s)) −Ui (si , B−i (s))
by (16)xi ∈Sik−1≥ Ui (A, Bk−1−i (s)) − max Ui (xi , B−i (s))
xi ,A

≥
|{z}

xi ,A

by (22)and GR-dominance

=
|{z}

k−1
max Ui (xi , B−i(s̃)) −Ui (A, Bk−1−i (s̃))ci (s̃, s̃0 ).

by (16)and c(s̃,s̃0 )>0–22–

That is, the condition in Definition 4 as satisfied. Further note that if sA is strictly GR-dominant, then
the weak inequality in (23) due to GR-dominance becomes a strict inequality, so that the condition in
Definition 5b is satisfied.
Lemma 3. (i) If sA is GR-dominant, then c is asymmetric towards A. (ii) If sA is strictly GR-dominant,then c is strictly asymmetric towards A.
Proof. (i) GR-dominance of sA and Lemma 2(i) together imply that, for all i ∈ N, ci is asymmetrictowards A. Theorem N(i) then implies that c is asymmetric towards A. (ii) Strict GR-dominance of sA
and Lemma 2(ii) together imply that, for all i ∈ N, ci is strictly asymmetric towards A. Theorem N(ii)then implies that c is strictly asymmetric towards A.

Proof of Theorem 1.
Assume sA is GR-dominant. Lemma 3(i) and Theorem P(i) together imply stochastic stability of sA .
Assume sA is strictly GR-dominant. Lemma 3(ii) and Theorem P(ii) together imply unique stochastic
stability of sA .

Proof of Theorem 2.
Let player i be level 0. Recall that when i updates his strategy, each strategy in Si is chosen withprobability 1/|Si |. This probability is independent of η and s−i , so (15) gives us ci (si , (s0i , s−i )) = 0 for
all s, s0i . This ci satisfies Definition 4, so ci is asymmetric.
Therefore, even if some players are level 0, Lemma 3(i) and the first part of Theorem 1 continue tohold. Therefore, if sA is GR-dominant, then sA is stochastically stable.
To prove the second part of the Theorem, let i have at least two strategies. Let s∗ be stochasticallystable. Consider s0i ∈ Si such that s0i , s∗i . Then ci (s∗ , (s0i , s∗−i )) = 0, therefore c(s∗ , (s0i , s∗−i )) = 0. It
follows from the tree characterization of stochastically stable states (see, e.g. Young, 1993a) that(s0i , s∗−i ) must also be stochastically stable.


A.3 Proofs for Section 5
Proof of Proposition 1.
Step 1First we show that if A is (strictly) risk dominant, then sA is (strictly) GR-dominant. Note that condition (5) for GR-dominance reduces to(24)

Ui (A, s0−i ) +Ui (A, s00−i ) ≥ Ui (B, s0−i ) +Ui (B, s00−i )for all i ∈ N, s0 , s00 A-associated.

Now, if s0 , s00 are A-associated, then for all i,(25)

Ui (A, s0−i ) −Ui (B, s0−i )

–23–

=
|{z}

∑ wi j (aAA − aBA ) − ∑ wi j (aBB − aAB )by (6) j∈Nr{i}s0j =Aj∈Nr{i}s0j =B≥|{z}j∈Nr{i}s0j =B∑ wi j (aBB − aAB ) − ∑ wi j (aAA − aBA )j∈Nr{i}by (7)
s0j =A≥|{z}∑ wi j (aBB − aAB ) − ∑ wi j (aAA − aBA )j∈Nr{i}by A-association
s00j =Bof s0 , s00

j∈Nr{i}s00j =A= Ui (B, s00−i ) −Ui (A, s00−i ).
|{z}by (6)

That is, (24) holds and sA is GR-dominant. If risk dominance is strict, then the first ≥ in (25) is strict,therefore (24) holds strictly and sA is strictly GR-dominant.
Step 2The definition of risk dominance implies that at least one of A, B is risk dominant.
Non-strict
By Step 1, if A is risk dominant, then sA is GR-dominant. Theorem 1 then implies that sA is stochastically stable.
If A is not risk dominant, then B is strictly risk dominant. Step 1 then implies that sB is strictly
GR-dominant and Theorem 1 implies that sB is uniquely stochastically stable. Therefore, sA is notstochastically stable.
StrictBy Step 1, if A is strictly risk dominant, then sA is strictly GR-dominant. Theorem 1 then implies thatsA is uniquely stochastically stable.
If A is not strictly risk dominant, then B is risk dominant. Step 1 then implies that sB is GR-dominant
and Theorem 1 implies that sB is stochastically stable. Therefore, sA is not uniquely stochasticallystable.

Proof of Proposition 2.
Risk dominance of A and Step 1 of the proof of Proposition 1 together imply that sA is GR-dominant.
Theorem 2 then implies that sA is stochastically stable
Let s0 = (B, sA−i ). Let s00 be such that s0i , s00i for all i ∈ N. Note that Bk (s0 ) = s00 for odd k and Bk (s0 ) = s0
for even k.
From sA , player i switches to B with positive probability. Consequently, c(sA , s0 ) = ci (sA , s0 ) = 0. It
follows from the tree characterization of stochastically stable states that s0 is also stochastically stable.
k odd
Let s∗ be any strategy profile. From s0 , with positive probability (that does not approach zero asη → 0), all players in the set { j , i : s∗j = B} update their strategies, best responding to Bk−1 (s0 ) = s0
by playing B. Denote the resulting profile s∗∗ . Note that c(s0 , s∗∗ ) = 0.

–24–

If s∗ = s∗∗ , then it follows from the tree characterization of stochastically stable states that s∗ isstochastically stable.
∗∗
If s∗ , s∗∗ , then it must be that s∗i , s∗∗i = B. From s , with positive probability (that does not
approach zero as η → 0) player i updates his strategy and switches to A. Therefore, c(s∗∗ , s∗ ) = 0. It
follows from the tree characterization of stochastically stable states that s∗ is stochastically stable.

k evenConsider a profile s. Note that B1i (s) is independent of si . If B1i (s) = A (respectively, B), then for j , i,
B2j (s) = A (respectively, B), B3i (s) = A (respectively, B), and so on. In particular, Bik−1 (s) = B1i (s) is
independent of si . Therefore, the choice probabilities of j , i are independent of si .
Now consider that if i were of level k ≥ 1, Proposition 1 would imply that sA is the unique stochastically stable profile. As the behavior of j , i is independent of si , it must be that at any stochasticallystable profile s∗ we have s∗j = sAj = A. Therefore no profile other than sA and s0 is stochasticallystable.


A.4 Proof of Theorem 3
Applying (15) to (9), we have

(26)




0
if s0 = s,ci (s, s0 ) := gi (ϒi (s0i , fi (s))) if s0i , si , s0−i = s−i ,∞otherwise .

Lemma 4. Let f preserve A-association. (i) If sA is GR-dominant, then, for all i ∈ N, ci is asymmetrictowards A. (ii) If sA is strictly GR-dominant and, for all i ∈ N, gi is strictly increasing and fi (sA ) = sA ,then, for all i ∈ N, ci is strictly asymmetric towards A.
Proof. Consider s, s0 , s̃ ∈ S such that s, s̃ are A-associated. As f preserves A-association, we have(27)

fi (s), fi (s̃) are A-associated.

Case 1: s = s0 or s0i = A or ci (s, s0 ) = ∞ or s̃i = A.
If ci (s, s0 ) = ∞, let s̃0 = sA . The conditions in Definitions 4 and 5b are satisfied.
If ci (s, s0 ) is finite, let s̃0 = s̃. (26) implies ci (s̃, s̃0 ) = 0, therefore the conditions in Definitions 4 and5b are satisfied.
Case 2: s , s0 and s0i , A and ci (s, s0 ) is finite and s̃i , A.
(26) and finiteness of ci (s, s0 ) implies s−i = s0−i . s , s0 and s0i , A then imply that si = A. Let s̃0 be suchthat s̃0−i = s̃−i , s̃0i = A.
If ci (s̃, s̃0 ) = 0, then the conditions in Definitions 4 and 5b are satisfied.

–25–

If ci (s̃, s̃0 ) > 0, then(28)ci (s, s0 ) |{z}= gi ϒi (s0i , fi (s))
by (26)
0= gi max Ui (xi , ( fi (s))−i ) −Ui (si , ( fi (s))−i )|{z}
xi ∈Siby (8)

≥ gi Ui (A, ( fi (s))−i ) − max Ui (xi , ( fi (s))−i )
xi ,A


≥
gi max Ui (xi , ( fi (s̃))−i ) −Ui (A, ( fi (s̃))−i )
|{z}
xi ,A

by (27)and GR-dominance


0
=
g
ϒ
(
s̃
,
f
(
s̃))
i
i
i
i
|{z}

by (8)=|{z}c(s̃, s̃0 ).

by (26)and c(s̃,s̃0 )>0That is, the condition in Definition 4 as satisfied. Further note that if sA is strictly GR-dominant
and gi is strictly increasing, then the weak inequality in (28) due to GR-dominance becomes a strict
inequality, so that the condition in Definition 5b is satisfied.
For the remainder of this proof, assume that f (sA ) = sA , sA is strictly GR-dominant, and gi is strictlyincreasing.
Note that, as sA is A-associated with itself, strict GR-dominance of sA implies that(29)

arg max Ui (xi , (sA )−i ) = {A}.
xi ∈SiIf s , sA , then either s−i , sA−i , in which case c(sA , s) = ∞, or s−i = sA−i , si , A, in which case(30)= gi ϒi (si , fi (sA ))c(sA , s) |{z}by (26)



A
A
=
g
max
U
(x
,
(
f
(s
))
)
−U
(s
,
(
f
(s
))
)
−i
i i
i
−i
|{z} i xi ∈Si i i i

by (8)=|{z}by f (sA )=sA

>
|{z}



A
A
gi max Ui (xi , (s )−i ) −Ui (si , (s )−i )xi ∈Si0.

by si ,A, (29),gi strictly increasing

Therefore, the condition in Definition 5a is satisfied.

Proof of Theorem 3.
Assume sA is GR-dominant. Lemma 4(i) implies that, for all i ∈ N, ci is asymmetric towards A.

–26–

Theorem N(i) then implies that c is asymmetric towards A. Theorem P(i) then implies that sA is
stochastically stable.
Assume sA is strictly GR-dominant and, for all i ∈ N, gi is strictly increasing and fi (sA ) = sA . Lemma
4(ii) implies that, for all i ∈ N, ci is strictly asymmetric towards A. Theorem N(ii) then implies thatc is strictly asymmetric towards A. Theorem P(ii) then implies that sA is uniquely stochasticallystable.


A.5 Proof of Theorem 4
Let Pε be the Markov kernel of the process with F = { f1 , . . . , fn }. Define processes Pε, f1 , . . . Pε, fn as
identical to Pε except that F = { f1 }, . . . , F = { fn } respectively. Note thatn(31)

Pε = ∑ ϕ( fm ) Pε, fi .
i=1

Let cost functions for Pε, f1 , . . . Pε, fn be given by c f1 , . . . , c fn .
Proof of Theorem 4.
Assume sA is GR-dominant. Lemma 4(i) implies that, for all i ∈ N, fm ∈ F, cifm is asymmetric towards
A. Theorem N(i) then implies that, for m = 1, . . . , n , c fm is asymmetric towards A. Given (31), thatis Pε is a convex combination of Pε, f1 , . . . Pε, fn , this implies that c is asymmetric towards A (Newton,
2020, Theorem 1). Theorem P(i) then implies that sA is stochastically stable.
Assume sA is strictly GR-dominant and, for all i ∈ N, gi is strictly increasing and fi (sA ) = sA . Lemma
4(ii) implies that, for all i ∈ N, fm ∈ F, cifm is strictly asymmetric towards A. Theorem N(ii) thenimplies that, for m = 1, . . . , n , c fm is strictly asymmetric towards A. Given (31), that is Pε is a convex
combination of Pε, f1 , . . . Pε, fn , this implies that c is strictly asymmetric towards A (Newton, 2019,
Theorem 1). Theorem P(ii) then implies that sA is uniquely stochastically stable.


A.6 Proofs for Section 7
Proof of Theorem 5.
Non-strict
If A is a weakly dominant strategy for i, then(32)

Ui (A, s−i ) ≥ max Ui (xi , s−i ) for all s−i ,xi ,Aand consequently(33)

Ui (A, s0−i ) +Ui (A, s00−i ) ≥ max Ui (si , s0−i ) + max Ui (si , s00−i ).
si ,A

si ,A

–27–

Therefore, if A is weakly dominant for all i ∈ N, then (33) holds for all i, s0 , s00 . Therefore, sA is
GR-dominant.
StrictIf A is a strictly dominant strategy for i, then(34)

Ui (A, s0−i ) > max Ui (xi , s−i ) for all s−i ,xi ,Aand consequently(35)

Ui (A, s0−i ) +Ui (A, s00−i ) > max Ui (si , s0−i ) + max Ui (si , s00−i ).
si ,A

si ,A

Therefore, if A is strictly dominant for all i ∈ N, then (35) holds for all i, s0 , s00 . Therefore, sA is strictly
GR-dominant.
Proof of Proposition 3.
For all i ∈ N, it is a weakly dominant strategy for player i to bid his valuation. Therefore, sA is
composed of weakly dominant strategies and Theorem 5 implies that sA is GR-dominant. Theorem 4
then implies that sA is stochastically stable.

Proof of Proposition 4.
Let s0 and s00 be A-associated.
Consider s∗i , A. There must exist v∗i ∈ Vi such that s∗i (v∗i ) , v∗i . The restriction to sensible strategies
implies that s∗i (v∗i ) ≤ v∗i , so it must be that s∗i (v∗i ) < v∗i . Note that s∗i (v∗i ) ∈ Bi = Vi .

As s0 and s00 are A-associated, for a given player j , i, it must be that either s0j = A or s00j = A. Without
loss of generality assume that s0j = A.
Case 1: Player i has valuation v∗i and all other players k , i have valuation v∗k = s∗i (v∗i ).

As s0j = A, we have s0j (v∗j ) = s0j (s∗i (v∗i )) = s∗i (v∗i ).
Sensible strategies imply that for k , i, j, we have s0k (v∗k ) = s0k (s∗i (v∗i )) ≤ s∗i (v∗i ).

Consider strategy profile (s∗i , s0−i ). Player i’s bid is s∗i (v∗i ). This equals player j’s bid and is greaterthan or equal to all other bids. Therefore, player i wins the good and obtains a realized payoff ofv∗i − s∗i (v∗i ) > 0 with probability at most one half.
Consider strategy profile (A, s0−i ). Player i’s bid is v∗i . This is strictly greater than all other bids. The
second highest bid (possibly tied) is player j’s bid of s∗i (v∗i ). Therefore, player i wins the good andobtains a realized payoff of v∗i − s∗i (v∗i ) > 0 with probability one.
Therefore at valuations (v∗k )k∈N , player i obtains a strictly higher realized payoff from (A, s0−i ) than hedoes from (s∗i , s0−i ).

Case 2: Consider all valuations (vk )k∈N other than (v∗k )k∈N considered in Case 1. By standard arguments for second price auctions, at any realized valuations, a player with strategy A could not haveobtained a strictly higher payoff by playing a strategy other than A.

–28–

Therefore at valuations (vk )k∈N , player i obtains at least as high a payoff from (A, s0−i ) as he does from(s∗i , s0−i ).
As vk are iid with full support on Vk = Vi , Case 1 occurs with positive probability. Therefore, combining Case 1 and Case 2, we obtain(36)

Ui (A, s0−i ) > Ui (s∗i , s0−i ).

Next, note that weak dominance of A implies that(37)

Ui (A, s00−i ) ≥ Ui (s∗i , s00−i ).

Summing (36) and (37),(38)

Ui (A, s0−i ) +Ui (A, s00−i ) > Ui (s∗i , s0−i ) +Ui (s∗i , s00−i ).

Our argument and hence (38) holds for any i ∈ N and A-associated s0 and s00 . That is, sA is strictly
GR-dominant according to Definition 1.
Applying Theorem 4, it follows that sA is uniquely stochastically stable.



References
Alós-Ferrer, C. and Netzer, N. (2010). The logit-response dynamics. Games and Economic
Behavior, 68:413–427.
Bacharach, M. (1992). Backward induction and beliefs about oneself. Synthese, 91(3):247–
284.
Battalio, R., Samuelson, L., and Van Huyck, J. (2001). Optimization incentives and coordination failure in laboratory stag hunt games. Econometrica, 69(3):749–764.
Block, H. and Marschak, J. (1959). Random orderings and stochastic theories of response.
Working paper, Cowles Foundation for Research in Economics, Yale University.
Blume, L. E. (1993). The statistical mechanics of strategic interaction. Games and Economic
Behavior, 5(3):387 – 424.
Blume, L. E. (1996). Population games. Working Papers 96-04-022, Santa Fe Institute.
Blume, L. E. (2003). How noise matters. Games and Economic Behavior, 44(2):251–271.
Cabrales, A., Nagel, R., and Armenter, R. (2007). Equilibrium selection through incomplete
information in coordination games: an experimental study. Experimental Economics,
10(3):221–234.
–29–

Conlisk, J. (1993a). Adaptation in games: Two solutions to the crawford puzzle. Journal of
Economic Behavior & Organization, 22(1):25–50.
Conlisk, J. (1993b). Adaptive tactics in games: Further solutions to the crawford puzzle.
Journal of Economic Behavior & Organization, 22(1):51–68.
Cox, D. R. (1958). The regression analysis of binary sequences. Journal of the Royal
Statistical Society. Series B (Methodological), pages 215–242.
Crawford, V. (2007). Modeling behavior in novel strategic situations via level-k thinking.
Conference slides - North American Economic Science Association Meetings.
Crawford, V. P. (1974). Learning the optimal strategy in a zero-sum game. Econometrica:
Journal of the Econometric Society, pages 885–891.
Crawford, V. P. (2019). Experiments on cognition, communication, coordination, and cooperation in relationships.
Duffy, J. and Nagel, R. (1997). On the robustness of behaviour in experimental ‘beauty
contest’games. The Economic Journal, 107(445):1684–1700.
Foster, D. and Young, H. P. (1990). Stochastic evolutionary game dynamics. Theoretical
Population Biology, 38:219–232.
Geanakoplos, J. and Gray, L. (1991). When seeing further is not seeing better. Bulletin of
the Santa Fe Institute, 6(2):1–6.
Gill, D. and Prowse, V. (2016). Cognitive ability, character skills, and learning to play
equilibrium: A level-k analysis. Journal of Political Economy, 124(6):1619–1676.
Goeree, J. K. and Holt, C. A. (2004). A model of noisy introspection. Games and Economic
Behavior, 46(2):365–382.
Harsanyi, J. C. and Selten, R. (1988). A general theory of equilibrium selection in games.
MIT Press Books, 1.
Heinemann, F., Nagel, R., and Ockenfels, P. (2004). The theory of global games on test:
experimental analysis of coordination games with public and private information. Econometrica, 72(5):1583–1599.
Heller, Y. (2015). Three steps ahead. Theoretical Economics, 10(1):203–241.
Ho, T.-H. and Su, X. (2013). A dynamic level-k model in sequential games. Management
Science, 59(2):452–469.
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.
–30–

Iijima, R. (2015). Iterated generalized half-dominance and global game selection. Journalof Economic Theory, 159:120–136.
Kandori, M., Mailath, G. J., and Rob, R. (1993). Learning, mutation, and long run equilibria
in games. Econometrica, 61(1):29–56.
Khan, A. and Peeters, R. (2014). Cognitive hierarchies in adaptive play. International
Journal of Game Theory, 43(4):903–924.
Lim, W. and Neary, P. R. (2016). An experimental investigation of stochastic adjustment
dynamics. Games and Economic Behavior, 100:208–219.
Mäs, M. and Nax, H. H. (2016). A behavioral study of “noise” in coordination games.
Journal of Economic Theory, 162:195–208.
Matros, A. (2003). Clever agents in adaptive learning. Journal of Economic Theory,111(1):110–124.
Mohlin, E. (2012).
75(1):299–318.

Evolution of theories of mind.

Games and Economic Behavior,

Morris, S., Rob, R., and Shin, H. S. (1995). p-dominance and belief potential. Econometrica,
63:145–157.
Myatt, D. P. and Wallace, C. (2003). Sophisticated play by idiosyncratic agents. Journal of
Evolutionary Economics, 13(3):319–345.
Myerson, R. (1978). Refinements of the Nash equilibrium concept. International Journal ofGame Theory, 7:73–80.
Nagel, R. (1995). Unraveling in guessing games: An experimental study. American Economic Review, 85(5):1313–1326.
Nash, J. F. (1950). Equilibrium points in n-person games. Proceedings of the National
Academy of Sciences, 36(1):48–49.
Newton, J. (2017). Shared intentions: The evolution of collaboration. Games and Economic
Behavior, 104:517 – 534.
Newton, J. (2018). Evolutionary game theory: A renaissance. Games, 9(2):31.
Newton, J. (2019). Combining strictly asymmetric choice rules. SSRN Working Paper Series
3433736.
Newton, J. (2020). Conventions under heterogeneous behavioural rules. Review of Economic
Studies, (https://doi.org/10.1093/restud/rdaa063).
Peski, M. (2010). Generalized risk-dominance and asymmetric dynamics. Journal of Economic Theory, 145(1):216 – 248.
–31–

Proto, E., Rustichini, A., and Sofianos, A. (2019). Intelligence, personality, and gains fromcooperation in repeated interactions. Journal of Political Economy, 127(3):1351–1390.
Robalino, N. and Robson, A. (2016). The evolution of strategic sophistication. American
Economic Review, 106(4):1046–1072.
Rusch, H. (2019). The evolution of collaboration in symmetric 2×2-games with imperfectrecognition of types. Games and Economic Behavior.
Sáez-Martı, M. and Weibull, J. W. (1999). Clever agents in young’s evolutionary bargaining
model. Journal of Economic Theory, 86(2):268–279.
Sandholm, W. H. (2010). Population games and evolutionary dynamics. Economic learningand social evolution. Cambridge, Mass. MIT Press.
Selten, R. (1991). Anticipatory learning in two-person games. In Game equilibrium models
I, pages 98–154. Springer.
Stahl, D. O. (1993). Evolution of smartn players. Games and Economic Behavior, 5(4):604–
617.
Stahl, D. O. (1999). Evidence based rules and learning in symmetric normal-form games.
International Journal of Game Theory, 28(1):111–130.
Stahl, D. O. (2000). Rule learning in symmetric normal-form games: theory and evidence.
Games and Economic Behavior, 32(1):105–138.
Stahl, D. O. and Wilson, P. W. (1994). Experimental evidence on players’ models of otherplayers. Journal of Economic Behavior and Organization, 25(3):309–327.
Stennek, J. (2000). The survival value of assuming others to be rational. International
Journal of Game Theory, 29(2):147–163.
Tang, F.-F. (2001). Anticipatory learning in two-person games: some experimental results.
Journal of economic behavior & organization, 44(2):221–232.
Van Huyck, J. B., Battalio, R. C., and Beil, R. O. (1990). Tacit coordination games, strategic
uncertainty, and coordination failure. American Economic Review, pages 234–248.
Young, H. P. (1993a). The evolution of conventions. Econometrica, 61(1):57–84.
Young, H. P. (1993b). An evolutionary model of bargaining. Journal of Economic Theory,59(1):145 – 168.

–32–