Equilibrium computation in discrete network games

Leung, Michael P. Article Equilibrium computation in discrete network games Quantitative Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Leung, Michael P. (2020) : Equilibrium computation in discrete network games, Quantitative Economics, ISSN 1759-7331, The Econometric Society, New Haven, CT, Vol. 11, Iss. 4, pp. 1325-1347, https://doi.org/10.3982/QE1386 This Version is available at: https://hdl.handle.net/10419/253593 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/ Quantitative Economics 11 (2020), 1325–1347 1759-7331/20201325 Equilibrium computation in discrete network games Michael P. L eung Department of Economics, University of Southern California Counterfactual policy evaluation often requires computation of game-theoretic equilibria. We provide new algorithms for computing pure-strategy Nash equilibria of games on networks with finite action spaces. The algorithms exploit the fact that many agents may be endowed with types such that a particular action is a dominant strategy. These agents can be used to partition the network into smaller subgames whose equilibrium sets may be more feasible to compute. We provide bounds on the complexity of our algorithms for models obeying certain restrictions on the strength of strategic interactions. These restrictions are analogous to the assumption in the widely used linear-in-means model of social interactions that the magnitude of the endogenous peer effect is bounded below one. For these models, our algorithms have complexity Op(nc), where the randomness is with respect to the data-generating process, nis the number of agents, and cdepends on the strength of strategic interactions. We also provide algorithms for computing pairwise stable and directed Nash stable networks in network formation games. Keywords. Multiple equilibria, graphical games, network formation, empirical games. JEL classification. C31, C57, C63, C73. 1. Introduction Graphical and network formation games have attracted increasing attention in empirical work. Practical use of these models often requires computing the set of equilibria. This is important for evaluating counterfactual policies, for example, assessing the impact of a subsidy on technology adoption in the presence of social interactions (Bhattacharya, Pascaline, and Kanaya (2019))or that of busing programs and other reallocation policies (Mele (2019)). Another use is model estimation, which may require computing equilibria in order to evaluate likelihood or moment functions (Bajari, Hong, and Ryan (2010), Miyauchi (2016), Soetevent and Kooreman (2007), Xu and Lee (2015)). Also, from a theoretical standpoint, the size of the equilibrium set and its ease of computation Michael P. Leung: [email protected] I thank the referees for useful suggestions that improved the paper. This research is supported by NSF grant SES-1755100. It uses data from Add Health, a program project directed by Kathleen Mullan Harris and designed by J. Richard Udry, Peter S. Bearman, and Kathleen Mullan Harris at the University of North Carolina at Chapel Hill, and funded by grant P01-HD31921 from the Eunice Kennedy Shriver National Institute of Child Health and Human Development, with cooperative funding from 23 other federal agencies and foundations. Information on how to obtain the Add Health data files is available on the Add Health website (http://www.cpc.unc.edu/addhealth). No direct support was received from grant P01-HD31921 for this analysis. ©2020 The Author. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at http://qeconomics.org.https://doi.org/10.3982/QE1386 1326 Michael P. Leung Quantitative Economics 11 (2020) are important for assessing the predictive power of a solution concept and its empirical plausibility (Jackson (2010, Chapter 9.3)). Computing the entire set of equilibria is a difficult problem. A naive brute-force search that checks the equilibrium conditions for every agent is computationally infeasible because the number of action profiles is exponential in the number of agents. Polynomial-time algorithms for computing all equilibria in graphical games are only available for tree networks (Daskalakis and Papadimitriou (2006), Kearns (2007)). Beyond trees, the “strong conjecture” is that no polynomial-time algorithm exists (Jackson (2010, Chapter 9.3)). For games of strategic complements, the extremal equilibria can be computed in polynomial time, but finding all equilibria between the extremes generally requires exhaustive search (e.g., Jia (2008)). We provide new algorithms for computing the set of equilibria in graphical and network formation games with finite action spaces. Our algorithms exploit the fact that many agents may have payoff functions such that a particular action is a dominant strategy, that is, always optimal regardless of the actions of other players. For example, in a binary game, an agent endowed with a large enough random-utility shock may find it a dominant strategy to choose action 1. Our algorithm first partitions the network into smaller disjoint subgames on subnetworks whose “boundaries” consist of these agents. The set of equilibria then consists of the “Cartesian product” of equilibrium sets for each of these subgames, which may be feasible to compute using existing methods on account of their smaller sizes. We provide probabilistic bounds on the complexity of our algorithms for a class of games satisfying a restriction on the strength of strategic interactions. For this class, we prove that our algorithms terminate in Op(nc)evaluations of the payoff function. The value of cis increasing in the strength of strategic interactions, which reveals an interesting trade-off between computability and the economic significance of social interactions.1Simulation evidence shows that when strategic interactions are too strong, so that our assumptions are violated, we can expect large, potentially exponential runtimes. This class of games with restricted strategic interactions is empirically relevant. In numerical illustrations, we show that our algorithms feasibly compute the set of equilibria of social interactions models estimated by Card and Giuliano (2013)andXu (2018). Their models obey our restrictions, and the magnitude of the peer effects estimates are economically meaningful. We also note that our restrictions are analogous to the assumption in the widely used linear-in-means model of social interactions that the endogenous peer effect is bounded below one in absolute value (Bramoullé, Djebbari, and Fortin (2009), Calvó-Armengol, Patacchini, and Zenou (2009)). Similar restrictions are imposed on autoregressive models in time series and spatial statistics for weak dependence. Furthermore, to our knowledge, the class of models that we study is the only class of static games of complete information for which large-network CLTs are currently available (Leung and Moon (2019), Leung (2019)). CLTs for large networks are required for inference in the typical setting where the econometrician observes a small set of plausibly independent networks. 1Here, “Op(·)” is with respect to the randomness of the data-generating process. Our algorithms are deterministic. Quantitative Economics 11 (2020) Equilibrium computation in discrete network games 1327 The key step for deriving our complexity result is to obtain exponential tail bounds on a certain statistic Δ, which is essentially the size of the largest subgame obtained after partitioning the network according to our algorithm. In fact, Δcorresponds to the size of the largest component of a certain random graph. We approximate this by a branching process for which the desired tail bounds can be obtained more easily, which is a common technique in random graph theory (Bollobás and Riordan (2008)). The argument is also used in Leung and Moon (2019)andLeung (2019) to derive primitive conditions for CLTs in network formation games and graphical games, respectively. We generalize the tail bounds of the former paper to a larger class of sparse graphs. In particular, we do not need to impose the assumption that agents are homophilous. In economics, homotopy methods have been used to compute game-theoretic equilibria for generic games; see Herings and Peeters (2010) for a survey. These are applicable to games with continuous action spaces (Judd, Renner, and Schmedders (2012)) and games of incomplete information (Bajari, Hong, Krainer, and Nekipelov (2010)). For discrete games, homotopy can be used to compute mixed-strategy equilibria, but the computational cost scales poorly with the size of the game. Our paper is instead concerned with computing pure-strategy equilibria for potentially large, discrete games. The literature on algorithmic game theory that gives rise to the “strong conjecture” mostly focuses on exact or approximate computation of equilibria in graphical games for general payoff functions, and the typical objective is to obtain worst-case bounds on the algorithmic runtime (Daskalakis, Goldberg, and Papadimitriou (2009)). Several papers in this literature explore computability under various restrictions on the network structure. We instead primarily utilize restrictions on the payoff functions, in particular on strategic interactions. We also study stochastic games, where payoffs depend on random and heterogeneous types. This allows us to consider algorithmic complexity from an ex ante perspective with respect to the randomness of the network and types and study the “typical” behavior of our algorithms in large games. Outline The next section presents our algorithm and complexity result for graphical games with binary action spaces. We also provide extensions to multinomial and ordered choice. We then present numerical illustrations in Section 3. In the Online Supplemental Appendix (Leung (2020)), Section SA.4 provides analogous results for undirected network formation games under the solution concept of pairwise stability and Section SA.5 for directed network formation games. Notation We represent a network on nagents as an n×nadjacency matrix, where the ij th entry Aij , referred to as a potential link, is an indicator for whether agent iis connected to j. Following the usual convention, we require that Aii =0for all agents i, meaning that there are no self links. If Ais a symmetric matrix, then it represents an undirected network. Otherwise, it is a directed network. Consider a directed network A. Adirected path from agent ito jis a sequence of distinct agents starting with iand ending with jsuch that for each k,kin this sequence, Akk=1.Thelength of a directed path is the number of links it involves. A weakly connected component is a set of agents such that (1) for each pair of agents i,jin this set, there exists a directed path from either ito 1328 Michael P. Leung Quantitative Economics 11 (2020) jor jto i, and (2) there is no larger set of agents with property (1) containing this set.2 Astrongly connected component is similar, except it requires both a directed path from i to jand jto i. For an undirected network, we refer to a strongly connected component simply as a component. 2. Graphical games Let Nn={1n}be the set of agents, which are connected through an undirected network A.Eachagenti∈Nnis endowed with a type Ti∈Rdt, which is distributed i.i.d. across agents. Let T=(Ti)n i=1bethetypeprofile.Fornow,weassumeeachagentitakes a binary action Yi∈{01}. We later extend the results to more than two actions. Let Y=(Yi)n i=1be an action profile. For any i, we may partition Y=(YiY−i),T=(TiT−i), and A=(AiA−i),whereAiis the ith row of Aand A−ithe remaining submatrix, and Y−i,T−iare similarly defined. For a given action profile Y,agenti’s net payoff from choosing action 1 over 0 is USi(YTA)Tiwhere Si(YTA)≡S(Y−iTiT−iAiA−i) for some function S(·)with range Rds. Strategic interactions enter payoffs through the vector of statistics Si(YTA)due to its dependence on Y−i. An action profile Yconstitutes a pure-strategy Nash equilibrium if for every i∈Nn, Yi=1USi(YTA)Ti>03(2.1) Let ENE(TA)⊆{01}nbe the set of Nash equilibria, that is, the set of action profiles such that for each Y∈ENE(TA),theith component Yisatisfies (2.1)foralli. Example 1. A large literature dating back to Granovetter (1978) studies threshold models of behavior, where agent ichooses action 1 if and only if the number or share of neighbors choosing that action exceeds a threshold (Jackson (2010), Schelling (1978)). This model has been used to study, for example, product adoption and protests (de Matos, Ferreira, and Krackhardt (2014), González (2017)). It corresponds to the payoff function USi(YTA)Ti=β j=i Aij Yj  j=i Aij −ξ(Ti) for the case in which the fraction of adopting neighbors influences own adoption. Here, Si(YTA)=jAij Yj/jAij is the fraction of neighbors choosing action 1, and 2This definition deviates slightly from standard use in referring to a component as the set of agents, rather than the subnetwork on this set of agents. 3The choice of the tie-breaking rule here for indifference is not important for the results. It has no material import in typical econometric applications, where the payoff function is additively separable in a continuously distributed stochastic error. Quantitative Economics 11 (2020) Equilibrium computation in discrete network games 1329 ξ(Ti)/β is agent i’s threshold. This specification is similar to the well-known model of social interactions studied by Brock and Durlauf (2001), which is the discrete choice analog of the Manski (1993) linear-in-means model that is widely used in applied economics to study social interactions. In place of the term multiplying β, we can also consider type-weighted versions of the average action, for example, Si(YTA)=jAij 1{Tj= t}Yj/jAij 1{Tj=t}, or nonlinear functions of Y−iand Aisuch as the minimum or maximum action. Hoxby and Weingarth (2005) motivated the use of these alternative specifications. In these examples, strategic interactions only operate through network neighbors of the ego i. We next impose this restriction more generally. Let N(i) ={j∈Nn:Aij =1}the set of agents connected to i. For any set of agents G⊆Nn,letTG=(Ti)i∈G, and likewise define YG. Assumption 1 (Local interactions). There exists a function ˜ S(·)such that for all n∈N and i∈Nn, Si(YTA)=˜ S(YN(i)TiTN(i)Ai) This says that i’s payoffs only depend on the outcomes, types, and potential links of agents connected to i. It is distinguished from, for example, aggregate games in which payoffs depend on some aggregate statistic involving the actions of all agents (e.g., Menzel (2016)), to which our results do not apply. Econometrician’s information We assume that the econometrician observes the network Aand type profile T, and given a known payoff function U(·),herobjectiveisto compute ENE(TA). Now, typically in practice, Ais observed in the data, but types are instead partitioned into an observed and unobserved component Ti=(Xiεi).Also,both U(·)and the distribution of εigiven Xiare specified up to some unknown parameter θ, in which case Tand U(·)are not entirely known. However, for counterfactual exercises, a candidate value of θis typically selected (e.g., it may be estimated or chosen from an identified set), resulting in a known U(·). Then, for every agent i,theunobservedcomponent εiis drawn from the specified conditional distribution under the candidate θ, resulting in an observed type profile T. Network formation model We consider a nonparametric, stochastic model of network formation for A. The implementation of the algorithm will not depend on this model. Instead, its purpose is to derive bounds on the complexity of our algorithm. To simplify the exposition, we initially consider a model with no strategic interactions, but we later generalize the main result to the larger class of models introduced in Section SA.4, which do allow for strategic interactions. Endow each pair of agents {i j}⊆Nnwith a random utility shock ζij , which is i.i.d. across pairs. For all i j ∈Nnwith i= j, potential links in Asatisfy Aij =gn(τiτjζij ) (2.2) 1330 Michael P. Leung Quantitative Economics 11 (2020) where gn(·)is a {01}-valued function that varies with the network size n,andτi∈Rd is a subvector of Tithat influences link formation (and possibly also outcomes). For example, in the context of friendship formation, τimay include the race and gender of individual i. Since Aij is an undirected network, we assume gn(τiτjζij )=gn(τjτiζji). Semiparametric analogs of (2.2) are commonly used to study link formation (e.g., Fafchamps and Gubert (2007)). Graham (2017) studies estimation of the model gn(τiτjζij )=1h(XiXj)β+αi+αj+ζij >0 where τi=(Xiαi), and only the subvector Xiis observed. The function h(·)allows for homophily in the Xi’s. Our model also allows for homophily in the αi’s. In the case where αiis correlated with some other unobserved component of Tithat enters payoffs U(·), this generates unobserved homophily, which induces a network that is endogenous with respect to the unobserved determinants of outcomes Yi.Model(2.2) also nests stochastic block models and latent space models, which are the subject of a large literature in statistics (e.g., Bickel and Chen (2009)). 2.1 Strategic neighborhoods We next state and motivate a key concept used in our algorithm, which is the notion of a strategic neighborhood. We first need several definitions. For any G⊆Nn, recall that TG=(Tk)k∈Gand AGis the submatrix of Acontaining only the rows and columns of A in G.ThenENE(TGAG)is the set of Nash equilibria in the game where the set of players is Grather than Nn. Define the nonrobustness indicator Rc i=1inf sU(sTi)≤0∩sup s U(sTi)>0(2.3) We say that the equilibrium action of agent iis robust if Rc i=0, and otherwise that it is nonrobust.Wheni’s action is robust, either infsU(sTk)>0or supsU(sTk)≤0.Inthe former (latter) case, agent kchooses action 1 (0) regardless of her neighbors’ outcomes, which only enter k’s payoffs through the first argument of U(·).Hence,Rc i=0implies that i’s equilibrium action is a dominant strategy for the given realization of her type. Define a directed network Don Nnwith ij th entry Dij =Aij Rc j This connects an agent ito a neighbor (with respect to A)jif j’s equilibrium action is nonrobust. Let C(TA)⊆Nnbe the set of strongly connected components of D(see Section 1for a definition). For any G⊆Nn, define S(G) =G∪k∈Nn:max j∈GAjk1−Rc k=1 This adds to Gthe set of agents with robust actions that are connected to G. Definition 1. S(C) is a strategic neighborhood if C∈C(TA). Quantitative Economics 11 (2020) Equilibrium computation in discrete network games 1331 Figure 1. Gray agents have robust actions, white nonrobust. It is not hard to show that the set of strategic neighborhoods coincides with the set of weakly connected components of D(defined in Section 1). Example 2. In Figure 1, agents with robust (nonrobust) actions are colored gray (white). Notice Dhas five strongly connected components, which are the “islands” that result from deleting all links involving the gray agents: {124},{3},{5},{6},{789}. For example, {124}is a strongly connected component, since we can travel from any agent to another through a path of agents with nonrobust actions. On the other hand, {56}is not a strongly connected component because D65 =0. To obtain the strategic neighborhoods, we add to each component the gray agents connected to it, resulting in {15}, {3},{5},{56},{5789}. Observe that these are the weakly connected components of D. For example, {56}is such a component because D56 =1. Note that the strongly connected components partition Nn, whereas the strategic neighborhoods do not. Recall that for any action profile Y,YGis the subprofile (Yi)i∈Gfor any G⊆Nn.Our algorithm exploits the following property of strategic neighborhoods, which is a consequence of Assumption 1: YS(C) ∈ENE(TS(C)AS(C))∀Y∈ENE(TA) (2.4) That is, for any Nash equilibrium Y,thesubprofileYS(C) is a Nash equilibrium in the game with only players in S(C). A formal proof is given in Lemma SA.2.2. For intuition, consider Figure 1. Because agent 1 has a nonrobust action, its optimality may be affected by changes in the action of her neighbor, agent 2. Likewise, agent 2’s action may be affected by changes in those of 3 and 5. However, 3 and 5 have robust actions and consequently maintain the same equilibrium action regardless of those of other agents, say 6 and 7. Therefore, if actions for agents in the strategic neighborhood {12345} are at equilibrium, then they remain optimal even after deleting agents {6789}from the network. 2.2 Algorithm Our algorithm exploits property (2.4) to decompose ENE(TA)into the Cartesian product of equilibrium sets on smaller subnetworks, namely those on strategic neighborhoods. For each C∈C(TA), we need to compute ENE(TS(C)AS(C)). Under assumptions stated in the next subsection, we prove that it is feasible to compute these sets via 1332 Michael P. Leung Quantitative Economics 11 (2020) exhaustive search because the size of the largest strategic neighborhood is Op(log n).To combine these sets and obtain ENE(TA), we have to account for the fact that strategic neighborhoods are not necessarily disjoint. Specifically, if i∈S(C) ∩S(C)for two distinct components C,C, then we need to decide whether i’s action should be dictated by profiles in ENE(TS(C)AS(C))or ENE(TS(C)AS(C)). Fortunately, since C,Cmust be disjoint by virtue of being strongly connected components, it follows that i’s equilibrium action is necessarily robust and, therefore, the same across all equilibria in these two sets. In order to succinctly state the algorithm, we need some additional notation. For G⊆H⊆Nn,let ENE(THAH)|G=Y∈{01}|G|:Y=Y Gfor some Y∈ENE(THAH) which simply drops from each equilibrium action profile in ENE(THAH)the actions corresponding to agents in H\G. Next, for any C∈C(TA)and i∈S(C),let π(i;C) = j∈S(C) 1{j≤i}(2.5) the number of agents in S(C) with label less than or equal to i.4Finally, define YS(C)T=Y∈{01}|S(C)|:Yπ(i;C) =1if inf sU(sTi)>0 and Yπ(i;C) =0if sup s U(sTi)≤0∀i∈S(C)(2.6) This is a subset of all possible action profiles for agents on S(C).Eachprofilein(2.6) fixes the actions of agents with robust actions (Rc i=0) at their dominant strategies (1 if infsU(sTi)>0and 0 if supsU(sTi)≤0). The actions of agents with nonrobust actions are not fixed and vary freely across profiles in this set. We state our proposed procedure in Algorithm 1. Remark 1 (Explanation of Algorithm 1). Line 1computes the set of strategic neighborhoods. As discussed in the previous subsection, this is the same as the set of weakly connected components of D, which can be efficiently computed using wellknown algorithms based on depth-first search. See, for example, the Matlab function graphconncomp() or the NetworkX Python function weakly_connected_ components(). The computational complexity is O(n +L) where Lis the number of links in D(Kleinberg and Tardos (2006)). This assumes the graph is implemented using an adjacency list, which is the efficient format for sparse graphs, the focus of this paper (see Remark 4). 4This definition has the following purpose. Let Y∈{01}|S(C)|be an action profile for agents in S(C). Throughout the paper, our convention is that the components of Yare arranged in increasing order of the label of the corresponding agent. For example, if S(C) ={15}, then the first (second) component of Y dictates the action of agent 1 (5). Hence, under this convention, the action of agent i∈S(C) according to profile Yis given by Yπ(i;C). Quantitative Economics 11 (2020) Equilibrium computation in discrete network games 1339 Remark 9. Theorem SA.4.2 in the Online Supplemental Appendix generalizes Theorem 1, allowing Ato be drawn from a stochastic model of network formation with strategic interactions. 2.5 Multinomial choice Our previous results pertain to games with binary action spaces. We next consider the extension to K+1>2unordered actions, which we arbitrarily label {0K}.Let Uk(Si(YTA)Ti)be i’s utility from choosing action k,where Si(YTA)≡S(Y−iTiT−iAiA−i) (2.14) and S(·)is a function with range Rdssatisfying Assumption 1.AnactionprofileY= (Yi)n i=1is a pure-strategy Nash equilibrium if for every i∈Nn, Yi=kif and only if UkSi(YTA) Ti>U Si(YTA)Ti∀= k (2.15) Example 5. Suppose Ti=((X ikεik))K k=0,whereXik is observed and εik unobserved. Let UkSi(YTA)Ti=θ1+X ikθ2+  βk  j Aij 1{Yj=}  j Aij +εik This allows payoffs from action kto depend on the fraction of neighbors choosing action for any , and the peer effect βk can vary across and k. Algorithm 1and Theorem 1can be extended to this setting if we redefine the nonrobustness indicator (2.3)as Rc i=1inf smin =kUk(s Ti)−U(s Ti)≤0∀k∈{0K}(2.16) To understand this, note that if Rc i=0, then there is some action ksuch that the marginal utility of choosing kover any other is positive in any Nash equilibrium (infsmin=k(Uk(s Ti)−U(s Ti)) > 0), in which case choosing kis the dominant strategy. This definition reduces to (2.3) in the binary choice setting where K=1and the payoff of action 0 is normalized to 0. Algorithm 1can be applied to compute the set of Nash equilibria under multinomial choice by redefining Rc ias (2.16), the definition of equilibrium in line 2of Algorithm 1 as (2.15), and YS(C)T=Y∈{0K}|S(C)|:Yπ(i;C) =kif inf smin =kUk(s Ti)−U(s Ti)>0∀i∈S(C) k ∈{0K} Analogously to (2.6), this is the set of action profiles on S(C) that fix the actions of agents with robust actions at their dominant strategies. The resulting algorithm computes in 1340 Michael P. Leung Quantitative Economics 11 (2020) Op(n1+q)time by Theorem 1, whose proof applies almost verbatim. Example SA.1.2 in Section SA.1 illustrates the interpretation of Assumption 2in the multinomial choice setting. 2.6 Ordered choice We next consider the case in which the action space {0K}is ordered in the natural way. Let U(ySi(YTA) Ti)denote i’s utility from choosing action y,whereSi(YTA) is defined as in (2.14). An action profile Y=(Yi)n i=1is a pure-strategy Nash equilibrium if, for every i∈Nn, Yi=argmax y∈{0K} UySi(YTA) Ti(2.17) Define U(K +1Si(YTA)Ti)=U(−1Si(YTA)Ti)=−∞. Then by Lemma 1 of Aradillas-Lopez and Rosen (2019), (2.17) is equivalent to UYiSi(YTA) Ti ≥maxUYi+1Si(YTA) TiUYi−1Si(YTA)Ti (2.18) if U(·)satisfies a strict concavity condition in its first argument (their Restriction SR(i)). Concavity is a mild restriction guaranteeing each agent ihas an a.s. unique best response to any profile of actions Y−i. We maintain this assumption in what follows. Example 6. Card and Giuliano (2013) estimated an empirical model of peer effects in risky behavior among teens. They consider an ordered response model with strategic interactions with K=2,where0indicates no sexual activity, 1intimate contact without intercourse, and 2intercourse. Their model is equivalent to normalizing the payoff of action 0 to 0and setting U(1Si(YTA)Ti)=X iβ+εi−c1(Y−iA)and U(2Si(YTA)Ti)=2(X iβ+εi)−c1(Y−iA)−c2(Y−iA).Here,Ti=(Xiεi),and Si(YTA)=(c1(Y−iA)c2(Y−iA)) are cutoffs that depend on the actions of other agents. Then defining U∗ i=X iβ+εi,aNashequilibriumYsatisfies, for all agents i, Yi=⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 0if U∗ i≤c1(Y−iA) 1if c1(Y−iA)<U∗ i≤c2(Y−iA) 2if c2(Y−iA)<U∗ i Examples of cutoffs are c1(Y−iA)=α1−γ1  j Aij 1{Yj≥1}  j Aij c 2(Y−iA)=α2−γ2  j Aij 1{Yj=2}  j Aij  where α2>α 1and α1<α 2−γ2to ensure strict concavity. This example coincides with the baseline specification of Card and Giuliano (2013) in their setting where a network Quantitative Economics 11 (2020) Equilibrium computation in discrete network games 1341 consists of only two linked agents. Under strategic complements (γ1γ2≥0), it says that agents choose riskier behaviors the higher the share of their friends choosing riskier behaviors. We extend Algorithm 1and Theorem 1to ordered choice by redefining (2.3)as Rc i=1inf sU(ysTi)−maxU(y +1sTi) U(y −1sTi)<0 ∀y∈{0K} Similar to (2.16), if Rc i=0, then there is some action ysuch that the marginal utility of choosing yover any other action is positive in any Nash equilibrium, so that choosing y is the dominant strategy. In Example 6, Rc i=1X iβ+εi−α1+max{γ10}>01X iβ+εi−α2+min{γ20}<0 ×1min−X iβ+εi+α2−max{γ20}X iβ+εi−α1+min{γ10}<0 Algorithm 1can be applied to compute the set of Nash equilibria by redefining Rc ias above, the definition of equilibrium in line 2of Algorithm 1as (2.18), and YS(C) T=Y∈{0K}|S(C)|:Yπ(i;C) =yif inf sU(ysTi)−maxU(y +1sTi) U(y −1sTi)≥0 ∀i∈S(C)y ∈{0K} Analogously to (2.6), this is the set of action profiles on S(C) wherewefixtheactions of agents with robust actions at their optimal choices. Theorem 1, whose proof applies almost verbatim to the resulting algorithm, implies its computational complexity is Op(n1+q). 3. Numerical illustrations This section illustrates the performance of our algorithms on graphical games estimated in Card and Giuliano (2013)andXu (2018). We also show empirically the relationship discussed in Remark 8between computational feasibility and the parameter λmk in Assumption 2that controls the strength of strategic interactions. 3.1 Binary choice We consider a binary graphical game inspired by Xu (2018), who estimates a model of college attendance with social interactions. He specifies net payoffs from attendance as USi(YTA)Ti=X iθ+β j Aij Yj  j Aij +εi 1342 Michael P. Leung Quantitative Economics 11 (2020) which corresponds to Example 1with a linear model for the threshold. Here, Yiis student i’s college attendance decision, and Aij represents friendship between iand j.We apply Algorithm 1to compute the set of pure-strategy Nash equilibria using his estimated parameters. Xu (2018) used data from the restricted-use sample of Add Health (Harris and Udry (2018)), only using the three largest schools (831 student observations). We instead use all schools from the public-use sample, excluding students with missing data (1952 students). We construct the covariates Xiused in his application, and following his setup, draw εifrom the logistic distribution. The public-use sample contains information on degrees (number of friends of each student) but not the full network A. We opt to simulate a network from a configuration model (Jackson (2010, Chapter 4.1.4)) calibrated to the empirical degree sequence of the Add Health network. This model approximately draws a network uniformly at random from the set of all networks such that the degree sequence matches the empirical degree sequence.10 For (θ β), we take the estimate in Table 5, column AMLE(4)of Xu (2018)andadd02 to the estimated value of β. As noted in Xu’s paper, the partial-equilibrium peer effects suggested by these estimates are fairly large and similar to those of other studies. With Xu’s original estimates, for an agent with covariates equal to the mean covariate vector, the probability of college attendance increases by 1183% if the fraction of friends attending increases from 0to 05in partial equilibrium. Using our sample and modified parameters, this marginal effect is instead 46%. We compute the set of Nash equilibria for 100 simulation draws. Each simulation redraws random utility shocks and a network from the configuration model, while keeping covariates fixed. Shocks are independent across agents and of the network, as in Xu’s application. Computation is carried out on a laptop with a 26GHz processor and 8GB of memory. The algorithm is coded in Python and does not parallelize. Table 1reports the results. The rows give the mean, standard deviation, minimum, and maximum of the statistic across simulation draws. Note that the standard deviation for the average degree of Ais almost zero because the degree distribution is given by the data and essentially fixed across draws. We see that the average outcome is similar across equilibria, and the number of equilibria is small, on average around three. The computation time is 1second on average, although occasionally the largest component can have a larger number of agents, resulting in a longer computation time. In this case, the largest size is 19, and computing the corresponding set of equilibria takes about half a minute. We next numerically illustrate the relationship between βand the size Δof the largest component of D. The motivation is that βcontrols the strength of strategic interactions λmk. Our theoretical results require this parameter to be less than one, which ensures that the size of the largest component Δgrows only logarithmically with n.Recall that, in line 2of Algorithm 1, the most computationally intensive step is computing 10We use out-degrees (number of friends named by the ego) as degrees. We simulate a single network A on all observations. In reality, the data consists of several schools with few cross-school links. Quantitative Economics 11 (2020) Equilibrium computation in discrete network games 1343 Table 1. Results. ¯ YLower ¯ YUpper # NE Time ΔDDeg AGiant ADeg Mean 0141 0142 3211840488 171764914 SD 0008 0008 3053340040 140004 Min 0118 0118 1001400395 171504902 Max 0166 0167 1603781900607 171904921 Note:n=1952,100 simulations. Column 1 is the smallest average outcome across simulations, column 2 the largest. Column 3 is the number of equilibria. Column 4 is computation time in seconds. Column 5 (7) is the size of the largest component of D(A) and column 6 (8) the average degree of D(A). the equilibrium set of the strategic neighborhood corresponding to the largest component of C(TA). As discussed in Remark 2, this requires searching over 2Δelements, so Δdetermines the computational feasibility of our proposed algorithm. If βis too large, then Δwill be too large for feasible computation. We simulate Daccording to the same model above, except with βincreased by 06 rather than 02. As predicted by the theory, with a larger β(and hence larger λmk), the average size of the largest component increases to 32. This corresponds to a significant increase in 2Δand, therefore, the expected computation time. When we increase βby 1 rather than 06, the average size of the largest component balloons to 159, so computing the equilibrium set is infeasible in practice. 3.2 Ordered choice We repeat the exercise in the previous subsection, now using the ordered choice model of Card and Giuliano (2013)inExample6. We construct their covariates Xiusing the public-use sample of Add Health, whereas the authors utilize the restricted-use sample. After discarding observations with missing data, our sample size is 1184.Wecalibrate the values of β,γ1,γ2using the third columns of Tables 3 and A3 of their paper. This corresponds to their specification allowing for peer effects but assuming independent random-utility shocks across agents. The authors do not report estimates of the intercepts α1,α2, so we set them to −15,15, respectively. For these parameter values and our data, given an agent with covariates equal to the mean covariate vector, their probability of engaging in no sexual activity (action 0) decreases by 23% if the fraction of friends engaging in at least some intimate contact (actions 1 or 2) increases from 0to 05in partial equilibrium. The corresponding partialequilibrium effect on the probability of engaging in intercourse (action 2) is a 20% increase. We compute the set of Nash equilibria for 100 simulation draws using modifications to Algorithm 1discussed in Section 2.6. We draw random utility shocks εifrom a standard normal distribution, following Card and Giuliano (2013). Independently of the shocks, we draw the network from a configuration model calibrated to the empirical degree sequence, as in the previous binary choice illustration. This setting differs from that of Card and Giuliano (2013) because we use friendship network data and assume 1344 Michael P. Leung Quantitative Economics 11 (2020) Table 2. Results. ¯ YLower ¯ YUpper # NE Time ΔDDeg AGiant ADeg Mean 1224 1226 2162630401 98554515 SD 0014 0014 18376270045 160000 Min 1188 1188 1001200230 98104515 Max 1265 1267 160 37401600503 98704515 Note:n=1184,100 simulations. Column 1 is the smallest average outcome across simulations, column 2 the largest. Column 3 is the number of equilibria. Column 4 is computation time in seconds. Column 5 (7) is the size of the largest component of D(A) and column 6 (8) the average degree of D(A). our whole sample (1184 observations) is part of the same game, whereas the authors assume that each game consists of only two students who are best friends. Finally, due to the larger action space, we parallelize 2of the algorithm across 16 cores (8GB memory per core, 2–3GHz CPUs) for components Cof size at least 12. Table 2reports the results of this exercise. The statistics for Δare largely similar to the binary choice exercise. The computation time is 2seconds on average, and the longest computation time is about 6minutes, which corresponds to a simulation draw for which the size of the giant component of Dis 16. 4. Conclusion We propose new algorithms for computing the set of Nash equilibria of graphical games. For models satisfying a restriction on the strength of strategic interactions, we show the algorithms typically complete in polynomial time, or more formally, in Op(nc)evaluations of the payoff function for some c>1. Our theory and simulation results suggest that the closer the restriction is to being violated, the larger the exponent c, and hence the more difficult it is to compute the equilibrium set. The algorithms proceed by constructing small subgames for which it is feasible to compute the equilibrium set and then combining these sets. These subgames correspond to the components of a certain network, which can be quickly computed using well-known algorithms based on depth-first search. Under our conditions, we show that the largest component is typically small, scaling logarithmically with the network size. It then becomes feasible to exhaustively search the space of action profiles component by component to compute all equilibria. In the Online Supplemental Appendix, we provide algorithms for computing equilibria of network formation games, including pairwise stable and Nash stable equilibria. The former solution concept only allows an agent to unilaterally deviate by deleting a single link, while the latter allows for unilateral deletion of multiple links. It is possible to consider refinements in the undirected setting, such as pairwise Nash stability, by combining aspects of both algorithms. We discuss how the algorithms can be applied to compute previously intractable sharp bounds on structural parameters based on moment inequalities in Sheng (2016). Quantitative Economics 11 (2020) Equilibrium computation in discrete network games 1345 References Aradillas-Lopez, A. and A. Rosen (2019), “Inference in ordered response games with complete information.” CeMMaP working paper. [1340] Bajari, P., H. Hong, J. Krainer, and D. Nekipelov (2010), “Computing equilibria in static games of incomplete information using the all-solution homotopy.” Operations Research, 58, 237–245. [1327] Bajari, P., H. Hong, and S. Ryan (2010), “Identification and estimation of a discrete game of complete information.” Econometrica, 78 (5), 1529–1568. [1325] Barabási, A. (2015), Network Science. Cambridge University Press. [1337] Bhattacharya, D., D. Pascaline, and S. Kanaya (2019), “Demand and welfare analysis in discrete choice models with social interactions.” Working paper. [1325] Bickel, P. and A. Chen (2009), “A nonparametric view of network models and Newman– Girvan and other modularities.” Proceedings of the National Academy of Sciences, 106 (50), 21068–21073. [1330] Bickel, P., A. Chen, and E. Levina (2011), “The method of moments and degree distributions for network models.” Annals of Statistics, 39 (5), 2280–2301. [1336] Bollobás, B. (2001), Random Graphs. Cambridge University Press. [1334] Bollobás, B., S. Janson, and O. Riordan (2007), “The phase transition in inhomogeneous random graphs.” Random Structures and Algorithms, 31 (1), 3–122. [1336,1338] Bollobás, B. and O. Riordan (2008), “Random graphs and branching processes.” In Handbook of Large-Scale Random Networks, 15–115, Springer. [1327] Bramoullé, Y., H. Djebbari, and B. Fortin (2009), “Identification of peer effects through social networks.” Journal of Econometrics, 150 (1), 41–55. [1326,1334] Brock, W. and S. Durlauf (2001), “Discrete choice with social interactions.” Review of Economic Studies, 68 (2), 235–260. [1329] Calvó-Armengol, A., E. Patacchini, and Y. Zenou (2009), “Peer effects and social networks in education.” Review of Economic Studies, 76 (4), 1239–1267. [1326,1335] Card, D. and L. Giuliano (2013), “Peer effects and multiple equilibria in the risky behavior of friends.” Review of Economics and Statistics, 95 (4), 1130–1149. [1326,1340,1341,1343] Chandrasekhar, A. (2016), “Econometrics of network formation.” In Oxford Handbook on the Econometrics of Networks (Y.Bramoullé,A.Galeotti,andB.Rogers,eds.).[1337] Daskalakis, C., P. W. Goldberg, and C. H. Papadimitriou (2009), “The complexity of computing a Nash equilibrium.” SIAM Journal on Computing, 39 (1), 195–259. [1327] Daskalakis, C. and C. Papadimitriou (2006), “Computing pure Nash equilibria in graphical games via Markov random fields.” In Proceedings of the 7th ACM Conference on Electronic Commerce, 91–99. ACM. [1326,1333] 1346 Michael P. Leung Quantitative Economics 11 (2020) de Matos, M. G., P. Ferreira, and D. Krackhardt (2014), “Peer influence in the diffusion of theiPhone3Goveralargesocialnetwork.”Management Information Systems Quarterly, 38 (4), 1103–1133. [1328] Fafchamps, M. and F. Gubert (2007), “The formation of risk-sharing networks.” Journal of Economic Development, 83, 326–350. [1330] González, F. (2017), “Collective action in networks: Evidence from the Chilean student movement.” PUC-Chile working paper. [1328] Graham, B. (2017), “An econometric model of network formation with degree heterogeneity.” Econometrica, 85 (4), 1033–1063. [1330] Granovetter, M. (1978), “Threshold models of collective behavior.” American Journal of Sociology, 83 (6), 1420–1443. [1328] Harris, K. and R. Udry (2018), “National longitudinal study of adolescent to adult health (Add Health), 1994–2008 [public use].” Ann Arbor, MI: Carolina Population Center, University of North Carolina-Chapel Hill [distributor], Inter-University Consortium for Political and Social Research [distributor]. [1342] Herings, P. and R. Peeters (2010), “Homotopy methods to compute equilibria in game theory.” Economic Theory, 42 (1), 119–156. [1327] Hoxby, C. and G. Weingarth (2005), “Taking race out of the equation: School reassignment and the structure of peer effects.” Stanford working paper. [1329] Jackson, M. (2010), Social and Economic Networks. Princeton University Press. [1326, 1328,1342] Janson, S., T. Luczak, and A. Rucinski (2011), Random Graphs, Vol. 45. John Wiley & Sons. [1338] Jia, P. (2008), “What happens when Wal-Mart comes to town: An empirical analysis of the discount retailing industry.” Econometrica, 76 (6), 1263–1316. [1326] Judd, K., P. Renner, and K. Schmedders (2012), “Finding all pure-strategy equilibria in games with continuous strategies.” Quantitative Economics, 3 (2), 289–331. [1327] Kearns, M. (2007), “Graphical games.” In Algorithmic Game Theory (N.Nisan,T.Roughgarden, E. Tardos, and V. Vazirani, eds.). Cambridge University Press. Chapter 5. [1326] Kleinberg, J. and E. Tardos (2006), Algorithm Design. Pearson Education, Inc. [1332] Leung, M. (2019), “Inference in models of discrete choice with social interactions using network data.” arXiv preprint arXiv:1911.07106v1.[1326,1327,1334] Leung, M. and R. Moon (2019), “Normal approximation in large network models.” arXiv preprint arXiv:1904.11060v1.[1326,1327,1334] Leung, M. P. (2020), “Supplement to ‘Equilibrium computation in discrete network games’.” Quantitative Economics Supplemental Material, 11, https://doi.org/10.3982/ QE1386.[1327] Quantitative Economics 11 (2020) Equilibrium computation in discrete network games 1347 Manski, C. (1993), “Identification of endogenous social effects: The reflection problem.” Review of Economic Studies, 60 (3), 531–542. [1329] Mele, A. (2019), “Does school desegregation promote diverse interactions? An equilibrium model of segregation within schools.” JHU working paper. [1325] Menzel, K. (2016), “Inference for games with many players.” Review of Economic Studies, 83 (1), 306–337. [1329] Miyauchi, Y. (2016), “Structural estimation of pairwise stable networks with nonnegative externality.” Journal of Econometrics, 195 (2), 224–235. [1325] Mode, C. (1971), Multitype Branching Processes: Theory and Applications,Vol.34.American Elsevier Pub. Co. [1338] Schelling, T. (1978), Micromotives and Macrobehavior. Norton & Company, New York, NY. [1328] Sheng, S. (2016), “A structural econometric analysis of network formation games.” UCLA working paper. [1344] Soetevent, A. and P. Kooreman (2007), “A discrete-choice model with social interactions: With an application to high school teen behavior.” Journal of Applied Econometrics,22 (3), 599–624. [1325] Turova, T. (2012), “Asymptotics for the size of the largest component scaled to “logn”in inhomogeneous random graphs.” Arkiv för Matematik, 51 (2), 371–403. [1338] Xu, H. (2018), “Social interactions in large networks: A game theoretic approach.” International Economic Review, 59, 257–284. [1326,1341,1342] Xu, X. and L. Lee (2015), “Estimation of a binary choice game model with network links.” OSU working paper. [1325] Co-editor Peter Arcidiacono handled this manuscript. Manuscript received 10 July, 2019; final version accepted 22 June, 2020; available online 9 July, 2020.