Stability of strict equilibria in best experienced payoff dynamics: Simple formulas and applications

Available online at www.sciencedirect.com ScienceDirect Journal of Economic Theory 206 (2022) 105553 www.elsevier.com/locate/jet Stability of strict equilibria in best experienced payoff dynamics: Simple formulas and applications ✩ Segismundo S. Izquierdo a,∗, Luis R. Izquierdo b aBioEcoUva, Department of Industrial Organization, Universidad de Valladolid, Dr. Mergelina s/n, 47011 Valladolid, Spain bDepartment of Management Engineering, Universidad de Burgos, Spain Received 30 December 2021; final version received 6 September 2022; accepted 11 September 2022 Available online 13 September 2022 Dedicated to the memory of Bill Sandholm Abstract We consider a family of population game dynamics known as Best Experienced Payoff Dynamics. Under these dynamics, when agents are given the opportunity to revise their strategy, they test some of their possible strategies a fixed number of times. Crucially, each strategy is tested against a new randomly drawn set of opponents. The revising agent then chooses the strategy whose total payoff was highest in the test, breaking ties according to a given tie-breaking rule. Strict Nash equilibria are rest points of these dynamics, but need not be stable. We provide some simple formulas and algorithms to determine the stability or instability of strict Nash equilibria. ©2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/). ✩This paper comes as a result of a wonderful and inspiring collaboration with the late Bill Sandholm. We feel extremely fortunate for having had the opportunity to work with such an exceptional and distinguished scholar, master and friend. We also thank the Economics Department of the University of Wisconsin-Madison for their continuing support (specially Marzena Rostek, Daniel Quint and Ananth Seshadri), and Srinivas Arigapudi for helpful comments. Financial support from the Spanish State Research Agency (PID2020-118906GB-I00/AEI/10.13039/501100011033), from the Spanish Ministry of Science, Innovation and Universities (PRX19/00113, PRX21/00295) and from the Fulbright Commission (US-Spain) (PRX19/00113, PRX21/00295), is gratefully acknowledged. Luis R. Izquierdo is grateful to the Center for Control, Dynamical Systems, and Computation at UC Santa Barbara, where part of this work was done, for their hospitality. *Corresponding author at: Department of Industrial Organization, Universidad de Valladolid, Dr. Mergelina s/n, 47011 Valladolid, Spain. E-mail address: [email protected]a.es (S.S. Izquierdo). https://doi.org/10.1016/j.jet.2022.105553 0022-0531/©2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/). S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 JEL classification: C72; C73 Keywords: Best experienced payoff; Procedural rationality; Payoff-sampling dynamics; Stability 1. Introduction Most dynamics in Evolutionary Game Theory can be neatly seen as a combination of a population game and a revision protocol (Sandholm, 2010). The population game assigns to each population state a vector of payoffs, one for each strategy in the population. The revision protocol specifies how agents, using the payoff assigned to each strategy, update their current strategy. A crucial assumption embedded in this framework is that, at any population state, there is one single payoff assigned to each strategy. In population games where agents are matched to play a symmetric normal form game, the payoff assigned to each strategy is often the expected payoff the agent will obtain when using that strategy. But how can agents know this expected payoff? Unless there is complete matching, agents somehow know the exact population state, or agents are explicitly communicated the precise expected payoff for each strategy, it seems unrealistic to assume that they will all share exactly the same expectations for any given strategy. From this point of view, it is noteworthy that many evolutionary dynamics from the economics literature are informationally demanding in one important respect: they require agents to be fully informed about the population’s current aggregate behavior. This assumption seems rather strong in the large-population contexts to which evolutionary models are most naturally applied. In many situations, it seems more natural to assume that agents acquire information by interacting with only a sample of the population, rather than assuming that they have access to accurate statistics of the whole population. There are two distinct lines of research that follow this approach while keeping the assumption that agents respond optimally to the information they have. The first line assumes that agents take samples of the actions being played in the population, and they use these samples to make inferences about the distribution of actions in the whole population, and to best respond to the estimates thus formed. This is the approach followed by Sandholm (2001), Kosfeld et al. (2002), Osborne and Rubinstein (2003), Kreindler and Young (2013), Oyama et al. (2015), Heller and Mohlin (2018), Salant and Cherry (2020), and Sawa and Wu (2021). Under this approach, note that agents must be aware of the population game they are playing, so they can best reply to their point estimates of the population distribution of actions.1 A second approach –significantly less demanding on agents’ informational and computational skills– was pioneered by Osborne and Rubinstein (1998) and Sethi (2000). Here, revising agents try out a subset of the available strategies by playing them against randomly drawn counterparts, and then choose the strategy that performed best in the test. Crucially, each game is played against new randomly drawn counterparts, so sub-optimal strategies may be selected in the test if they happened to be lucky in the random sampling of co-players. In this approach, note that agents do not even need to know that they are playing a game. Agents who follow this revision protocol have been called procedurally rational agents (Osborne and Rubinstein, 1998), and the evolutionary dynamics they produce are the so-called payoff-sampling dynamics 1The dynamics induced by this protocol have been termed sampling best response dynamics (see e.g. Oyama et al. (2015)) and action-sampling dynamics (see e.g. Sethi (2021); Arigapudi et al. (2021, 2022)). 2 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 (Sethi, 2021; Arigapudi et al., 2021, 2022) or, more generally, Best Experienced Payoff (BEP) dynamics (Sandholm et al., 2019).2These dynamics are the main object of study in this paper. The procedurally rational agents described before, and their associated BEP dynamics and equilibria, have been used in a variety of applications including consumer choice procedures and product pricing strategies (Spiegler, 2006a), markets with asymmetric information (Spiegler, 2006b), trust and delegation of control (Rowthorn and Sethi, 2008), the Traveler’s Dilemma (Berkemer, 2008), market entry (Chmura and Güth, 2011), ultimatum bargaining (Mie¸kisz and Ramsza, 2013), use of common-pool resources (Cárdenas et al., 2015), contributions to public goods (Mantilla et al., 2020), the Centipede game (Sandholm et al., 2019; Izquierdo and Izquierdo, 2021), the Prisoner’s Dilemma (Arigapudi et al., 2021), and coordination problems (Izquierdo et al., 2022). Sethi (2021) studies the equilibria of these processes in symmetric, finitely repeated games, with several applications. Under BEP dynamics, strict Nash equilibria of a game correspond to states that are rest points, but they may not be stable. Sandholm et al. (2020), building on Sethi’s (2000) pioneering work, provide several sufficient conditions for instability and for asymptotic stability of strict equilibria under BEP dynamics. Arigapudi et al. (2021) refine one of the most general sufficient stability conditions in Sandholm et al. (2020), providing a tighter one. While many of the stability and instability conditions in Sandholm et al. (2020)are really simple and can be immediately checked from the payoffs of the game, the most general stability condition (Theorem 2 II in Arigapudi et al. (2021)), and the most general instability condition (Proposition 5.4 in Sandholm et al. (2020)) are –if taken at face value– actually difficult to check, as they state a condition over all sets in a certain power set, or require finding a subset of strategies that satisfies some condition. Here we show that these general stability and instability conditions can be checked by conducting a simple analysis, whose complexity is equivalent to carrying out an iterated elimination of dominated strategies, and which admits a simple interpretation. We also provide some tighter tests for specific BEP dynamics. The rest of the paper is structured as follows. Section 2contains a short introduction to Best Experienced Payoff processes and their dynamics. In Section 3we summarize previous results on stability of strict equilibria, indicating also the new contributions in this paper. Section 4 presents the new stability tests and formulas, Section 5shows an application of our results to tacit coordination games, and in Section 6we state some conclusions. The proofs, and some additional information, have been grouped in an appendix. All figures in this paper can be easily replicated with open-source freely available software which also performs exact computations of rest points and exact linearization analyses (EvoDyn-3s (Izquierdo et al., 2018) for Figs. 1–4and BEP-TCG (Izquierdo and Izquierdo, 2022) for Figs. 5-8). 2. Best experienced payoff protocols and dynamics For notational simplicity, we keep our presentation to p-player symmetric games played in one population, but all our results can be easily extended to asymmetric games played in ppopulations. Following Sandholm et al. (2020), we consider a unit-mass population of agents who are matched to play a symmetric p-player normal form game G ={S, U}. This game is defined by 2The term payoff-sampling dynamics is used when revising agents test all their available actions. Sandholm et al. (2019) generalized payoff-sampling dynamics, allowing revising agents to consider subsets of their available actions. This generalization led to the so-called family of Best Experienced Payoff (BEP) dynamics. 3 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 a strategy set S={1, ..., n}, and a payoff function U:Sp→R, where U(i; j1, ..., jp−1)represents the payoff obtained by a strategy iplayer whose opponents play strategies j1, ..., jp−1. Our symmetry assumption requires that the value of Unot depend on the ordering of the last p−1 arguments. When p=2, we sometimes write Uij instead of U(i; j). Aggregate behavior in the population is described by a population state xin the simplex X={x∈Rn +:i∈Sxi=1}, with xirepresenting the fraction of agents in the population using strategy i∈S. The standard basis vector ei∈Xrepresents the pure (monomorphic) state at which all agents play strategy i. We consider Best Experienced Payoff (BEP) protocols defined by a triple (τ, κ, β). Under BEP protocols, agents occasionally revise their current strategy by conducting tests of alternative strategies. The first parameter, namely the test-set rule τ, indicates how the set of strategies to be tested is chosen. Specifically, here we consider the test-set rule τα, under which the revising agent, when considering whether to change his current strategy, will also test other α−1 randomly selected strategies in S(besides testing his current strategy). Naturally, α∈Nand 1 <α≤n. If all the strategies in Sare tested, i.e. if α=n, then we have the test-all rule, denoted by τall. The second parameter, called the number of trials κ∈N, specifies the number of times that each strategy will be played in the test. Thus, each strategy in the test set will be played by the revising agent over κmatches, with each match requiring a new independent sampling of p−1 co-players. The last parameter in the BEP protocol, namely the tie-breaking rule β, indicates the rule used to decide which strategy is selected when the best result (i.e. the greatest total payoff) in the tests is obtained by more than one strategy. We will omit the last parameter when our results are independent of the tie-breaking rule. Otherwise, we will focus on two tie-breaking rules. The uniform-if-tie rule, βunif, selects any of the strategies that obtain the best total payoff in the tests, each of these strategies with equal probability. This is the rule that has been considered in almost all cases in the literature. The stick-if-tie rule, βstick, chooses to keep using the current strategy if it obtains the best total payoff in the tests, and, otherwise, it breaks ties by random uniform selection among the strategies that obtained the best total payoff. Well-known results of Benaïm and Weibull (2003)show that the behavior of a large but finite population following the procedure above is closely approximated by the solution of the associated mean dynamic, a differential equation which describes the expected motion of the population from each state. This mean dynamic for BEP processes is (Sethi, 2000): ˙xi=wi(x) −xi(1) where wi(x) is the probability with which strategy iis selected by a revising agent, i.e., the probability that it is tested, it obtains the best total payoff, and, if there are ties, it is selected by the tie-breaking rule. The calculation of the term wi(x), i.e. the mean dynamic, for BEP(τα, κ, β) processes, was formalized by Sandholm et al. (2020). 3. Stability and instability under BEP dynamics. Antecedents and contribution 3.1. Background on stability and linear stability Consider a C1differential equation ˙x=V(x)defined on Xwhose forward solutions (x(t))t≥0 do not leave X. State x∗is a rest point or equilibrium of the dynamics if V(x∗) =0, so that the unique solution starting from x∗is stationary. 4 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 A rest point x∗is Lyapunov stable if for every neighborhood Oof x∗, there exists a neighborhood Oof x∗such that every forward solution that starts in O∩Xis contained in O. If x∗is not Lyapunov stable it is unstable. A rest point x∗is attracting if there is a neighborhood Oof x∗such that all solutions that start in O∩Xconverge to x∗. If a rest point x∗is Lyapunov stable and attracting, it is asymptotically stable. In this case, the maximal (relatively) open3set of states in Xfrom which solutions converge to x∗is called the basin of attraction of x∗. If the basin of attraction of x∗contains int(X), we call x∗almost globally asymptotically stable; if it is Xitself, we call x∗globally asymptotically stable. By the definition of the derivative, the value of Vin a (relative) neighborhood O∩Xof a rest point x∗can be approximated via V(x)=0+DV (x∗)(x −x∗)+o(|x−x∗|) where DV (x∗)is the Jacobian matrix of V(more precisely, the Jacobian of a C1extension of Vto Rnsuch that the first-order partial derivatives of the component functions of the extension are defined at x∗) evaluated at state x∗. The stability of x∗can be analyzed by considering the eigenvalues of DV (x∗)corresponding to those eigenvectors lying in the tangent space TX= {z∈Rn:izi=0}. If all such eigenvalues have negative real parts, then x∗is linearly stable. If any of those eigenvalues has positive real part, then x∗is linearly unstable. A linearly stable rest point is asymptotically stable, and solutions starting near the rest point converge to it at an exponential rate (Perko, 2001; Sandholm, 2010). 3.2. Linear stability analysis of strict Nash equilibria under BEP dynamics Focusing now on the BEP dynamics (1), consider a strict strategy sin a symmetric p-player game, i.e., a strategy ssuch that the strategy profile (s, s, ..., s) is a strict Nash equilibrium of the game. Following Osborne and Rubinstein’s (1998) pioneering study of rest points of the BEP(τall, κ, βunif)dynamic, and Sethi’s (2000) stability analysis of the BEP(τall, 1, βunif)dynamic, Sandholm et al. (2020)show that the linear stability analysis of a strict Nash equilibrium state es– a monomorphic state where all players use the same strict strategy s– under any BEP(τ, κ, β) dynamic, can be reduced to the analysis of an n ×nmatrix Vκ,s =(vκ,s ij )of total payoffs vκ,s ij , defined by vκ,s ij =(κ −1)U(i;s, s, ..., s) +U(i;j, s, ..., s) To simplify the notation, we will drop the superindex swhen it is clear that we are referring to a specific equilibrium strategy s, in which case we will use Vκand vκ ij . The Jacobian of the dynamics at the equilibrium escan be calculated from the terms in Vκ. The term vκ ij is the total payoff to strategy iwhen, over its κtrials, it meets exclusively players using the strict Nash strategy s, except in one trial, where exactly one of the (p −1)co-players uses strategy j. The reason why these are the only relevant payoffs for a linear stability analysis is that, in the proximity of the strict equilibrium, where xs=1 −, the probability of any random sample of ακ(p−1)co-players with more than one co-player choosing a strategy other than sis O(2). Thus, when αstrategies are tested, the relevant sampling events –those whose probability is O(1)or O(), but is not O(2)– are: 3A set is relatively open in Xif it is the intersection of Xwith an open set in Rn. 5 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 i) Those in which all the ακ(p−1)randomly sampled co-players use strategy s. In this case, a test of strategy sprovides the total payoff vκ ss and a test of strategy i= sprovides the total payoff vκ is. Since sis a strict Nash strategy, vκ ss >v κ is, so, if strategy sis in the test set, then it will be selected. ii) Those in which all but one of the sampled co-players use strategy sand exactly one co-player (the “deviating co-player”) uses strategy j= s. Assuming all strategies are tested: •If, in a battery of tests (for which n κ(p−1)co-players are sampled), the single deviating co-player using strategy jis met when testing strategy s, the total payoffs in the battery of tests are vκ sj (when testing s) and {vκ is}i∈S{s}(when testing the other strategies). Defining S2≡argmaxi=svκ is =argmaxi=sU(i; s, s, ..., s), we have that either the selected strategy belongs to S2, or the selected strategy is s, depending on the comparison of vκ sj and vκ ts ≡ maxi=svκ is. In case of equality, the tie-breaking rule would apply. •If the deviating co-player is met when testing strategy i= s, the total payoffs are vκ ss, vκ ij and {vκ ks}k∈S{s,i}. Since every element in {vκ ks}k∈S{s,i}is less than vκ ss, the selected strategy is either sor i, depending on the comparison of vκ ss and vκ ij . In case of equality, the tie-breaking rule would apply. To analyze the stability of a strict equilibrium state es, Sandholm et al. (2020) consider a change of variables that takes esto the origin 0(by eliminating the coordinate xs, given that n i=1xi=1) and show that the Jacobian of the dynamics at the origin is DW(0) =DW+(0) − I(n−1), where DW+(0)is a matrix of non-negative terms that can be easily calculated from the terms in Vκ, following the previous discussion. 3.3. Instability results A series of instability results (i.e. sufficient conditions for instability) can be derived from the analysis of Vκby considering that the Perron-Frobenius eigenvalue of DW+(0)is at least as large as the Perron-Frobenius eigenvalue of any principal submatrix of DW+(0), which is in turn bounded from below by the minimum sum of the elements in each of its columns (or rows). If the Perron-Frobenius eigenvalue of DW+(0)is greater than 1, then DW(0)has a real positive eigenvalue4and, consequently, esis unstable. A general condition that guarantees instability following this approach is provided by Proposition 5.4 (ii) in Sandholm et al. (2020), which states that esis linearly unstable under any BEP(τ α, κ, β) dynamic if, for some nonempty J⊆S{s}, (p −1)κ α−1 n−1 i∈J 1[vκ ij >v κ ss]+1[S2⊆J]1[vκ sj <v κ ts]>1 for all j∈J, (2) where 1[·] denotes a Boolean function that takes the value 1 if the condition in the brackets is met, and the value 0 otherwise. Under BEP(τall, κ, β) dynamics (i.e., for α=n) and given a subset of strategies J⊆S{s}, this result considers a tight bound on the column sums of the submatrix of DW+(0)corresponding to the strategies in J,5and it is, up to our knowledge, the most general available result that guarantees instability under BEP(τall, κ, β) dynamics (for any tie-breaking rule) with either κ>1or p>2. And the result applies to BEP(τα, κ, β) dynamics as well. 4If λis an eigenvalue of DW+(0), then (λ −1)is an eigenvalue of DW(0) =DW+(0) −I. 5See note at the beginning of appendix A.2. 6 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 3.4. Stability results A series of stability results (i.e. sufficient conditions for stability) can also be derived from the analysis of Vκby considering that, if DW+(0)is a triangular matrix, its eigenvalues are its diagonal elements. If the eigenvalues λiof DW+(0)are all less than one, then the eigenvalues of DW(0), which are λ i=λi−1, are all negative and, consequently, esis stable. This can be used to show, for instance, that, under any BEP(τα, κ, β) dynamics, any strict equilibrium state is asymptotically stable if the number of trials is larger than a certain threshold (Sandholm et al., 2020, Corollary 5.8). Under BEP(τall, κ) dynamics, the most general condition that guarantees that the Jacobian of DW+(0)can be arranged as a triangular matrix whose diagonal elements are 0is the existence of an ordering of the strategies in Ssuch that, for all i, j= swith i≥jwe have: vκ ss >v κ ij and, if i∈S2, vκ sj >v κ is. This is a refinement of Proposition 5.9 in Sandholm et al. (2020) that can be shown to be equivalent to the sufficient condition for asymptotic stability in Theorem 2 (II) in Arigapudi et al. (2021). Arigapudi et al. (2021) focus on the BEP(τall, κ) dynamic and on a family of games that satisfy a specific genericity requirement, which here we term κ-generic games (Arigapudi et al., 2021, Definition 4). They show that their sufficient condition for asymptotic stability of strict Nash equilibria is both sufficient and necessary in κ-generic games with either more than two players (p>2) or more than one test of each strategy (κ>1). However, their stability condition is difficult to check if followed literally, since it involves testing a requirement on each and every set in the power set of S{s}. The requirement of having a κ-generic game can also be too stringent in practical cases, as it may not be satisfied even by two-player games with generic payoff matrices. As an illustration, none of the more than 20 numeric examples in Osborne and Rubinstein (1998), Sethi (2000), Sandholm et al. (2019, 2020), Sethi (2021) and Arigapudi et al. (2021)are κ-generic. 3.5. Contribution In this paper we: i) Show that the general sufficient condition for instability of strict equilibria indicated above (Sandholm et al., 2020, Proposition 5.4 (ii)), which applies under any BEP(τα, κ) dynamics, can be checked using a simple algorithm. The complexity of this algorithm is equivalent to performing an iterated elimination of dominated strategies. ii) Show that a similarly simple algorithm can be used to check the general sufficient condition for asymptotic stability of strict equilibria under BEP(τall, κ) dynamics indicated in Section 3.4,6i.e., the most general condition that guarantees, under any tie-breaking rule, a triangular Jacobian DW(0)with all diagonal values (eigenvalues) equal to −1. We also provide a tighter stability test under the specific tie-breaking rule βstick, a rule that favors stability under BEP(τall, κ) dynamics. iii) Discuss conditions under which the sufficient condition for asymptotic stability in ii) is also necessary for stability, for different BEP(τall, κ) dynamics. This extends the results of Arigapudi et al. (2021)by removing the constraint that the game be κ-generic. 6As indicated before, this is equivalent to the sufficient condition for asymptotic stability in Arigapudi et al. (2021), Theorem 2, II. 7 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 iv) Apply our results to explore the predictive power of BEP dynamics in tacit coordination games. In these games, most game theoretical models do not correspond well with experimental evidence. 4. Stability and instability tests 4.1. s-Stabilizing and potentially s-stabilizing strategies In this section, we define s-stabilizing and potentially s-stabilizing strategies in subsets J⊆S{s}. Informally, a s-stabilizing strategy in Jis a strategy that, under a BEP(τall, κ) dynamic, does not contribute to the growth of the fraction of players using the strategies in J, when the population state is close to the strict equilibrium state es. In contrast, if a strategy is not potentially s-stabilizing in J, it is associated to at least some minimum contribution to the growth of the fraction of players using the strategies in J, when the population state is close to the strict equilibrium state es, under any BEP(τα, κ) dynamic. Definition (s-stabilizing and potentially s-stabilizing strategies). Let sbe a strategy such that the strategy profile (s, s, ..., s) is a strict Nash equilibrium of the game. Let S2be the set of strategies that obtain the second-best payoff, vκ ts, when playing against s-players, i.e., S2≡ argmaxi=svκ is =argmaxi=sU(i; s, s, ..., s), and vκ ts ≡maxi=svκ is. Let Jbe a non-empty set J⊆S{s}. A strategy j∈Jis s-stabilizing in J, for a number of trials κ, if •vκ ij <v κ ss for all i∈J, and •If S2∩J= ∅, then vκ sj >v κ ts. A strategy j∈Jis potentially s-stabilizing in J, for a number of trials κ, if •vκ ij ≤vκ ss for all i∈J, and •If S2⊆J, then vκ sj ≥vκ ts. Clearly, every s-stabilizing strategy in Jis potentially s-stabilizing in J. To understand the previous conditions, consider a test of each strategy by a revising agent who, when sampling the required n κ(p−1)co-players, meets just once a deviating co-player not using strategy s, but using strategy j∈Jinstead. The condition vκ ij <v κ ss guarantees that, if the deviating jplayer is met when testing strategy i∈J, the total payoff vκ ij to strategy iis less than the total payoff vκ ss to strategy s, so strategy sis selected. Similarly, the condition ((S2∩J= ∅) ⇒vκ sj > vκ ts) guarantees that, if the deviating j-player is met when testing strategy s(in which case the maximum of the payoffs obtained by all the strategies is either vκ sj or vκ ts), no strategy i∈Jis selected. Intuitively, in a neighborhood of es, if jis s-stabilizing in Jthen we could say that j does not help any other strategy in J(including itself) to destabilize es. With relation to the analysis of the Jacobian of the BEP(τall, κ) dynamics at es, if a strategy jis s-stabilizing in a subset of strategies J, then jhas a null contribution (on the column corresponding to j) to the principal submatrix of DW+(0)associated to J. And if, starting from J1=S{s}, a process of iterative elimination of s-stabilizing strategies (see appendix A.1) eliminates all strategies in S{s}, then DW+(0)can be arranged (by reordering the strategies) as a triangular matrix with a zero diagonal (so the eigenvalues of DW+(0)are 0, and the eigenvalues of DW(0)are −1), proving asymptotic stability of es. 8 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 Note that if, for a number of trials κ0and some subset of strategies J, a strategy j∈Jis s-stabilizing in J, then jis s-stabilizing in Jfor any κ>κ 0. In contrast, if a strategy jis not potentially s-stabilizing in some subset of strategies J(such that j∈J), then the (positive or destabilizing) contribution of jto the principal submatrix of the Jacobian of the dynamics corresponding to the strategies in J, in the column corresponding to j, is guaranteed to be above a certain threshold value, under any BEP(τα, κ) dynamic. If there is some subset of strategies Jsuch that every strategy j∈Jis not potentially s-stabilizing in J, the fact that the sum of the terms in every column of the principal submatrix of DW(0)associated to Jis above a threshold value can be used to obtain a lower bound for the Perron–Frobenius eigenvalue of DW(0), and to guarantee instability of the equilibrium. Note that if, for a number of trials κ0and some subset of strategies J, a strategy j∈Jis not potentially s-stabilizing in J, then jis not potentially s-stabilizing in Jfor any κ<κ 0. 4.2. Instability under BEP(τα, κ) dynamics Our first proposition shows that a tight sufficient test for instability of strict equilibria under any BEP(τα, κ) dynamics can be carried out by analyzing the iterated elimination of potentially s-stabilizing strategies in S{s}. Although the process of iterated elimination may be considered evident, a formal description can be found in appendix A.1. All the proofs have been relegated to appendix A.2. Note that if a strategy j∈J⊆S{s}is potentially s-stabilizing in J, then jis also potentially s-stabilizing in any subset of Jcontaining j. As a consequence, the order in which potentially s-stabilizing strategies are iteratively eliminated does not alter the final set of surviving strategies. Proposition 4.1. Let esbe a strict equilibrium. If for a number of trials κ0>n−1 (p−1)(α−1)some strategy survives the iterated elimination of potentially s-stabilizing strategies in S{s}, then state esis unstable under any BEP(τα, κ) for any κsatisfying n−1 (p−1)(α−1)<κ≤κ0. Corollary 4.2. Let esbe a strict equilibrium. If for a number of trials κ0some strategy survives the iterated elimination of potentially s-stabilizing strategies in S{s}, then state esis unstable under any BEP(τall, κ) for any κwith 1 <κ≤κ0, and, if p>2, for any κ≤κ0. Example 4.1. Consider the game with payoff matrix Uij =Vκ=1=⎛ ⎝ 300 200 200 ⎞ ⎠,which leads to Vκ=2=⎛ ⎝ 633 422 422 ⎞ ⎠. Corollary 4.2 shows that the equilibrium state e1is unstable under BEP(τall, κ=2) dynamics. This can be proved by noting that, for κ=2, strategies 2 and 3 survive the iterated elimination of potentially 1-stabilizing strategies, since none of them is potentially 1-stabilizing in J=S {s} ={2, 3}. This is so because, for s=1 and j∈J, we have that S2={2, 3} ⊆Jbut vκ=2 1j= 3 <4 =vκ=2 t1. However, for κ=2, this game satisfies the necessary conditions for asymptotic stability in Theorem 2 in Arigapudi et al. (2021), which are not sufficient in this case, since the game is not κ-generic. Thus, Corollary 4.2 (and Proposition 4.1, more generally) can be used to prove the instability of strict equilibria on which Theorem 2 in Arigapudi et al. (2021) remains silent. 9 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 Table 1 Payoff matrices for a p-player tacit coordination game with three strategies (n =3). Left: general case. Middle: a=2and b=1. Right: a=1and b=0. min of others’ strategies 12 3 1a−b a −b a −b 2a−2b2a−2b2a−2b 3a−3b2a−3b3a−3b min of others’ st. 123 1 1 1 1 2 0 2 2 3−1 1 3 min of others’ st. 123 1 1 1 1 2 1 2 2 3 1 2 3 Table 1represents the payoff function for the 3-strategy case (n =3). The row headings on the payoff matrices in Table 1indicate the strategy chosen by the player that receives the payoff. The column headings indicate the minimum value of the strategies chosen by the other (p −1) players. For b>0, the unique best reply to any (partial) pure strategy profile (j1, ..., jp−1)used by the other players is the minimum of their contributions, i.e. min(j1, ..., jp−1). The monomorphic states ei, with i∈{1, ..., n}, are consequently the only pure-strategy Nash equilibrium states of the game, and they are all strict. Strategy 1(the maxmin strategy) is called the secure strategy, while strategy nis called the efficient strategy because, if adopted by everyone, it corresponds to the efficient equilibrium profile (n, ..., n). For b=0, the efficient strategy nis weakly dominant (see Table 1, right matrix) and enis the only strict Nash state. All symmetric strict Nash equilibria satisfy most equilibrium refinements and correspond to evolutionarily stable states, according to the standard definition of evolutionary stability (Weibull, 1995).10 However, experimental evidence clearly shows that human subjects do discriminate between different strict equilibria in these games. Van Huyck et al. (1990) present and discuss neat experimental evidence on these games with n =7 strategies, repeatedly played within (fixed) groups of different sizes. Their most striking findings are summarized below:11 •Games with b>0. The behavior of human subjects in these games clearly depends on the number of players. When the game is played in very small groups (i.e., p=2 players), there is a clear tendency to choose the efficient strategy.12 In contrast, in groups with several players (p≈15), the distribution of strategies is initially diverse, and then the vast majority of players approach the lowest effort (i.e. the secure strategy 1) fairly quickly –in ten periods or less–, even when the experiment is repeated with the same group of co-players: “most people appear to consider the highest effort a good bet in small groups, but not in large groups” (Crawford, 1991). Note that this clear pattern of discrimination between strict Nash equilibria, dependent on the number of players and against the payoff-dominance criterion in the case of large groups, cannot be explained along the lines of traditional game theory (Crawford, 1991). •Games with b=0. In between two rounds of repeatedly playing the stage game with b>0 within a large group (at both of which nearly all subjects ended up choosing the lowest effort; even faster and more sharply in the second round), Van Huyck et al. (1990) put the 10 Crawford (1991) provides a detailed analysis of these games and shows that the only equilibrium state that satisfies a finite-population definition of evolutionary stability is the secure state e1. 11 We refer to each play of the stage game as one period, and we use the term round for several consecutive periods. 12 Van Huyck et al. (1990)also present results on setups where players were randomly paired after every period. In that case, they did not find any stable pattern of behavior. 16 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 Fig. 5. Tacit coordination game with n =3 strategies and a=2b>0(see Table 1) under BEP(τall, κ=1, βstick) dynamics, for number of players p=2 (left), p=3 (middle) and p=15 (right). same groups to play one round of the game with b=0for five periods. In stark contrast with the results for b>0, in this intermediate round with b=0, nearly all players chose the highest effort in virtually all periods. This suggests that the consistent results obtained with b>0 (both before and after playing the repeated game with b=0) were not due to players’ misunderstanding of the incentives structure, but to strategic uncertainty, i.e. players’ uncertainty about how the other players may respond to the multiplicity of strict Nash equilibria (Crawford, 1991). 5.2. Results Without aiming to provide an explanation for the regularities found by Van Huyck et al. (1990)– we refer the reader to Crawford’s (1991) insightful analysis for a discussion of possible explanations –, our goal in this section is to explore whether BEP dynamics can capture the discrimination between different strict Nash equilibria shown by humans in tacit coordination games, and its dependence on the number of players p. We include the most relevant results of this analysis below (proofs are included in the appendix). The stability analysis of strict equilibria states under BEP dynamics is more interesting for low values of the number of trials κ, since for sufficiently large values of κ, every strict equilibrium is asymptotically stable. a) Games with b>0. The stability of the different strict Nash states is highly dependent on the number of players p. For two players, the efficient state en(maximum contribution) is Lyapunov stable under any BEP(τall, 1), while (assuming that the number of strategies is greater than 1 +a a−b) the secure state e1(minimum contribution) is unstable (see Fig. 5(i) for the three-strategy case). By contrast, for more than two players, the efficient state en is unstable (under any BEP(τall, 1) dynamic13), while the secure state e1is asymptotically stable (under every BEP(τall, κ) dynamics). Fig. 5illustrates these results for a game with n =3 strategies under BEP(τall, 1, βstick) dynamics. The fact that increasing the number of players favors the instability of enand the stability of e1is in full accordance with experimental evidence. 13 Proposition 4.1 also shows that the efficient state enis unstable for every BEP(τα, 1) dynamics if p>n. 17 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 Fig. 6. Tacit coordination game with n =3 strategies, p=3players, a=3, and b=2(see Table 1) under BEP(τall, κ, βstick) dynamics, for number of trials κ=1 (left), κ=3 (middle) and κ=5 (right). Let us now analyze the stability of the intermediate strict Nash states e2, ..., en−1for p>2. We find three cases: i) a<2b. In this case, every intermediate state e2, ..., en−1is unstable under BEP(τall, κ< a a−b) dynamics, and also under BEP(τα, κ< a a−b) dynamics if p>n, leaving e1as the only asymptotically stable strict Nash state (this includes the cases κ=1 and κ=2, given that a a−b>2). In turn, every intermediate state e2, ..., en−1is asymptotically stable under every BEP(τall, κ> a a−b) dynamics. The stability of the intermediate states in the borderline case κ=a a−bdepends on the tie-breaking rule (instability under βunif, stability under βstick). Fig. 6illustrates these results for a game with n =3 strategies under BEP(τall, κ, βstick) dynamics. Note that, in the cases where the intermediate state is stable (i.e. κ>2), its basin of attraction is rather small compared with the basin of attraction of the secure state e1. ii) a=2b. In this case, every intermediate state e2, ..., en−1is unstable under BEP(τall, κ= 1, βstick) dynamics for p>3, leaving e1as the only asymptotically stable strict Nash state. This is also the case under BEP(τall, κ=1, βunif) dynamics with p>4, and under BEP(τα, κ=1, βunif) dynamics with p≥2n. For κ>2, every intermediate state is asymptotically stable under every BEP(τall, κ>2) dynamics. The case κ=2 depends on the tie-breaking rule (stability under βstick, instability under βunif). iii) a>2b. In this case, for p>2, every intermediate state e2, ..., en−1is asymptotically stable under BEP(τall, κ) dynamics. Note, however, that the basin of attraction of these intermediate states is again rather small compared with the basin of attraction of the secure state e1, especially if pis large (see Fig. 7). b) Games with b=0. In this case, strategy nis weakly dominant and the efficient state enis the only strict Nash equilibrium state. For p=2 players, this efficient state is almost globally asymptotically stable under both BEP(τall, 1, βunif) and BEP(τall, 1, βstick). Besides, for any number of players, enis asymptotically stable under BEP(τall, κ>1) dynamics, and also under the BEP(τall, 1, βstick) dynamic.14 Fig. 8illustrates these results for a game with n =3 strategies under the BEP(τall, 1, βstick) dynamic. 14 However, Proposition 4.4 shows that enis unstable under the BEP(τall, 1, βunif) dynamic for p>3, and under BEP(τα, 1, βunif) dynamics for p≥2n.. 18 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 Fig. 7. Tacit coordination game with n =3 strategies and a>2b>0(see Table 1) under BEP(τall, κ=1) dynamics (for any tie-breaker), for number of players p=5 (left), p=10 (middle) and p=15 (right). Fig. 8. Tacit coordination game with n =3 strategies and b=0(see Table 1) under BEP(τall, κ=1, βstick) dynamics, for number of players p=2 (left), p=3 (middle) and p=15 (right). Thus, in general terms (but also with a few exceptions –e.g. see footnote 14), BEP(τall, κ) dynamics with a low number of trials κseem to exhibit regularities similar to those observed in the experimental evidence for tacit coordination games, i.e.: (i) for b>0, clear discrimination between strict Nash states, selecting the secure state e1in large groups but not in games with two players, and (ii) for b=0, a clear tendency to select the weakly dominant strategy. 5.3. Discussion Strict Nash states are stable under most deterministic evolutionary dynamics (Sandholm, 2014), such as all monotone imitative dynamics (e.g. the replicator dynamics (Taylor and Jonker, 1978)), all sign-preserving excess payoff dynamics (e.g. the BNN dynamic (Brown and von Neumann, 1950)), and all pairwise comparison dynamics (e.g. the Smith (1984) dynamic). The intuition is that, in a small neighborhood of a strict Nash state es, the strict Nash strategy sis the unique best reply to every population state in terms of expected payoffs. However, consider a population state in which most players use the strict Nash strategy sand a small fraction of players use strategy j= s. Under random matching, the probability that an s-player happens to be in a p-player group in which there is at least one j-co-player is approximately times the number (p−1) of co-players (considering a first-order approximation). This means that, given a fixed fraction of j-players in a population, the larger the number of players pin a game, the larger the probability of finding at least one co-player using strategy j. If 19 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 agents revise their strategies based on the performance that those strategies provide when tested in specific groups of p(randomly drawn) players –instead of looking at the expected payoff of each strategy in the population–, then the number of players pcan have a large influence on the population dynamics. Experimental results in tacit coordination games constitute a clear example of the practical relevance of the number of players in the stability of different strict Nash equilibria, and BEP dynamics in tacit coordination games also illustrate this effect. Focusing on tacit coordination games with a<2band BEP(τall, κ=1) dynamics, suppose that most players (a fraction 1 −) use strategy s>1 and a small fraction of players use strategy j<s. Most of the revising s-players who, when testing strategy s, happen to meet a j-co-player in their group, will then adopt some strategy lower than s(under test-all, they will likely adopt strategy s−1, because, when testing strategies against a group of s-players, s−1is the second-best reply, after s). As discussed before, the number of such revising agents is roughly proportional to the number of co-players (p−1).15 To be specific, they will be approximately (1 −) (p−1). In turn, most of the j-players will adopt strategy swhen revising. Thus, if (1 −) (p−1) >, i.e. if p>2− 1−, state esis unstable. This is the intuition why, for a sufficiently large number of coplayers (p>2 under τall; p>nunder τα), the efficient and the intermediate strict Nash states become unstable.16 Note that BEP dynamics capture the effect that the number of players pcan have in the stability of a strict Nash state in tacit coordination games, via the probability of meeting a deviating j-co-player in a group of pplayers, which is an increasing function of p. This increasing probability of meeting a deviating j-co-player is also likely to be an important factor to explain the effect of the number of players in the experimental results, as pointed out by Van Huyck et al. (1990, p. 236). In any case, it is important to emphasize that many experimental designs in the literature do not readily fit in the evolutionary framework we have assumed here, and one would expect additional factors to be at play in those experimental studies (see Crawford (1991)). 6. Conclusions Strict Nash equilibria correspond to rest points under Best Experienced Payoff dynamics, but these rest points may be unstable. In this paper we provide a simple test, with a simple interpretation, that guarantees asymptotic stability under BEP(τall, κ) dynamics. We also provide a related simple test that guarantees instability of strict equilibria under the more general family of BEP(τα, κ) dynamics. Focusing on BEP(τall, κ, βunif) dynamics, which is the family of BEP dynamics prevalent in the literature, and for values of the number of trials κabove a small threshold value κ1≤n, our stability test proves either asymptotic stability or, otherwise, instability. We also show that, for κ>nand as κincreases, any strict equilibrium is either always asymptotically stable or there is a single transition from instability to asymptotic stability, within a bounded range of values of κ.17 Similar results are obtained for the BEP(τall, κ, βstick) dynamic, for which we present an even tighter asymptotic stability test. 15 In contrast, note that under best-response dynamics (in terms of expected payoff), no s-player would change strategy for sufficiently low . 16 Similar arguments can be applied for the other sampling dynamics, i.e. sampling best response dynamics or actionsampling dynamics, under which strict Nash states can also be unstable (Sandholm, 2001). 17 Sandholm et al. (2020) provide bounds on the values of κthat can correspond to instability. 20 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 Finally, in order to illustrate our results and to explore the predictive power of BEP dynamics, we have conducted a detailed analysis of the stability of strict equilibria in tacit coordination games. In these games, experimental evidence is at odds with the predictions of most game theoretical analyses. Data availability The software we developed and used to create the figures (EvoDyn-3s (Izquierdo et al., 2018) for Figs. 1-4 and BEP-TCG (Izquierdo and Izquierdo, 2022) for Figs. 5-8) is open source and freely available. Appendix A A.1. Iterated elimination of strategies Definition (Survivors of iterated elimination of strategies satisfying condition Cin a finite set ). Let J0≡and define Jmrecursively by Jm={i∈Jm−1|idoes not satisfy condition Cin Jm−1}. The (potentially empty) set J||is the set of strategies that survive iterated elimination of strategies satisfying condition Cin set . An algorithm for this procedure is described in Algorithm 1. Algorithm 1 Iterated elimination of strategies satisfying condition Cin set . J← while ∃j∈J| jsatisfies condition Cin Jdo J←J{j∈J| jsatisfies condition Cin J} end while Jat the end is the set of all surviving strategies after iterated elimination A.2. Proofs Note. Bound on the Perron-Frobenius eigenvalue of DW+(0)under BEP dynamics, based on the columns of the principal submatrices of DW+(0). Under BEP(τall, κ) dynamics, the inflow (positive) terms in column jof DW+(0)are associated to the terms 1[vκ ij >v κ ss], 1[vκ ts >v κ sj ], 1[vκ ij =vκ ss]or 1[vκ ts =vκ sj ], when the corresponding cases in the brackets hold, i.e., when the indicator function takes the value 1. The inflow associated to the last two terms, 1[vκ ij =vκ ss]and 1[vκ ts =vκ sj ], is 0 under tie-breaking rules that always select the agent’s current strategy if it is among the optimal tested strategies (such as βstick). In this case, the less favorable for the instability of s, the inflow (positive) terms in column jof DW+(0)are (p −1) κ1[vκ ij >v κ ss], at position DW+ ij (0), plus a total inflow of (p −1) κ1[vκ ts >v κ sj ]distributed (according to the tie-breaking rule) among the rows of DW+(0) corresponding to the strategies in S2. Consequently, given a subset J⊆S{s}and considering its associated principal submatrix DW+ J(0), corresponding to the strategies in J, the largest value that we can guarantee (for every tie-breaking rule) for the sum of the terms in the column of DW+ J(0)corresponding to strategy jis (p −1) κi∈J1[vκ ij >v κ ss], plus, if S2⊆J, (p −1) κ1[vκ ts >v κ sj ]. Considering τα, for κ> n−1 (p−1)(α−1)(with τall, either p>2or k>2are 21 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 enough to satisfy this condition) it can be shown, following arguments similar to the proof of fact 2 in Arigapudi et al. (2021), that proposition 5.4 (ii) in Sandholm et al. (2020), which is based on the bound discussed here (by columns), is more general than proposition 5.4 (i), which is based on a bound by rows that considers only the terms 1[vκ ij >v κ ss]. Proof of Proposition 4.1.Considering κ=κ0, if the iterated elimination of potentially s-stabilizing strategies does not eliminate all strategies in S{s}, then there is some non-empty set J⊆S{s}which does not contain any potentially s-stabilizing strategies. This implies that for every j∈J, either ∃i∈Jsuch that vκ ij >v κ ss or (S2⊆Jand vκ sj <v κ ts). With these conditions, proposition 5.4 of Sandholm et al. (2020) guarantees instability of the strict equilibrium if κ> n−1 (p−1)(α−1). The extension to κ<κ 0comes from the fact that if a strategy is not potentially sstabilizing in Jfor a number of trials κ0, then it is not potentially s-stabilizing in Jfor any κ<κ 0. Proof of Proposition 4.3.Following Sandholm et al. (2020), consider a change of variables for the population state (x1, x2, ..., xn)that sends the equilibrium esto the origin 0, by eliminating the coordinate xswhile keeping the labeling of the other coordinates. In this system, consider the Jacobian of the dynamics at the equilibrium, DW(0). Let DWJ(0)be the square submatrix of DW(0)whose rows and columns correspond to the strategies in J. If jis s-stabilizing in J for κ=κ0, then the column of DWJ(0)corresponding to strategy jis made up (see Sandholm et al. (2020)) by zeros in all non-diagonal positions, with a value −1at the diagonal position. Let (j1, j2, ..., jn−1)be an ordering of the (n −1)strategies in S{s}that iteratively eliminates s-stabilizing strategies. Then the column of DW(0)corresponding to strategy j1is made up by zeros in all non-diagonal positions, with a value −1at the diagonal position. Considering the cofactor expansion of the determinant of the Jacobian along the column corresponding to j1, and denoting by DW−{j1}(0)the submatrix of DW(0)obtained by eliminating the column and row corresponding to j1, we have that |DW(0)| =(−1) |DW−{j1}(0)|. Now, the column of DW−{j1}(0)corresponding to strategy j2is made up by zeros in all non-diagonal positions, with a value −1at the diagonal position. Proceeding sequentially with the other strategies we obtain |DW(0)| =(−1) |DW−{j1}(0)| =(−1)2|DW−{j1,j2}(0)| =... =(−1)n−1, i.e., all the eigenvalues of the Jacobian have negative real parts, which implies asymptotic stability of the equilibrium. The result for κ≥κ0follows from the fact that if a strategy is s-stabilizing in Jfor a number of trials κ0, then it is s-stabilizing in Jfor any κ>κ 0. Proof of Proposition 4.4.The stability part comes from Proposition 4.3. For the instability part, first consider κ=κ0. If the iterated elimination of s-stabilizing strategies does not eliminate all strategies in S{s}, then there is some non-empty set J⊆S{s}which does not contain any s-stabilizing strategies. This means that for every j∈J, either ∃i∈Jsuch that vκ ij ≥vκ ss or (S2∩J= ∅and vκ sj ≤vκ ts). Considering this and Lemma A.1 below, which is a direct adaptation of proposition 5.4 in Sandholm et al. (2020)for the BEP(τα, κ, βunif) dynamics, we have that the minimum possible value of the left hand side on Equation (4)is (p −1)κ 1 |S2|+1, so the condition κ>|S2|+1 p−1guarantees instability under BEP(τall, κ, βunif) dynamics. If v1 ss−minj∈S{s}v1 sj v1 ss−v1 ts <κ, then vκ sj >v κ ts for all j= sand the minimum possible value indicated before is (p −1)κ 1 2, so the condition κ> 2 p−1guarantees instability. The adaptation of these results to BEP(τα, κ, βunif) dynamics is immediate considering Equation (5). The extension to κ<κ 0comes from the fact 22 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 that if a strategy is not s-stabilizing in Jfor a number of trials κ0, then it is not s-stabilizing in J for any κ<κ 0. Lemma A.1. Let esbe a strict equilibrium, let S2=argmaxi=sU(i; s, s, ..., s), and let t∈S2. Under any BEP(τall, κ, βunif) dynamic, state esis linearly unstable if, for some nonempty J⊆ S{s}, the following condition holds for all j∈J: (p −1)κ  i∈J 1[vκ ij >v κ ss]+1 2 i∈J 1[vκ ij =vκ ss](4) +(p −1)κ |S2∩J|1 |S2|1[vκ sj <v κ ts]+ 1 |S2|+11[vκ sj =vκ ts]>1 And under any BEP(τα, κ, βunif) dynamic, letting b=min(|S2|, α−1), state esis linearly unstable if, for some nonempty J⊆S{s}, the following condition holds for all j∈J: (p −1)κ α−1 n−1 i∈J 1[vκ ij >v κ ss]+1 2 i∈J 1[vκ ij =vκ ss](5) +(p −1)κ α−1 n−1|S2∩J|1 b1[vκ sj <v κ ts]+ 1 b+11[vκ sj =vκ ts]>1 Proof of Proposition 4.5.The stability part comes from adapting the proof of Proposition 4.3 to the BEP(τall, κ, βstick) dynamic, considering that the Jacobian DW(0)for the BEP(τall, κ, βstick) dynamic has components (Sandholm et al., 2020): DWij (0)=(p −1)κ 1[vκ ij >v κ ss]−1[j=i]if i/∈S2, (p −1)κ 1[vκ ij >v κ ss]+ 1 |S2|1[vκ is >v κ sj ]−1[j=i]if i∈S2. For the instability part follow the steps in the proof of Proposition 4.4, noting that if a nonempty set J⊆S{s}does not contain any weakly s-stabilizing strategies, then, for every j∈J, either ∃i∈Jsuch that vκ ij >v κ ss or (S2∩J= ∅and vκ sj <v κ ts). Note also that the equivalent of Equation (2)for the BEP(τ all, κ, βstick)dynamic is (p −1)κ  i∈J 1[vκ ij >v κ ss]+|S2∩J|1 |S2|1[vκ sj <v κ ts]>1 Proofs of statements in Section 5.2 (Results on Tacit Coordination Games). For the analysis of the stability of the strict Nash states of a p-player tacit coordination game under BEP dynamics, we calculate the values vκ,s ij , which in this case are: vκ,s ij =(κ −1)U(i;s, s, ..., s) +U(i;j, s, ..., s) =(κ −1)a min(i, s) −κbi+amin(i, j) if p=2 min(i,j,s) if p>2. The n ×nmatrices Vκ=1,s for p=2 and for p>2are shown in Tables 2and 3respectively. Note that Vκ=1,s for p=2 (Table 2) is the payoff matrix Uij . Matrices Vκ,s for κ>1 can be easily calculated from the corresponding matrix Vκ=1,s by adding, to every column in Vκ=1,s , column sof Vκ=1,s times (κ −1). 23 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 Table 2 Matrix Vκ=1,s for tacit coordination games with p=2 players. This is also the payoff matrix of the game if p=2. 12 3... n 1a−b a −b a −b... a−b 2a−2b2a−2b2a−2b... 2a−2b 3a−3b2a−3b3a−3b... 3a−3b . . . . . . . . . . . ..... . . n a −nb 2a−nb 3a−nb ... na −nb Table 3 Matrix Vκ=1,s for tacit coordination games with more than two players (i.e. p>2). 12... s−1ss+1... n 1a−b a −b... a−b a −b a −b... a−b 2a−2b2a−2b... 2a−2b2a−2b2a−2b... 2a−2b . . . . . . . . ..... . . . . . . . ..... . . s−1a−(s −1)b 2a−(s −1)b ... (s −1)(a −b) (s −1)(a −b) (s −1)(a −b) ... (s −1)(a −b) s a −sb 2a−sb ... (s −1)a −sb s(a −b) s(a −b) ... s(a −b) s+1a−(s +1)b 2a−(s +1)b ... (s −1)a −(s +1)b sa −(s +1)b sa −(s +1)b ... sa −(s +1)b . . . . . . . . ..... . . . . . . . ..... . . n a −nb 2a−nb ... (s −1)a −nb sa −nb sa −nb ... sa −nb a) Games with b>0. Results about the stability of the efficient state enand of the secure state e1. –For p=2, the efficient state enis Lyapunov stable under any BEP(τall, 1). Proof. Direct application of Proposition 5.11(i) in Sandholm et al. (2020), noting that Unn >U ij for all i, j= n(see Table 2).  –For p=2 and n >1 +a a−b, the secure state e1is unstable under any BEP(τall, 1). Proof. Direct application of Proposition 5.4(i) in Sandholm et al. (2020), considering the subset of strategies J={n, n −1}and noting that, if n >1 +a a−b, then U11 <U ij for i, j∈J(see Table 2).  –Proposition 4.1 shows that the efficient state enis unstable under any BEP(τall, 1) dynamic if p>2, and under every BEP(τα, 1) dynamics if p>n. Proof. Table 3shows matrix Vκ=1,s for p>2. For s=nwe have S2={n −1}and v1,s s(n−1)=(n −1) a−n b<(n −1)(a −b) =v1,s ts . Consequently, strategy (n −1) is not potentially n-stabilizing in any set that contains it, and Proposition 4.1 shows that enis unstable under the BEP(τall, 1) dynamic for p>2, and under every BEP(τα, 1) dynamics for p>n. –Proposition 4.3 shows that the secure state e1is asymptotically stable under every BEP(τall, κ) dynamics if p>2. 24 S.S. Izquierdo and L.R. Izquierdo Journal of Economic Theory 206 (2022) 105553 Proof. Table 3shows matrix Vκ=1,s for p>2. For s=1 and κ=1, the condition vκ=1 ij < vκ=1 ss =s(a−b), which implies satisfaction of part of the conditions for s-stabilizing strategies, holds for all i, j= s. Looking at matrix Vκ=1,s=1, we have S2={2}and v1,s sj = a−b>a−2b=v1,s ts . Consequently, all strategies are 1-stabilizing in S{1}for κ=1, and we can apply Proposition 4.3 to state that the secure state e1is asymptotically stable under every BEP(τall, κ).  Results about the stability of the intermediate strict Nash states e2, ..., en−1. i) a<2b. Proposition 4.1 shows that every intermediate state e2, ..., en−1is unstable under BEP(τall, κ< a a−b) dynamics for p>2, and under every BEP(τα, κ< a a−b) dynamics for p>n. Conversely, if κ> a a−b, then Proposition 4.3 shows that every intermediate state is asymptotically stable under every BEP(τall, κ> a a−b) dynamics for p>2. The case κ=a a−bdepends on the tie-breaking rule. For p>2, Proposition 4.4 shows that every intermediate state is unstable under BEP(τall, κ=a a−b, βunif), and Proposition 4.5 shows that every intermediate state is stable under BEP(τall, κ=a a−b, βstick). Proof. Table 3shows matrix Vκ=1,s for p>2. For s∈{2, ..., n −1}, the condition vκ ij < vκ ss =κs(a−b), which implies satisfaction of part of the conditions for s-stabilizing strategies, holds for all i, j= s. Given that a<2b, we have S2={s−1}. We can now compute vκ,s s(s−1)=κs(a −b) −a, and vκ,s ts =vκ,s (s−1)s =κ(s −1)(a −b). Therefore, the condition vκ,s s(s−1)≥vκ,s ts holds if and only if κ≥a a−b. Thus, if κ< a a−b, then vκ,s s(s−1)<v κ,s ts , so strategy (s−1) is not potentially s-stabilizing in any set that contains it, and Proposition 4.1 shows that every intermediate state es∈ {e2, ..., en−1}is unstable under BEP(τall, κ< a a−b) dynamics for p>2, and under every BEP(τα, κ< a a−b) dynamics for p>n. Conversely, if κ> a a−b, then vκ,s s(s−1)>v κ,s ts , so strategy (s −1)is s-stabilizing in S {s}. After eliminating strategy (s −1), all the other strategies are s-stabilizing in J= S{s, s−1}, since vκ ij <v κ ss =κs(a−b) for all i, j= sand S2∩J=∅. Thus, no strategy survives the iterated elimination of s-stabilizing strategies, and we can apply Proposition 4.3 to state that every intermediate state es∈{e2, ..., en−1}is asymptotically stable under every BEP(τall, κ> a a−b). The case κ=a a−b>2 depends on the tie-breaking rule.18 For p>2, Proposition 4.4 can be applied to prove that every intermediate state is unstable under BEP(τall, κ= a a−b, βunif),19 and Proposition 4.5 can be applied to prove that every intermediate state is asymptotically stable under BEP(τall, κ=a a−b, βstick).20  ii) a=2b. Proposition 4.5 shows that every intermediate state e2, ..., en−1is unstable under BEP(τall, κ=1, βstick) dynamics for p>3. Proposition 4.4 shows that they are also 18 Given that a<2b, we have a a−b>2. 19 In this case, strategy (s−1) is not s-stabilizing in any set that contains it and |S2|+1 p−1=2 p−1<2if p>2. 20 In this case, strategy (s −1)is weakly s-stabilizing in S{s}. After eliminating strategy (s −1), all the other strategies are weakly s-stabilizing in J=S{s, s−1}, since vκ ij <v κ ss =κs(a−b) for all i, j= sand S2∩J=∅. Thus, no strategy survives the iterated elimination of weakly s-stabilizing strategies. 25