Scenario Sampling for Large Supermodular Games

Scenario Sampling for Large Supermodular Games

\thispagestyle{empty}

\setcounter{page}{1}

Introduction

Payoff interdependence, where the utility one agent gets from taking a particular action varies with the actions chosen by others, characterizes many models of economic behavior. The returns to adopting a networked technology increase in the fraction of other agents also adopting Goolsbee_Klenow_JLE2002,Ackerberg_Gowrisankaran_RAND2006. A teen's decision to smoke may be influenced by whether her friends also smoke Gaviria_Raphael_RESTAT2001,Krauth_JBES2007,Card_Giuliano_RESTAT2013. The returns to forming an R&D partnership (or a supply chain relationship) between two firms might vary with the presence or absence of such partnerships (relationships) across other firms. Firms' decisions regarding market entry typically depend on the entry decisions of competing firms Bresnahan_Reiss_JOE91, Jia_EM08,Ciliberto_Tamer_EM2009. In these settings, and many others, it is convenient to view the set of actions taken by agents as an equilibrium of a game. \\ \\ The econometric analysis of games poses a number of, now well understood, challenges (see, for example, the surveys by dePaula_ARE13, Aradillas_Lopez_ARE2020 and Molinari_HBE2020). One set of issues stems from model incompleteness: econometric models of strategic interaction often admit multiple Nash Equilibria (NE) for a given set of (unobserved) preference shocks, $\mathbf{U}$, and (unknown) payoff parameters, $\theta$. Another set of issues involves computational tractability. Even if the econometrician “completes” the model by specifying which equilibrium is played when (or, more generally, writes down an equilibrium selection model), parameter estimation in complete information games with more than a handful of players and actions is often infeasible because evaluating the likelihood function involves a high-dimensional integral with a complex region of integration. \\ \\ In this paper we introduce an approach to payoff parameter estimation appropriate for large supermodular complete information games with binary actions. By “large" we mean games with hundreds of players, each of whom might take hundreds of of actions (i.e., games with tens of thousands of strategic variables). This class of games includes many examples of interest to empirical researchers in economics and other fields. \\ \\ Consider the peer effects in smoking example introduced above (with $t=1,\ldots,T$ players). A researcher might postulate that the payoff from smoking is increasing in the fraction of one's peers who smoke. The payoff may also vary with observed agent attributes, $X_t$, and an unobserved normally (or logistically) distributed random utility “shock", $U_t$. Under complete information, any pure strategy Nash Equilibrium (NE) in this setting will coincide with a fixed point of a system of $T$ non-linear simultaneous equations. A consequence of this simultaneous determination of smoking decisions is that an agent's unobserved taste for smoking -- the Gaussian random utility shock in her payoff function -- will co-vary with the fraction of her peers that smoke. The naive probit regression fit of own smoking behavior onto own attributes and the fraction of peers smoking does not consistently recover agent preferences Heckman_EM1978. \\ \\ If the researcher is willing to make an equilibrium selection assumption, we will assume that the NE equilibrium with the fewest number of smokers is the one that prevails, then the likelihood is well-defined. Evaluating this likelihood, because it requires computing a $T$-fold integral, is difficult. For modest $T$, say 20 or 30 agents, Krauth_JOE2006 and Soetevent_Kooreman_JAE07 have proposed simulation algorithms for computing this integral. These algorithms make use of additional structure in this example beyond supermodularity. Our approach handles this example as well as others, including those where, say, $T=500$, and each agent takes $M>1$ actions. In such settings likelihood evaluation requires computing a $TM$-fold integral with a very complex region of integration. \\ \\ For researchers unfamiliar with the econometric complexities of game estimation, our method is relatively straightforward to adopt. For example, a peer effects researcher can simply introduce the fraction of one's peers who smoke as a “covariate" in a probit-like specification. In typical examples computation requires no more than a few minutes on a good desktop computer. Unlike the naive probit fit described above, our method -- by appropriately handling the game-theoretic aspects of the model -- delivers consistent estimates of payoff function parameters under easy to communicate assumptions. \\ \\ For economists with experience in game estimation, our approach makes large game analysis feasible. For example, we show how our methods can be used to estimate payoff functions in some models of (directed) network formation. In this example each of $T$ agents decides whether to direct a link (or not) to each of the $T-1$ other agents in her network. This results in a game with $T(T-1)=O(T^2)$ strategic variables. In an empirical illustration we study the Nykatoke network dataset collected by deWeerdt_IAP04. This network includes $T=116$ households. Following deWeerdt_IAP04 we fit a model which includes household specific sender and receive fixed effects, observed household attributes, and a taste for supported links (see Jackson_et_al_AER12). We are aware of no extant methods, beyond those introduced below, that would allow a researcher to empirically study a game with over $13,000$ strategic decision variables with a payoff function indexed by over two hundred parameters.\footnote{We defer on a discussion of whether fitting such a high dimensional model to the Nyakatoke network is sensible to later in the paper.} \\ \\ Computational limits have profoundly shaped the nature of empirical work involving strategic interaction. While methods that fully embrace payoff interdependence and strategic interaction commonly feature in empirical industrial organization, where many settings of interest involve just a few agents Ciliberto_Tamer_EM2009, applications involving many agents and/or actions are scarce. The failure to embrace the “strategic nature” of discrete interactions in, for example, empirical peer effects analyses arguably undermines the credibility of work in this area. Indeed, this was one theme of Manski_ReStud93. We emphasize peer effects and network formation examples below. \\ \\ An important accomplishment of econometricians studying games has been the development of methods of inference that do not require making a priori assumptions on equilibrium selection (see Molinari_HBE2020 for a comprehensive survey). We depart from this norm and do maintain an equilibrium selection assumption in what follows (see also Bajari_et_al_EM10). Our results are also restricted to supermodular games (loosely games where the actions of others do not discourage -- or weakly encourage -- a player to take an action). While they are restrictive relative to some treatments in prior work, these assumptions allows us to focus on our main contribution: likelihood evaluation for very large games. We discuss how to relax our equilibrium selection assumption at the close of the paper. \\ \\ In a large game, evaluating the likelihood involves computing a high-dimensional integral over a complex region of integration. Our approach involves transforming this integral into an expectation and using importance sampling to estimate it. The use of importance sampling in the simulated maximum likelihood (SML) context goes back at least to McFadden_EM89 in the econometrics literature. Our particular problem requires computing the sum of a (typically very large) set of “rectanglar” probabilities (i.e., hypercube volumes). Similar to the GHK algorithm of Geweke_EM1989, Hajivassiliou_Ruud_HBE1994, Keane_EM94 and Hajivassiliou_et_al_JOE1996, we generate random vectors within a target rectangle by taking draws from a sequence of univariate truncated distributions. Unlike the GHK simulator, the location of the rectangles whose volume we require is not known ex ante and the points of truncation are determined sequentially via game-theoretic arguments. We also compute individual rectangle probabilities “analytically" as opposed to using a weighted frequency estimator. We elaborate on these and other differences below. \\ \\ To be clear, our innovation is the introduction of a particular importance sampler: scenario sampling. The likelihood of a game outcome, say $\mathbf{Y}=\mathbf{y}=\left(y_1, \dots y_T \right)'$, conditional on a set of agent attributes, $\mathbf{X}=\left(X_1, \dots X_T \right)'$, and parameter value, $\theta$, coincides with the probability that the set of random utility shocks, $\mathbf{U}=\left(U_1, \dots U_T \right)'$, lie in a region where $\mathbf{Y}=\mathbf{y}$ is the selected NE. In a binary action game this region will be a collection of high-dimensional hyper-cubes or “scenarios". The total volume of these cubes equals the likelihood. We estimate this volume by sampling scenarios and aggregating them in a particular way. \\ \\ In order to sample a scenario in the target set, we need to construct a vector of random utility draws $\mathbf{U}$ such that $\mathbf{Y}=\mathbf{y}$ is the selected NE with probability one. We accomplish this task by drawing the agent-by-action random utility shocks sequentially. The support of a given draw may depend on the realizations of prior draws. Such an approach allows us to ensure that, in the end, $\mathbf{U}$ will be such that $\mathbf{Y}=\mathbf{y}$ is the selected NE. Our sequential sampler uses both the structure of the NE conditions as well as supermodularity. \\ \\ The methods introduced below make estimation of a binary peer effects games with hundreds of peer groups, each consisting dozens of agents, relatively routine. Similarly we outline a set of tools that would allow a researcher to easily fit an economically interesting structural model of strategic network formation to a graph consisting of hundreds of agents. We are aware of no comparable estimation methods for these settings.\footnote{The closest competitor would be the simulated method-of-moments (SMM) approach outlined by Uetake_Watanabe_AE13 and used by Jia_EM08, Nishida_MS2015 and Miyauchi_JOE16. This approach involves comparing moments calculated from simulated game outcomes to those observed in the dataset in hand. Depending on the application of interest, this approach can be of comparable computational cost to ours. In other settings it can be more costly. For example, in the context of network formation models, it is well-known that computing induced subgraph frequencies -- the natural moments to use for SMM estimation in this context -- is computationally very costly Bhattacharya_Bickel_AS15, Graham_HBE2020. If the target parameter $\theta$ has more than a few components, then our method -- as it allows for gradient-based optimization -- also has possible speed advantages. For some models we are also able to avoid repeated NE computation, something that is required by the SMM-method (see Appendix (ref)). Finally, our approach, being likelihood-based, also offers efficiency advantages and facilitates Bayesian inference (for interested researchers).} \\ \\ The next section introduces a simple, and likely familiar, coordination game. We use this game to introduce the main assumptions and features of our methods in an easy to understand way. \\ \\ Section (ref) extends our basic analysis to binary peer effects games. The analysis of such games is commonplace, but extant empirical work generally ignores, or side-steps, game theoretic difficulties (but see Krauth_JOE2006,Krauth_JBES2007 and Soetevent_Kooreman_JAE07 for important exceptions). Section (ref) extends our results to a general class of discrete supermodular games. Certain games of technology adoption and network formation, as we explain, are members of this class. \\ \\ In Section (ref) we explore the numerical properties of our methods via a series of Monte Carlo experiments. Finally, in Section (ref), we use our methods to estimate the payoff parameters in a game of network formation using the Nyakatoke network data collected by deWeerdt_IAP04. Our empirical model of network formation is inspired by the “support" model of favor exchange introduced by Jackson_et_al_AER12. \\ \\ In what follows random variables are denoted by capital Roman letters, specific realizations by lower case Roman letters and their support by blackboard bold Roman letters. That is $Z$, $z$ and $\mathbb{Z}$ respectively denote a generic random draw of, a specific value of, and the support of, $Z$. Random vectors and matrices are generally written in boldface (e.g., $\mathbf{X}$). We use Greek letters for parameters and a “0" subscript to denote their population values. We sometimes omit this subscript when doing so causes no confusion. \\ \\

A simple coordination game

We begin with a simple game of coordination between a pair of friends $t=1,2$. Each friend/agent takes a binary action $Y_{t}\in \left\{ 0,1\right\}$. In Card_Giuliano_RESTAT2013 $Y_{t}$ corresponds to adolescent behaviors such as sexual intercourse, smoking, marijuana use or chronic truancy. To keep things concrete (and light) we will consider two friends, Ademaro ($t=1$) and Brunhilde ($t=2$), who are deciding whether to attend ($Y_{t}=1$) an electronic dance music (EDM) concert or not ($Y_{t}=0$). \\ \\ The payoff function equals

for $t=1,2$. The payoff from not attending the concert is normalized to zero for both agents. Observable differences in the taste for EDM are captured by variation in the linear index $X_t'\beta$. Unobserved heterogeneity is captured by the random utility shifter $U_t$. Note the negative sign in front of $U_t$; hence it measures an agent's unobserved distaste for EDM. The notation $y_{-t}$ denotes the actions of players other than $t$. \\ \\ As we assume that $\delta\geq0$, the marginal utility associated with attending the concert, $Y_{t}=1$, is greater when your friend also attends, $Y_{-t}=1$. This makes the game supermodular. Ademaro's utility from attending, $Y_{1}=1$, when Brunhilde does not, $Y_{2}=0$, is \[ v\left(1,0;X_{1},U_{1},\theta\right)=X_{1}'\beta-U_{1}. \] Whereas if Brunhilde also attends his utility increases by $\delta$ to \[ v\left(1,1;X_{1},U_{1},\theta\right)=X_{1}'\beta+\delta-U_{1}. \] Similarly the utility Brunhilde receives from attending the concert depends on whether Ademaro does not attend

or does attend \[ v\left(1,1;X_{2},U_{2},\theta\right)=X_{2}'\beta+\delta-U_{2}. \]

Scenarios

The systematic utility of taking the action, $X_{t}'\beta+\delta y_{-t}$, when evaluated at all possible combinations of peer play, $y_{-t} \in \left\{0,1\right\}$, defines a partition of the support of $U_t$ into what we call buckets Pelican_Graham_NBER2020; also see Figure (ref). The bucket partition for the support of $U_{t}$, for $t=1,2$, is

The number of buckets will coincide with the number of possible peer play case distinctions, $L$, plus $1$. Specifically, the bucket partition (and its cardinality) can be found mechanically by evaluating the utility function for all possible values of $y_{-t}$. \\ \\ In our EDM example $L=2$, such that there are three buckets. If $U_1$ falls into the first bucket, then Ademaro's taste shock is sufficiently low that it is strictly dominant for him to attend the concert. That is he will go irrespective of what Brunhilde chooses to do. If $U_1$ instead falls into the second, or middle, bucket, then Ademaro is on the fence. His $U_1$ realization is low enough that it will be optimal for him to attend the concert if Brunhilde does as well, but he will not go to the concert without Brunhilde. Finally if $U_1$ falls into the third bucket, then it is a strictly dominant strategy for Ademaro to not go to the concert: his distaste for EDM is so high that even the presence of Brunhilde at his side is not enough to entice him to go. The interpretation of Brunhilde's bucket partition is analogous. \\ \\ A pair of buckets, one from Ademaro and one from Brunhilde, defines what we call a scenario. Let $\mathbf{b}_{jk}$ denote the scenario where $U_{1}$ falls into bucket $j=1,2,3$ and $U_{2}$ falls into bucket $k=1,2,3$. A scenario is a region of the support of $\mathbf{U}=\left(U_1,U_2\right)'$ where the fundamental strategic considerations of agents are constant. In other words, a scenario defines a range of realizations for the utility/cost shocks $\mathbf{U}=\left(U_{1},U_{2}\right)'$ where, within them, the fundamental nature of strategic play does not depend on the precise values of $U_{1}$ or $U_{2}$. \\ \\ In Figure (ref) scenario $\mathbf{b}_{22} = \left(X_{1}'\beta, X_{1}'\beta+\delta \right] \times \left(X_{2}'\beta, X_{2}'\beta+\delta \right]$ corresponds to a pair of random utility draws $\mathbf{U}=\left(U_1,U_2\right)'$ where both Ademaro and Brunhilde are “on the fence" about going to the concert. That is where it is a NE for them to both go or to both not go. This conclusion does not depend on the precise values of $U_{1}$ and $U_{2}$, only that they are somewhere within scenario $\mathbf{b}_{22}.$ \\ \\ In scenario $\mathbf{b}_{22}$ there are two NE, $\mathbf{Y}=\left(0,0\right)'$ and $\mathbf{Y}=\left(1,1\right)'$; the model is incomplete. In what follows we complete the model by assuming that when $\mathbf{U} \in \mathbf{b}_{22}$ Ademaro and Brunhilde do not go the concert (that is that $\mathbf{Y}=\left(0,0\right)'$ is the selected NE). This is a special case of our assumption, stated formally below, that the equilibrium with the “least" amount of action is the one that prevails if $\mathbf{U}$ falls in a scenario that supports multiple NE. \\ \\ The set of all scenarios, denoted by $\mathbb{B}$, partitions the support of $\mathbf{U}=\left(U_1,U_2\right)'$ into a set of nine rectangles:

See Figure (ref) for an illustration Bresnahan_Reiss_JOE91,Tamer_ReStud03,dePaula_ARE13). For the time being we use double subscripts to index different scenarios. As a second example of a scenario, when $U_{1}$ lies in its first bucket, and likewise for $U_{2}$, then Ademaro and Brunhilde are in scenario $\mathbf{b}_{11} = \left(\infty, X_{1}'\beta\right] \times \left(\infty, X_{2}'\beta\right]$ (corresponding to the lower-left-hand rectangle in Figure (ref)). In this scenario Ademaro's (Brunhilde's) utility/cost shock is so low that he (she) will attend the EDM concert irrespective of whether Brunhilde (Ademaro) does. In this scenario both players' strictly dominant strategy is to attend the concert; $\mathbf{Y}=\left(1,1\right)'$ is the NE. \\ \\

Likelihood

With an equilibrium selection assumption in hand, the probability of any game outcome $\mathbf{Y}=\mathbf{y}=\left(y_{1},y_{2}\right)'$ simply corresponds to the probability that $\mathbf{U}=\left(U_{1},U_{2}\right)$ falls into one of the scenarios in which $\mathbf{Y}=\mathbf{y}$ is the (selected) NE. We denote the subset of scenarios where $\mathbf{Y}=\mathbf{y}$ is the NE by $\mathbb{B}_{\mathbf{y}}$. The set of all scenarios is denoted by $\mathbb{B}$.

\\ \\ For example, the probability of observing $\mathbf{Y}=\left(1,1\right)'$ in a randomly sampled EDM concert attendance game (from some well-defined population of EDM concert attendance games), corresponds to the ex ante chance that a pair of random utility shocks falls into one of the three darker shaded regions of Figure (ref) (i.e., into scenarios $\mathbf{b}_{11}$, $\mathbf{b}_{12}$ or $\mathbf{b}_{22}$):

where we assume that $U_{1}$ and $U_{2}$ are iid with known CDF $F\left(\cdot\right)$ and PDF $f\left(\cdot\right)$ such that $f_{\mathbf{U}}\left(\mathbf{u}\right)=f\left(u_{1}\right)f\left(u_{2}\right)$. \\ \\ The three summands in (ref) correspond to the probability mass attached to each of the three colored scenarios in Figure (ref). In this simple two player game, with two-dimensional scenarios, direct likelihood evaluation involves no difficulties. Consequently maximum likelihood estimation (MLE) is both straightforward and entirely standard. \\ \\ However, consider the direct extension of the game to accommodate three players. In such a game there would be four buckets and $4^3=64$ scenarios (corresponding to cubes in $\mathbb{R}^3$).\footnote{If agents are not exchangeable, for example peers are “best friends" and “second best friends", then there would be $5$ buckets and $125$ scenarios.} In general, the number of scenarios for an observed game outcome will grow exponentially with the number of players/strategic decisions.\footnote{In games with additional special structure, the number of scenarios may grow more slowly with $T$.} In this paper we are interested in large games. Those with many players, $T$, each of whom, might take many binary actions, $M$. When $TM$ is in the hundreds or thousands, direct likelihood evaluation, and hence MLE, is not feasible. \\ \\ Our approach to (approximate) likelihood evaluation in many scenario games involves simulation. The probability that a random draw of $\mathbf{U}=\left(U_{1},U_{2}\right)'$ falls in scenario $\mathbf{b}$ is simply

where we suppress the role of covariates, $\mathbf{X}$, in the notation. For example, the ex ante probability that Ademaro and Brunhilde find themselves in scenario $\mathbf{b}_{22}$ is

Observe that $\zeta\left(\mathbf{b};\theta\right)$ is a pmf for scenarios with support $\mathbb{B}$. Let $\mathbf{B}$ denote a random draw from the distribution of scenarios described by this pmf. We can re-write the likelihood of the event $\mathbf{Y}=\tbinom{1}{1}$, that is equation (ref), as

Conceptually, the probability to the right of the last equality above is straightforward to simulate (practically, as we will see, there are difficulties). To see this note that every random draw, $\mathbf{U}$, from the population distribution of preference shocks, $F_{\mathbf{U}}$, will fall into one, and only one, scenario. The event $\mathbf{U} \in \mathbf{b}$ occurs with an ex ante probability of $\zeta\left(\mathbf{b};\theta\right)$. It is therefore easy to generate random draws from $\zeta\left(\mathbf{b};\theta\right)$ because the population distribution of $\mathbf{B}$ over $\mathbb{B}$ is induced by the one for the random utility shifters $\mathbf{U}$ (which are easy to simulate). Hence we have the equality

where the probability to the right can be computed by the accept/reject Monte Carlo (“dartboard”) simulation estimate

with $s=1, \dots, S$ indexing independent random draws $\mathbf{U}^{(s)}$ from $F_{\mathbf{U}}$. \\ \\ Unfortunately, in large games, it is generally the case that the event $\mathbf{y}$ is a NE at $\mathbf{U}$ occurs with very low probability. In large games the number of possible pure strategy combinations, the cardinality of the set $\mathbb{Y}$, is typically enormous (here $\mathbb{Y}$ is the set of all $2^{TM}$ possible game outcomes). The population probability of observing any particular game outcome or NE, $\mathbf{Y}=\mathbf{y}$, is therefore very small. Estimating small probabilities with a computationally manageable number of simulation draws, $S$, by accept/reject frequency methods is well-known to be infeasible (see, for example, Hajivassiliou_Ruud_HBE1994 or Au_Beck_PEM2001). \\ \\ As in other related contexts our solution to this conundrum involves importance sample. We begin with the observation that evaluating the likelihood of a given game outcome $\mathbf{Y}=\mathbf{y}$ only requires integration over scenarios in the set $\mathbb{B}_{\mathbf{y}}$ (i.e., scenarios where $\mathbf{Y}=\mathbf{y}$ is the selected NE). Those scenarios in the complement $\mathbb{B}\setminus\mathbb{B}_{\mathbf{y}}$ do not enter the likelihood calculation. Although enumeration of the set $\mathbb{B}_{\mathbf{y}}$ is infeasible in large games, we show how it is possible to sample randomly from it. \\ \\ Let $\lambda_{\mathbf{y}}\left(\mathbf{b};\theta\right)$ be a function which assigns probabilities to the scenarios contained in $\mathbb{B}_{\mathbf{y}}$. We will require that $\lambda_{\mathbf{y}}\left(\mathbf{b};\theta\right)$ be strictly greater than zero for any $\mathbf{b}\in\mathbb{B}_{\mathbf{y}}$ and exactly zero otherwise (i.e., for $\mathbf{b}\in\mathbb{B}\setminus\mathbb{B}_{\mathbf{y}})$. We also require that this function satisfy the adding up condition $\sum_{\mathbf{b}\in\mathbb{B}_{\mathbf{y}}}\lambda_{\mathbf{y}}\left(\mathbf{b};\theta\right)=1$. The function $\lambda_{\mathbf{y}}\left(\mathbf{b};\theta\right)$ is a pmf for those scenarios where $\mathbf{Y}=\mathbf{y}$ is the NE. Let $\tilde{\mathbf{B}}$ be a random scenario draw from the distribution with pmf $\lambda_{\mathbf{y}}\left(\mathbf{b};\theta\right)$. Later we show how to construct such a draw, but for now assume an appropriate method is in hand. Note that, by construction, $\Pr\left(\mathbf{\tilde{B}}\in\mathbb{B}_{\mathbf{y}}\right)=1$ and $\Pr\left(\mathbf{\tilde{B}}\in\mathbb{B}\setminus\mathbb{B}_{\mathbf{y}}\right)=0$. \\ \\ Let $\theta^{\left(0\right)}$ be some (fixed) value for the parameter; we have that

where $\tilde{\mathbf{B}}$ denotes a random draw from $\lambda_{\mathbf{y}}\left(\mathbf{b};\theta^{\left(0\right)}\right).$ We have written $\Pr\left(\left.\mathbf{Y}=\mathbf{y}\right|\mathbf{X};\theta\right)$ as an expectation over scenarios in $\mathbb{B}_{\mathbf{y}}$ (versus a summation over the much larger set $\mathbb{B})$. An importance sampling Monte Carlo estimate of this expectation is:

where $\tilde{\mathbf{B}}^{\left(1\right)} \dots \tilde{\mathbf{B}}^{\left(S\right)}$ are independent random draws from $\lambda_{\mathbf{y}}\left(\mathbf{b};\theta^{\left(0\right)}\right).$ \\ \\ This estimate, because the cardinality of $\mathbb{B}_{\mathbf{y}}$ is finite, is consistent as $S\rightarrow\infty$ (see below). More importantly, because all of the summands in (ref) are non-zero, this estimate has the potential to provide precise estimates of $\Pr\left(\left.\mathbf{Y}=\mathbf{y}\right|\mathbf{X};\theta\right)$ for modest values of $S$, particularly if the importance sampling weights, $\lambda_{\mathbf{y}}\left(\mathbf{b};\theta\right)$, are close to uniform. \\ \\ Operationalizing (ref) requires a method for sampling scenarios in $\mathbb{B}_{\mathbf{y}}$; such a method is the primary contribution of this paper. We first describe our approach in the context of the simple two player coordination game introduced in this section and generalize it to larger games in the sequel. Our approach is to draw $U_1$ and $U_2$ sequentially such that $\mathbf{U}=\left(U_1, U_2 \right)'$ is in a scenario in $\mathbb{B}_{\mathbf{y}}$ with probability one (i.e., $\mathbf{U} \in \tilde{\mathbf{B}},\,\, \tilde{\mathbf{B}} \in \mathbb{B}_{\mathbf{y}}$ w.p.1). \\ \\ Consider simulating the probability of the event that both Ademaro and Brunhilde go to the concert (i.e., that $\mathbf{Y}=\mathbf{y}=\tbinom{1}{1}$). For the purposes of illustration, we will first draw Brunhilde's preference shock, $U_2$, followed by Ademaro's, $U_1$. In order to construct a draw of $\mathbf{U}$ that falls into one of the three darker shaded regions of Figure (ref), it is necessary, albeit not sufficient, that $U_2 \leq X_{2}'\beta+\delta$. In the first step of our procedure we therefore draw $U_2$ from $F$ truncated at $X_{2}'\beta+\delta$. \\ \\ Next we draw Ademaro's preference shock, $U_1$. Our approach to doing so depends on the realized value of Brunhilde's shock, $U_2$. If Brunhilde's shock falls between $X_{2}'\beta$ and $X_{2}'\beta+\delta$, then she is “on the fence". It will only be a NE for her to go if Ademaro does as well. This means that Ademaro's shock must fall below $X_{1}'\beta$, such that it is strictly dominant for him to go. So in this case we draw $U_1$ from $F$ truncated at $X_{1}'\beta$. This generates $\left(U_1, U_2 \right)' \in \mathbf{b_{12}}$. \\ \\ Alternatively, consider the case where Brunhilde's step one shock was sufficiently low such that it is strictly dominant for her to go to the concert; that is $U_2 \leq X_{2}'\beta$. In this case we are free to draw Ademaro's shock from the larger interval $U_1 \leq X_{1}'\beta+\delta$. If $X_{1}'\beta \leq U_1 \leq X_{1}'\beta+\delta$, then Ademaro is “on the fence", but since Brunhilde is going no matter what, they both will go. We have $\left(U_1, U_2 \right)' \in \mathbf{b_{21}}$. If, instead, $U_1 \leq X_{1}'\beta$, then we have $\left(U_1, U_2 \right)' \in \mathbf{b_{11}}$ and they both go in that case as well. \\ \\ Note that finding the appropriate region of support for Ademaro's shock involves the following “counterfactual" thought experiment. In step 1 we simulate Brunhilde's shock under the presumption that, in the end, Ademaro will also go to the concert (we are computing the probability that they both go). In step 2, after drawing Brunhilde's shock, $U_2$, we ask ourselves what her play would be if Ademaro's taste shock instead was high enough such that it would be strictly dominant for him not to go to the concert. Since the game is supermodular, Ademaro not going (weakly) discourages Brunhilde from attending. We compute the NE associated with this “counterfactual" scenario and use it to find the appropriate upper threshold for Ademaro's shock. If Brunhilde is sensitive to Ademaro's choice (i.e., she is “on the fence" or $U_2$ is in her middle bucket), then we force Ademaro's shock to be lower. If Brunhilde is insensitive to Ademaro's choice (i.e., it is strictly dominant for her to go or $U_2$ is in her first bucket), then we can allow Ademaro's shock to range higher. \\ \\ The above procedure ensures that $\left(U_1, U_2 \right)'$ falls in a scenario in $\mathbb{B}_{\mathbf{y}}$ with probability one. It also reaches every scenario in this set with positive probability. Formalizing the calculations above yields the (importance) sampling probabilities

It is a simple exercise to verify that:

and hence that we have defined a proper probability distribution that places positive weight on all scenarios in $\mathbb{B}_{\mathbf{y}}$. In contrast the unconditional population frequencies of these three scenarios are (when $\theta_0=\theta$):

It is helpful for understanding what follows to observe that the scenario sampling probabilities are inverse probability weighted versions of their population counterparts:

Observing that $\hat{\lambda}_{\mathbf{y}}\left(b;\theta^{\left(0\right)}\right) = \frac{1}{S}\sum_{s=1}^{S}\mathbf{1}\left(\tilde{\mathbf{B}}^{\left(s\right)}=\mathbf{b}\right)$ consistently estimates $\lambda_{\mathbf{y}}\left(\mathbf{b};\theta^{\left(0\right)}\right)$ allows us to express our importance sampling likelihood estimate as

which indicates that likelihood estimate is unbiased for any fixed $S$ and consistent as $S\rightarrow\infty$ as long as $\lambda_{\mathbf{y}}\left(\mathbf{b};\theta^{\left(0\right)}\right)>0$ for all $\mathbf{b} \in \mathbb{B}_\mathbf{y}$. While $\hat{\Pr}\left(\left.\mathbf{Y}=\mathbf{y}\right|\mathbf{X};\theta\right)$ converges in mean square to $\Pr\left(\left.\mathbf{Y}=\mathbf{y}\right|\mathbf{X};\theta\right)$ at rate $\frac{1}{S}$, accuracy in actual applications will depend on the cardinality of $\mathbb{B}_{\mathbf{y}}$ as well as the features of $\lambda_{\mathbf{y}}\left(\mathbf{b};\theta^{\left(0\right)}\right)$ and $\zeta\left(\mathbf{b};\theta\right)$.

Simulated maximum likelihood (SML) estimation

Let $(\mathbf{X}_{1},\mathbf{Y}_{1}),\ldots,(\mathbf{X}_{N},\mathbf{Y}_{N})$ be a random sample of games. The simulated log likelihood equals:

with each of the summands in (ref) constructed via simulation as described above. When the researcher has access to a large number of independent games (such that the summands in (ref) are independent of one another), it is straightforward to characterize the large sample properties of our SML estimator. Under regularity conditions it will be consistent and asymptotically normal as $N\rightarrow\infty,\ S\rightarrow\infty$. See Hajivassiliou_Ruud_HBE1994. \\ \\ We detail additional features of our SML estimator below, but point out now that one advantage (besides the critical one of feasibility!) of importance sampling versus crude frequency simulation is that our criterion function is differentiable. This means that maximization of (ref) by gradient-based methods is possible; in turn allowing the dimension of $\theta$ to be large. The Hessian can also be computed numerically, making inference -- when valid -- straightforward. \\ \\

Peer effect games

In this section we extend our simple coordination game analysis to $T$-player single-action peer effect and technology adoption games. In these games the payoff from taking action is weakly-increasing in the number of people in an agent's reference, or peer, group who take action Manski_ReStud93. This is an important class of games. Manski_ReStud93, Brock_Durlauf_HBE01 and Bramoulle_et_al_JOE09 study the econometrics of these games when actions are continuous and agents' best response functions are linear (see Bramoulle_et_al_AR2020 for a survey). The binary-action case is less well understood, but see Krauth_JOE2006 and Soetevent_Kooreman_JAE07 for important analyses. In Section (ref) we show how to extend our analysis to a class of $T$-player, $M$-binary-action supermodular games. \\ \\

Likelihood

Consider a simple binary-action peer effects game. There are $T$ agents, each of who decide whether to take an action, $Y_{t}=1$, or not, $Y_{t}=0$. Agents are connected via a set of undirected relationships. Let $\mathbf{G}$ be the $T\times T$ row-normalized adjacency matrix recording this link structure. Let $\mathbf{G}_{t}$ denote the $t^{th}$ row of this matrix such that $\mathbf{G}_{t}\mathbf{y}$ equals the mean action of agent $t$'s peers. The payoff from action for agent $t$ is

This set-up approximates many peer effects and technology adoption games. We assume that $\delta\geq0$, so that peer action weakly encourages own action. \\ \\ The set of pure strategy NE in this game correspond to the solutions of the system of $T$ nonlinear equations

This system may have multiple solutions. In this paper we will assume that the minimal equilibrium, the one with the fewest agents taking action, is the one that prevails. This equilibrium can be found by substituting the zero vector $\mathbf{Y}=\underline{0}_{T}$ into the right-hand-side of (ref) and iterating to a fixed point. By Tarski's Fixed Point Theorem this iterative process stops at the minimal equilibrium Milgrom_Roberts_EM1990. \\ \\ This equilibrium selection assumption may not be plausible in some applications, it is perhaps most natural for “opt in” games. For example in adolescent peer effects and technology adoption games it is common for agents to start in the non-action state and then choose whether to act/adopt. Our results are easily modified to accommodate applications where the equilibrium with the most action is the one chosen (the so-called maximal equilibrium). The maximal equilibrium can be found by fixed point iteration starting at $\mathbf{Y}=\underline{1}_{T}$ (i.e., at the one vector). This equilibrium selection assumption might be appropriate for “opt out” games. \\ \\ As in the two-player coordination game described above, we can use the systematic component of agents' utility functions (ref) to partition the support of $U_t$ into buckets. If player $t$ has $J_t$ friends (corresponding to the number of non-zero elements in the $t^{th}$ row of the row-normalized adjacency matrix, $\mathbf{G})$, then her bucket partition will be

The number of buckets partitioning the support of $U_{t}$ equals the cardinality of the set $\left\{ s_{t}\left(\mathbf{y}_{-t}\right):\mathbf{y}_{-t}\in\left\{ 0,1\right\} ^T\right\}$ plus $1$ where $s_{t}\left(\mathbf{y}_{-t}\right)=\mathbf{G}_{t}\mathbf{Y}$. In this example we have $L_{t}=J_{t}+1$ for a total of $L_{t}+1=J_{t}+2$ buckets. If $U_t$ falls in the first bucket, then it is strictly dominant for player $t$ to take action regardless of what her peers do. If it falls in the second bucket, it is optimal to take action if at least one out of her $J_t$ peers do and so on. The buckets define ranges of realized values of $U_t$ where it is optimal to take action given that different numbers of peers also take action (the right-most bucket defines the set of $U_t$ realizations where it optimal to not take action across all possible levels of peer action). \\ \\ Scenarios in this game correspond to $T$-dimensional hyper-cubes in $\mathbb{R}^T$. Consider the scenario where all of the $U_t$ taste shocks fall into their second buckets. In this scenario it is optimal for all players to take action if at least one of their peers do. \\ \\ Associated with a scenario, $\mathbf{b}$, is a set of $T$ upper and lower bucket boundaries. We will denote the bucket boundaries in scenario $\mathbf{b}$ for agent $t$ by $\bar{b}_{t}$ and $\underline{b}_{t}$.\footnote{Note that $\underline{b}_{t} = -\infty$ if agent $t$'s bucket in scenario $\mathbf{b}$ is the first (left-most) one and $\bar{b}_{t}=\infty$ if it is the last (right-most) one.} Using this notation we can write the ex ante probability that $\mathbf{U}=(U_1,U_2,\ldots,U_T)'$ falls into scenario $\mathbf{b}$ as

We have suppressed the dependence of the bucket boundaries on $X_t$ and $\theta$ in the notation. \\ \\ To construct an estimate of the likelihood of the event $\mathbf{Y}=\mathbf{y}$ we, in addition to the expression for $\zeta\left(\mathbf{b};\theta\right)$ given above, require a method for randomly drawing a scenario, say $\tilde{\mathbf{B}}$, from the set $\mathbb{B}_{\mathbf{y}}$ with an ex ante probability, $\lambda_{\mathbf{y}}\left(\mathbf{b};\theta^{\left(0\right)}\right)$, that is computable. With these ingredients, we can estimate the likelihood -- as noted earlier -- by the simulated analog of the expectation:

See (ref) above. We randomly draw the scenario $\tilde{\mathbf{B}}$ by sequentially drawing the random preference shocks $U_1,U_2,\ldots,U_T$ such that, in the end, $\mathbf{U} \in \tilde{\mathbf{B}}$ and $\tilde{\mathbf{B}} \in \mathbb{B}_{\mathbf{y}}$ with probability one. \\ \\

Scenario Sampling

In this section we describe a procedure for constructing a random draw, $\tilde{\mathbf{B}}$, from the set $\mathbb{B}_{\mathbf{y}}$. We use the notation $\tilde{\mathbf{B}}$ to emphasize that this draw is not from the population distribution of scenarios, with support, $\mathbb{B}$ and pmf $\zeta\left(\mathbf{b};\theta\right)$, but instead drawn from a distribution with support on the smaller set $\mathbb{B}_{\mathbf{y}}$. Indeed, the cardinality of $\mathbb{B}_{\mathbf{y}}$ will typically be much smaller than that of $\mathbb{B}$. \\ \\ Recall that the population distribution of scenarios is induced by the population distribution of the random utility shocks $\mathbf{U}=\left(U_1,U_2, \ldots U_T \right)'$ (as well as the structure of preferences). We similarly sample scenarios from $\mathbb{B}_{\mathbf{y}}$ by constructing draws of the random utility shocks, $\mathbf{U}$. The innovation is to do this in a way such that $\mathbf{U} \in \tilde{\mathbf{B}}$ and $\tilde{\mathbf{B}} \in \mathbb{B}_{\mathbf{y}}$ with probability one. \\ \\ Key to our approach is the drawing of the taste shocks sequentially instead of independently. Specifically we allow the region from which $U_{t}$ is drawn from to depend on the realizations of earlier draws, $U_s$ in the sequence (where $s<t$). By carefully taking into account the constraints imposed by the target pure strategy combination $\mathbf{y}$ and the definition of a NE, we can ensure that the final sequence of draws $\mathbf{U}$ fulfills $\mathbf{U} \in \tilde{\mathbf{B}}$ and $\tilde{\mathbf{B}} \in \mathbb{B}_{\mathbf{y}}$ with probability one. \\ \\ The goal is to construct a draw of $\mathbf{U}=\left(U_1,U_2, \ldots U_T \right)'$ such that, at the current parameter value $\theta$, the selected NE is $\mathbf{y}$. Associated with such a draw is a scenario $\tilde{\mathbf{B}} \in \mathbb{B}_{\mathbf{y}}$ which can be used to simulate the likelihood function using equation (ref) above. \\ \\ Let $\mathbf{y}$ denote the NE for which we wish to compute the likelihood $\Pr\left(\left.\mathbf{Y}=\mathbf{y}\right|\mathbf{X};\theta\right)$. Without loss of generality we will assume that the first $T-s$ agents do not take the action (i.e., that $y_t=0$ for $t=1,\dots,T-s$) while the last $s$ agents do take the action (i.e., that $y_t=1$ for $t=T-s+1,\dots,T$). \\ \\ We will first draw random utility shocks for the $T-s$ agents who do not take action in NE $\mathbf{y}$. For these agents it must be the case that their utility shock $U_t$ is high enough such that it optimal for them not to take action given the play of others $\mathbf{y}_{-t}$. From (ref) we have that it must be the case that, for $t=1,\ldots,T-s$,

or, equivalently, that $U_{t}\in\left(X_{t}'\beta+\mathbf{G}_{t}\mathbf{y}\delta,\infty\right)$ for $t=1,\ldots,T-s$. Shocks of this magnitude are high enough to ensure that these agents' do not wish to take action, which would be a deviation from their behavior in NE $\mathbf{y}$. See (ref) above. \\ \\ We next consider agents the $s$ who do take action in the target equilibrium, $\mathbf{y}$. Finding the appropriate range restrictions for $U_t$ for the $y_t=1$ agents is more challenging. Since $\mathbf{G}_{t}\mathbf{y}\delta \geq 0$ (by supermodularity), it must be the case that, if $U_t \in\left(-\infty,x_{t}'\beta \right]$ for $t=T-s+ 1,\ldots,T$, then it will be optimal for these agents to choose $y_t=1$ (as desired). Indeed, draws this low ensure that it will be strictly dominant for these agents to take the action. However it is also possible that higher draws of $U_t$ are sufficiently low enough to ensure that these agents will still choose $y_t=1$. \\ \\ An example helps clarify the issues involved. Consider a setting where $\mathbf{G}$ corresponds to a complete graph (i.e., everyone is connected to everyone else in the group as in the canonical “linear-in-means" model studied by Manski_ReStud93, Bramoulle_et_al_JOE09 and others). Our goal continues to be the construction of a $\mathbf{U}=\left(U_1,U_2, \ldots U_T \right)'$ sequence where $\mathbf{Y}=\mathbf{y}$ is the NE. We again begin by drawing the $T-s$ preference shocks for the $y_t=0$ agents from the interval $U_{t}\in\left(X_{t}'\beta+\frac{s\delta}{T-1},\infty\right)$. This range restriction is sufficient to ensure that these $T-s$ agents will not want to deviate from $\mathbf{y}$. \\ \\ Next we need to draw utility shocks for the $s$ agents who we do want to take action. Assume, for the purposes of exposition, that the first $s-1$ of these draws, $U_{T-s+1}, \ldots , U_{T-1}$, are so low that it is strictly dominant for these players to choose $y_t=1$. In this case, for the $s^{th}$ action-taking agent, we only require a random utility shock lower than $X_{t}'\beta+\frac{(s-1)\delta}{T-1}$. For this last shock we can draw $U_{T}\in\left(-\infty,X_{t}'\beta+\frac{(s-1)\delta}{T-1}\right)$. \\ \\ We now consider a slight variation of this example: we assume that the only first $s-2$ draws for the action-taking agents, $U_{T-s+1}, \ldots , U_{T-2}$, are low enough for it to be strictly dominant for them to choose $y_t=1$. Next consider the appropriate range constraint for the $(s-1)^{th}$ action-taking agent's random utility draw. \\ \\ In taking this draw we know that the previous $s-2$ agents will take the action for sure, we will also proceed as if the draw for the $s^{th}$ agent will be low enough for her to want to choose $y_t=1$ as well. In this case any draw of $U_{t}\in\left(-\infty,X_{t}'\beta+\frac{(s-1)\delta}{T-1}\right)$ will suffice for the $(s-1)^{th}$ action-taking agent to choose $y_t=1$ as desired. Say our draw of $U_t$ for agent $t=T-1$ (the $(s-1)^{th}$ agent choosing $y_t=1$) is relatively high, specifically in the interval $\left(X_{t}'\beta+\frac{(s-2)\delta}{T-1},X_{t}'\beta+\frac{(s-1)\delta}{T-1}\right).$ \\ \\ In this situation the appropriate way to draw $U_t$ for agent $T$, the $s^{th}$ and final action-taking agent, is delicate. Say we draw $U_t \in \left(X_{t}'\beta+\frac{(s-2)\delta}{T-1},X_{t}'\beta+\frac{(s-1)\delta}{T-1}\right).$ In this case both agents $T-1$ and $T$ would be willing to choose $y_t=1$ as long as the other did, but they won't choose $y_t=1$ if the other chooses $y_t=0$. Since we assume that the NE with the least amount of action prevails in the presence of multiplicity, such a draw would not result in a scenario in our target set of $\mathbb{B}_{\mathbf{y}}$. \\ \\ To stay on track we require that $U_T$ lies below $X_{T}'\beta+\frac{(s-2)\delta}{T-1}$. In this case agent $T$ will take the action (because $s-2$ agents will choose $y_t=1$ for sure). Since agent $T$ takes the action, it will also be optimal for agent $T-1$, who had a somewhat higher random utility draw, to do so as well. This agent is on the fence, but since $T$ chooses $y_t=1$ she does so as well. We thus have $\mathbf{U} \in \tilde{\mathbf{B}}$ and $\tilde{\mathbf{B}} \in \mathbb{B}_{\mathbf{y}}$ as needed. \\ \\ In general there will be an agent specific threshold, $h_t$, between $X_{t}'\beta$ and $X_{t}'\beta+\mathbf{G}_{t}\mathbf{y}\delta$ that will be sufficient to keep our algorithm on track. The theshold $h_t$ is such that if $U_{t} \leq h_t $, then it is possible to construct subsequent draws $U_{t+1}, \ldots , U_T$, such that, in the end, $\mathbf{U} \in \tilde{\mathbf{B}}$ and $\tilde{\mathbf{B}} \in \mathbb{B}_{\mathbf{y}}$, as desired. If however $U_{t}>h_t$, then this will not be possible. Algorithm (ref) shows how to find this threshold. Given these thresholds it is relatively straightforward to sample $\tilde{\mathbf{B}} \in \mathbb{B}_{\mathbf{y}}$. \\

\\ Algorithm (ref) details how $U_{1} ,\ldots,U_{T}$ are sequentially drawn from a series of truncated distributions. Let $\mathbf{U} $ denote a draw produced by Algorithm (ref). The (ex ante) population probability of the event $\mathbf{U} \in\mathbf{b}$ (for $\mathbf{b} \in \mathbb{B}_{\mathbf{y}}$) is

where the weights $\omega_{t}$ are as given in the statement of Algorithm (ref) and $\bar{b}_{t}$ and $\underline{b}_{t}$ are the bucket boundaries for agent $t$ defined earlier. Note that $\lambda_{\mathbf{y}}\left(\mathbf{b};\theta\right)$ is a “re-weighted" version of $\zeta\left(\mathbf{b};\theta\right)$. We also have that $\lambda_{\mathbf{y}}\left(\mathbf{b};\theta\right)=0$ for all $\mathbf{b}\in\mathbb{B}\setminus\mathbb{B}_{\mathbf{y}}$. \\

\\ A key step of Algorithm (ref) is its calling of our Threshold Finder (i.e., Algorithm (ref)). By construction the Threshold Finder is first called after all draws of $U_{t} $ for $y_{t}=0$ agents have already been made (see Step 2 of Algorithm (ref)). Hence, at the start of each call of Algorithm (ref), $\mathbf{U} $ consists of draws of $U_{t}$ for all $y_{t}=0$ cases, those draws of $U_{t}$ for the $y_{t}=1$ cases for which the thresholds $h_{t}$ have already been determined, and the initialization values for any remaining elements. \\ \\ Let $t$ index the player for which $h_{t} $ is currently being determined and $t'$ other players. In Step 1.a.ii. of the Threshold Finder we provisionally set the random taste shock for all $t'$ where $y_{t'}=1$ and $h_{t'}$ has not yet been determined, such that in the minimal equilibrium computed in Step 3 we will have $\tilde{y}_{t'}=1$ with probability one. For all other players, except the current one, the relevant random taste shocks have already been chosen. \\ \\ In Step 2 of Algorithm (ref) we then (provisionally) set the current player's random utility draw, $\tilde{U}_{t}$, to a level such that the strictly dominant strategy will be for player $t$ to not to take action \emph{even when all other player actions are as specified in the target NE $\mathbf{y}$}. In the target NE $\mathbf{y}$ we have $y_{t}=1$ (Algorithm (ref) is only called in such cases), but here we wish to induce a different NE $\tilde{\mathbf{Y}}\preceq\mathbf{y}$ with $\tilde{Y}_{t}=0$. By forcing player $t$ to \emph{not} take action it may be that we also induce some other players whose thresholds $h_{t'}$ have already been chosen to also \emph{not} take the action as well, such that $\tilde{Y}_{t'}=0$ (even though $y_{t'}=1$ in the target NE). This provides useful information since it helps us understand how important player $t$'s decision to take the action is for sustaining the target NE. \\ \\ Observe that, by monotonicity of the utility function of the underlying game we have that $\tilde{\mathbf{Y}}\preceq\mathbf{y}$: the equilibrium simulated in Algorithm (ref) is less dense than the target one. In Step 3 of Algorithm (ref) we set $h_{t} =X_{t}'\beta+\mathbf{G}_{t}\tilde{\mathbf{Y}}\delta$. This is exactly the threshold we need. We know that if $U_{t} \leq h_{t} $ it (i) will be optimal for player $t$ to take action given the actions of her peers, $\tilde{\mathbf{Y}}_{-t}$, in the sparser equilibrium and (ii) because player $t$ will take the action, no other players will want to deviate from the target NE, $\mathbf{y}$ to $\tilde{\mathbf{Y}}$. Hence agents will choose $\mathbf{y}$ as desired. However if $U_{t} > h_{t}$, player $t$ will choose not to take the action and other players will also not take further actions beyond $\tilde{\mathbf{Y}}$. For such a draw of $\mathbf{U}$, $\mathbf{y}$ will not be the NE. \\ \\ These observations are formalized in the following Theorem.

A key feature of Theorem (ref) is the guarantee not just that $\mathbf{U} \in\mathbf{b}$ with $\mathbf{b}\in\mathbb{B}_{\mathbf{y}}$, but that all scenarios in $\mathbb{B}_{\mathbf{y}}$ are visited with positive probability. Theorem (ref) is sufficient for consistency of (ref) for the true likelihood as $S\rightarrow\infty$.

The coordination game

In this section we formally walk through our scenario sampling algorithm using the simple two-player coordination game introduced in the previous section. Our goal is to construct a simulation estimate of the ex ante probability that $\mathbf{Y}= {1 \choose 1}$ for a given $\theta$. There are three scenarios which lead to the observed outcome; these are the darker shaded lower left-hand-side rectangles in Figure (ref). We now illustrate how the Scenario Sampler, Algorithm (ref), samples each of them with positive probability. For the purposes of illustration, and to contrast with our informal analysis in the prior section, will will draw Ademaro's preference shock $U_1$ first, followed by Brunhilde's, $U_2$. \\ \\ Sampling scenario $\mathbf{b}_{11}$: Strictly dominant for both Ademaro and Brunhilde to attend \\ \\ Step 1 is initialization. Step 2 is not relevant for the $\mathbf{Y}= {1 \choose 1}$ NE. \\ \\ In the first execution of Step 3, the Threshold Finder proceeds under the presumption that in the end Brunhilde will want to choose $Y_2=1$ (see Step 1, (b) ii. in Threshold Finder). It therefore finds a threshold for Ademaro of $h_1 = X_{1}'\beta^{\left(0\right)}+\delta^{\left(0\right)}$. The Scenario Sampler consequently draws $U_1$ from $\left(-\infty, {h}_{1} \right]$ (see Step 3, (a) ii. in Scenario Sampler). In order eventually land in $\mathbf{b}_{11}$, it must be the case that our $U_1$ draw is lower then $X_{1}'\beta^{\left(0\right)}$. \\ \\ In the second execution of Step 3, the \textsc{Threshold Finder} knows that Ademaro will choose $y_t=1$ (Step 1, (b) i. in \textsc{Threshold Finder}) and therefore finds a threshold of $h_2 = X_{2}'\beta^{\left(0\right)}+\delta^{\left(0\right)}$ for Brunhilde. The $U_2$ is drawn from $\left(-\infty,{h}_{2} \right]$. In order to land in $\mathbf{b}_{11}$ it must be the case that this draw is below $X_{2}'\beta^{\left(0\right)}$. \\ \\ By using the truncated probability distributions given in the statement of the algorithm, we find that $\mathbf{b}_{11}$ is drawn with an ex ante probability $\lambda_{\mathbf{y}}\left(\mathbf{b}_{21};\theta^{\left(0\right)}\right) = \frac{F\left(X_{1}'\beta^{\left(0\right)}\right)}{F\left(X_{1}'\beta^{\left(0\right)}+\delta^{\left(0\right)}\right)}\left[\frac{F\left(X_{2}'\beta^{\left(0\right)}\right)}{F\left(X_{2}'\beta^{\left(0\right)}+\delta^{\left(0\right)}\right)}\right].$\\ \\ \textbf{Sampling scenario $\mathbf{b}_{21}$: Ademaro is “on the fence"} \\ \\ Step 1 is initialization. Step 2 is not relevant for the $\mathbf{Y}= {1 \choose 1}$ NE. \\ \\ In the first execution of Step 3, the \textsc{Threshold Finder} again proceeds under the presumption that in the end Brunhilde will want to choose $Y_2=1$ (see Step 1, (b) ii. in \textsc{Threshold Finder}). It therefore again finds a threshold for Ademaro of $h_1 = X_{1}'\beta^{\left(0\right)}+\delta^{\left(0\right)}$. As above, the \textsc{Scenario Sampler} draws $U_1$ from $\left(-\infty, {h}_{1} \right]$ (see Step 3, (a) ii. in \textsc{Scenario Sampler}). However in this instance we want to end up in scenario $\mathbf{b}_{21}$. Therefore it must be the case that our $U_1$ draw is in the interval $\left(X_{1}'\beta^{\left(0\right)},X_{1}'\beta^{\left(0\right)}+\delta^{\left(0\right)} \right)$. \\ \\ In the second execution of Step 3, the \textsc{Threshold finder} knows that \textit{Ademaro will only want to take the action if Brunhilde takes the action} (Step 1, (b) i. in \textsc{Threshold Finder}). Therefore it finds a lower threshold for Brunhilde of $h_2 = X_{2}'\beta^{\left(0\right)}$. The $U_2$ preference shock is drawn from $\left(-\infty,{h}_{2} \right]$. In order to land in $\mathbf{b}_{21}$ it must be the case that this draw is lower than $X_{2}'\beta^{\left(0\right)}$ (which it is by construction). \\ \\ $\mathbf{b}_{21}$ is drawn with an ex ante probability of $\lambda_{\mathbf{y}}\left(\mathbf{b}_{21};\theta^{\left(0\right)}\right) = \frac{F\left(X_{1}'\beta^{\left(0\right)}+\delta^{\left(0\right)}\right)-F\left(X_{1}'\beta^{\left(0\right)}\right)}{F\left(X_{1}'\beta^{\left(0\right)}+\delta^{\left(0\right)}\right)}.$ \\ \\ \textbf{Sampling scenario $\mathbf{b}_{12}$: Brunhilde is “on the fence"} \\ \\ This scenario is similar to the $\mathbf{b}_{11}$ scenario. It differs only in terms of the realized draw of $U_2$. The ex ante probability of drawing this scenario is $\lambda_{\mathbf{y}}\left(\mathbf{b}_{12};\theta^{\left(0\right)}\right) = \frac{F\left(X_{1}'\beta^{\left(0\right)}\right)}{F\left(X_{1}'\beta^{\left(0\right)}+\delta^{\left(0\right)}\right)}\left[\frac{F\left(X_{2}'\beta^{\left(0\right)}+\delta^{\left(0\right)}\right)-F\left(X_{2}'\beta^{\left(0\right)}\right)}{F\left(X_{2}'\beta^{\left(0\right)}+\delta^{\left(0\right)}\right)}\right]$. \\ \\ Observe how in all three cases, the \textsc{Threshold Finder} finds the appropriate threshold for Brunhilde by using information contained in Ademaro's $U_1$ draw. Specifically the algorithm determines whether Ademaro is sensitive to Brunhilde's play, if he is it chooses a lower threshold for Brunhilde' shock to ensure that, in the end, both of them will want to go to the concert. \\ \\ In the example above we construct $\mathbf{U} \in\mathbf{b}$ with $\mathbf{b}\in\mathbb{B}_{\mathbf{y}}$ by drawing Ademaro's preference shock first, followed by Brunhilde's. In our discussion of the same example in the prior section we reversed this order. By comparing the scenario probabilities above with those calculated earlier (see Equation (ref)) we can see that the order in which we draw the shocks for the $y_t=1$ agents matters. \\ \\ We speculate that there is an optimal ordering of the $y_t=1$ agents. That is an ordering which will result in importance sample weights that estimate the likelihood with the smallest amount of simulation error for a fixed number of simulation draws. Our conjecture is that the optimal ordering involves a sorting of agents by the linear indices $X_{t}'\beta^{\left(0\right)}$. We leave a complete analysis of this question to future work.

Technical comments

In this section we briefly discuss a few additional feature of our algorithm. Additional details are provided in the appendices. \\ \\ Section (ref) below introduces a class of binary-action, complete information, supermodular games to which an extended version of our scenario sampler can be applied. In these games $T$ players each take $M$ binary actions. For most games in this class the number of scenarios grows exponentially with $TM$. At the same time the probability of observing any particular NE generally shrinks exponentially. This makes explicit enumeration of scenarios, required for “direct" MLE, infeasible. This feature of our problem also makes crude frequency-based -- “dartboard" -- Monte Carlo methods completely impractical outside of toy examples. \\ \\ In contrast, our approach allows a researcher to randomly sample a scenario from the target set $\mathbb{B}_{\mathbf{y}}$ in polynomial time. This is the main reason why our approach makes SML estimation of games with several thousands strategic decision possible. However there are a few other properties of our procedure which make scenario-based estimation even more applicable to larger games. \\ \\ Differentiability \\ An advantage of importance sampling, relative to crude frequency-based Monte Carlo, is that the former results in a criterion function that is differentiable in $\theta$, while the latter does not (see McFadden_EM89, Ackerberg_QME2009. Inspection of Equation (ref) reveals that is locally differentiable in $\theta$. The details of this claim are spelled out in Appendix (ref). \\ \\ When agents' preferences are indexed by many parameters, it is very helpful to have the derivative of the log-likelihood function with respect to $\theta$ available. Non-gradient based optimization approaches do not scale well to high-dimensional settings. In our empirical illustration we fit a network formation model with over $200$ parameters by SML, quasi-Newton assisted, estimation (the model includes household-specific degree heterogeneity parameters as in Graham_EM17, Graham_HBE2020). Fitting a model of this size would not be practical without gradient-based optimization methods. \\ \\ Scenario Recycling \\ Maximizing the log-likelihood requires it to be evaluated at many different values of $\theta$. The most expensive component of log-likelihood evaluation involves computation of the Nash Equilibrium (NE). This observation applies not just to our scenario-based approach, but to other likelihood-based methods of game estimation Bajari_et_al_EM10. In Appendix (ref) we outline a procedure, “scenario recycling", which economizes on repeated NE calculations. Our procedure is related to the methods of Ackerberg_QME2009 as applied to games by Bajari_et_al_EM10. As with these approaches, scenario recycling works only if there is exactly one strategic parameter to estimate. This applies to the peer effect example of this section and the network formation example we develop empirically. \\ \\ Independence\\ In many applications a researcher will observe the NEs of several, independent, games. For example a researcher may observe the smoking behavior of adolescents across many different secondary schools. Such applications have a number of computational and statistical advantages. \\ \\ In these applications the sample log likelihood is the sum of the log-likelihoods associated with each observed game. These log-likelihood components can be estimated separately via their own simulated scenario samples and then aggregated. \\ \\ Independence across games also allows for the application of textbook SML large sample theory Newey_McFadden_HBE94, Hajivassiliou_Ruud_HBE1994. Our approach can also be used to analyze a single large game, but such applications raise novel statistical issues which we do not address here. Some additional discussion on this point is provided when we discuss our empirical illustration.

Supermodular games

In this section show how to adapt Algorithm's (ref) and (ref) to a broader class of binary-action supermodular games. In this class of games each of $T$-players decides whether to take, or not to take, each of $M$ (non mutually exclusive) binary actions. In the peer effects game analyzed in the previous section $M=1$; but in many games agents may make multiple strategic decisions. In a game of directed network formation, for example, each player decides whether to direct a link (or not) to each of the $T-1$ other players in the network (such that $M=T-1$). \\ \\ In order to present positive results, we need to restrict the structure of payoffs to ensure that the resulting game is supermodular. Let $Y_{tm}\in\left\{ 0,1\right\} $ denotes the $m^{th}$ action of player $t$. Denote agent $t$'s full $M \times 1$ action vector by $\mathbf{Y}_t=\left(Y_{t1},\ldots,Y_{tM}\right)'$. Let $\mathbf{Y}_{t,-m}=\left(Y_{t1},\ldots,Y_{tm-1},Y_{tm+1},\ldots,Y_{tM}\right)'$ denote player $t$'s $M-1$ actions other than $Y_{tm}.$ Similarly let $\mathbf{Y}_{-t}=\left(\mathbf{Y}_{1}',\ldots,\mathbf{Y}_{t-1}',\mathbf{Y}_{t+1}',\ldots,\mathbf{Y}_{T}'\right)'$ be the $\left(T-1\right)M\times1$ vector of actions taken by agents other than $t$, henceforth called her peers. Let $\mathbf{U}$ and $\mathbf{X}$ be matrices consisting of all taste shocks and covariates. A player's realized utility depends on their own actions, $\mathbf{y}_{t} \in \mathbb{Y}_t \overset{def}{\equiv} \{0,1\}^{M},$ as well as the actions of their peers, $\mathbf{y}_{-t}$. For pure strategy profile $\mathbf{y}\in \mathbb{Y} \overset{def}{\equiv} \{0,1\}^{TM}$ the utility function of player $t$, $\upsilon_{t}: \mathbb{Y} \rightarrow\mathbb{R}$ is

with $\theta=\left(\beta_{1}',\delta_{1}',\ldots,\beta_{M}',\delta_{M}'\right)'$ and where $s_{m}\left(\mathbf{y}_{t,-m},\mathbf{y}_{-t}\right)$ is a given vector-valued function of own actions (other than the $m^{th}$ one) and peers' actions. This function may vary with $m=1,\ldots,M$. It could also depend on exogenous agent-by-action covariates, but we suppress this in the notation. The setup also allows for player-by-action specific covariates, $X_{tm}$, to influence payoffs. Players choose actions to maximize their utility given the actions of their peers under complete information (i.e., agents best respond). \\ \\ The effect of an increase in $U_{tm}$ is to decrease player $t$'s marginal benefit of taking action $m$; it can be thought of as a distaste or cost-of-action shock. This term generates unobserved agent-specific heterogeneity in the marginal utilities attached to taking the $M$ actions. This $M$-vector endows our model with the classic random utility structure pioneered by McFadden_FinE74. We assume that the elements of $\mathbf{U}_{t}=\left(U_{t1},\ldots,U_{tM}\right)'$ are independently and identically distributed (iid) with known cumulative distribution function (CDF) $F\left(\cdot\right)$ and probability density function (PDF) $f\left(\cdot\right)$. Independence is also maintained across agents and games (the $t$ and $i$ subscripts). We briefly discuss different distributional and dependence assumptions on $\mathbf{U}_{t}$ in the conclusion. \\ \\ The $s_{m}\left(\mathbf{y}_{t,-m},\mathbf{y}_{-t}\right)$ term allows for player $t$'s marginal utility from action $m$ to depend on what other actions she chooses to take. For example the payoff from smoking may vary with whether she also decides to drink. This term also captures how the choices of other players in the game alter the utility player $t$ attaches to action $m$; so called endogenous effects in the parlance of Manski_ReStud93.\footnote{Exogenous or contextual effects can be added to ((ref)) simply by defining $x_{tm}$ to include, for example, averages of the attributes of other players in game $i$. Here our focus is on the implications of strategic interaction for estimation and inference, consequently we abstract from exogenous effects. } \\ \\ To ensure the resulting game is supermodular, we require that $s_{m}\left(\mathbf{y}_{t,-m},\mathbf{y}_{-t}\right)$ is monotone increasing in both its arguments and that $\delta_{m} \geq 0$. This restriction ensures that (i) own actions are (weak) complements with one another and that (ii) own and peer actions are weakly complementary as well. \\ \\ The first claim follows from the restrictions that (i) the elements of $s_{m}\left(\mathbf{y}_{t,-m},\mathbf{y}_{-t}\right)$ are weakly increasing in $\mathbf{y}_{t,-m}$ and that (ii) the elements of $\delta_{m}$ are non-negative for $m=1,\ldots,M$. Observe that $\left(\mathbb{Y}_{t},\succeq\right)$ is a complete lattice and, further, that for all $\mathbf{y}_{t},\mathbf{y}_{t}'\in\mathbb{Y}_{t}$ we have that

and hence that $\upsilon\left(\mathbf{y}_{t},\mathbf{y}_{-t};x{}_{t},\mathbf{u}_{t},\theta\right)$ is a supermodular function of $\mathbf{y}_{t}$ Topkis_Book98.\footnote{The notation $\mathbf{y}_{t}\lor \mathbf{y}_{t}'$ denotes the join or least upper bound operation, $\mathbf{y}_{t}\land \mathbf{y}_{t}'$ the meet or greatest lower bound operation.} No two actions a player can take are substitutes for one another. \\ \\ The second restriction on $s_{m}\left(\mathbf{y}_{t,-m},\mathbf{y}_{-t}\right)$ also has a nice economic interpretation. It implies that agent $t$'s utility from taking binary actions $m=1,\ldots,M$ is weakly increasing in $\mathbf{y}_{-t}$. Noting that $\left(\mathbb{Y}\setminus\mathbb{Y}_{t},\succeq\right)$ is also a complete lattice, we have that, for all $\mathbf{y}_{t}'\succeq \mathbf{y}_{t}$ and $\mathbf{y}_{-t}'\succeq\mathbf{y}_{-t}$, the increasing differences property

Own and peer actions are complementary. \\ \\ An implication of restrictions (ref) and (ref) is that the game is supermodular in the sense of Milgrom_Roberts_EM1990. They show that in supermodular games there exist two extremal NE in pure strategies -- minimal and maximal -- and that all rationalizable strategy profiles are bounded by these two extremal NE. The monotonicity of the utility function in $\mathbf{y}$ further allows us to find the minimal NE using Tarski's Tarski_PJM55 Theorem. Our algorithm exploits these implications of supermodularity. \\ \\ Our assumptions about sampling and the data generating process are collected in Assumption (ref).

Examples

Although Assumption (ref) is a real restriction, it is sufficiently flexible to accommodate many complete information games of interest to economists. To give some sense of the range of possible applications of our methods, it is helpful to consider a few examples. Our first example is closely related to the peer effects model analyzed in the previous section.

Our second example nests a model analyzed by Krauth_JOE2006 and Soetevent_Kooreman_JAE07, itself a complete information version of the seminal binary action peer effects model introduced by Brock_Durlauf_RES01,Brock_Durlauf_HBE01.

A third example, related to the first two, corresponds to the setting considered by Sundararajan_BE2008, Banerjee_et_al_Sci13, Kim_et_al_Lancet2015 and others.

Our fourth example is adapted from Miyauchi_JOE16, who pointed out the connection between the theory of supermodular games and some models of strategic network formation.\footnote{Miyauchi_JOE16 considered undirected networks, while our analysis formally pertains to directed ones.}

Our final example, due to Jia_EM08 and Nishida_MS2015, is well-known in the field of empirical industrial organization.

Scenario estimation for supermodular games

Our scenario sampling algorithm is easily adapted to handle the more complicated games of this section. Denote the systematic component of player $t$'s action $m$ utility by

Minimal adjustment to the peer effect algorithm outlined earlier gives our general Scenario sampler. \\

As in the peer effects special case, a key component of our general Scenario sampler is a Threshold finder subroutine.

The correctness of the general algorithm follows from a simple extension of Theorem (ref).

The rest of estimation proceeds as described earlier. Although we note that scenario recycling is not straightforward when the strategic interaction parameter, $\delta$, is vector-valued (as discussed further in the Appendix (ref)). This does result in an increase in computation time; although since finding the minimal equilibrium is straightforward in supermodular games estimation remains feasible, even for very large games.

Monte Carlo Experiment

In this section we summarize the results of a small number of Monte Carlo experiments. The purpose of the experiments is to verify our main theoretical claims as well as to get some sense of the small sample performance of our methods in an empirical setting of interest. \\ \\ The Monte Carlo design uses a random geometric graph to construct a friendship network with $T \times T$ adjacency matrix $\mathbf{D}$ Graham_NBER16. The friendship network is exogenous and determines each agent's set of peers. Specifically agents are scattered uniformly on a plane. The network is generated by randomly linking agents which are close to each other on this plane. The purpose is to approximate a real world friendship network where only close agents have the possibility to meet each other. \\ \\ The utility for agent $t$ has the form

In the Monte Carlo design we use four covariates. Two of these covariates are binary (sampled for each player from a Bernoulli distribution). The remaining two covariates are continuously-valued (sampled from a uniform distribution). The preference shocks $\mathbf{U}=\left(U_1,\ldots,U_T\right)'$ are iid standard normal random variables. Full details of the data generating process are available in Appendix (ref). For each simulation we (i) draw the vector of utility shocks $\mathbf{U}$ and (ii) find the minimal equilibrium, $\mathbf{Y}$, by fixed point iteration. Finally, we estimate $\beta$ and $\delta$ based on the resulting observed $\mathbf{Y}$ vector by simulated maximum likelihood (SML) using our Scenario sampler. The regressor matrix $\mathbf{X}$ is simulated once and then held fixed across Monte Carlo replications. \\ \\ We consider two variants of the above setup. In the first estimation is based upon the availability of many independent medium sized games. In this setting the asymptotic sampling distribution of the SMLE of $\theta$ follows from standard large sample results (see Hajivassiliou_Ruud_HBE1994, Newey_McFadden_HBE94). This is a “fixed $T$, fixed $M$, large $N$" setting. \\ \\ We also consider the properties of our SML estimator when there is only a single large game. This is a “large $T$, fixed $M$, fixed $N$" setting. Large sample theory for SML estimates is not available in this setting. Developing such theory raises a number of interesting questions that are well beyond the scope of this paper (see Menzel_ReStud2016 for some relevant ideas and also discussion in the next section). \\ \\ The case of many medium sized games is encountered if the researcher has, for example, friendship data across many independent school classrooms vanRijsewijk_et_al_PLOS2018. The case a single game arises when, for example, the researcher observes a network of relationships in a single village deWeerdt_IAP04. For the many medium sized games case we simulate datasets with $2,000$ agents belonging to one of $N=100$ separate friendship networks (each containing $T=20$ agents). For the single large game case we consider datsets with $T=500$ agents in $N=1$ friendship network. \\ \\ Monte Carlo results for both cases are displayed in, respectively, Panels A and B of Table (ref). We report the average and standard deviation of the SML estimate of $\delta$ across $1000$ simulated datasets for each of the two designs. The true value of $\delta$ is $0.20$, which is close to the average of the SMLEs. Also reported is the size of a likelihood ratio test for $H_0: \delta=0.20$ and the coverage of a Wald-based 95 percent confidence interval for $\delta$. The standard errors used to construct this interval are based upon the simulated Hessian matrix (calculated by differentiating the simulated log-likelihood function). We each design we report results when the likelihood is estimate by drawing $S=1, 10$ and $100$ scenarios. \\ \\ In both designs the SMLE of $\delta$ is approximately unbiased. This holds even when we use only a small number of scenario draws. However the normal approximation, as judged by the size of the LR test and the coverage of the confidence interval, only appears to be accurate for the many games design (consistent with extant large sample theory). This is confirmed by the histograms of the SMLEs for the two designs ($S=100$ cases) shown in Figure (ref). The single game distribution in the right panel is notably skewed. Understanding the sampling properties of SMLEs in single large game settings (the “large $T$, fixed $M$, fixed $N$" case) is an interesting topic for future research. \\ \\ Figure (ref) also shows the sampling distribution of naive probit estimates of $\delta$. Such estimates, since they fail to take into account the simultaneous determination of $Y_1,\ldots,Y_T$, are inconsistent (and clearly so).

\\ \\ We close this section by observing that our Panel B Monte Carlo experiments are based upon a single game with $500$ actions. We are aware of no other maximum likelihood based estimator for games of this size.

Risk-sharing in Nyakatoke

Joachim De Weerdt, in connection with dissertation research, collected risk-sharing links across households in Nyakatoke, a village in the Kagera Region of Tanzania (adjacent to Lake Victoria). Specifically, he asked all adult individuals in the village who they could rely upon for help and, from their responses, constructed a network of directed links across households.\footnote{Comola_Fafchamps_EJ14 discuss the Nyakatoke dataset in detail and our interpretation of the link data follows their suggested one.} deWeerdt_IAP04 undertook a pioneering empirical analysis of these data. He modelled link formation using dyadic logistic regression methods.\footnote{See Graham_EM17 and Graham_CEMMAP22 for formal analyses of the statistical properties of these estimators in single network settings.} The analysis focused on the role of kinhsip, clan, religion, wealth and economic activity overlap in driving link formation. \\ \\ deWeerdt_IAP04 also posited that households exhibited a taste for transitivity in links. To capture this feature of preferences he included the number of friends in common as an additional regressor in his analyses (see Table 6 of his paper). If the payoff from $t$ directing a link to $s$ varies with the presence or absence of other links in the network (e.g., with whether $t$ and $s$ have many friends $r$ in common), then, as described earlier, the observed configuration of links will correspond to the outcome of a strategic network formation game. In such a setting, since links are simultaneously determined (and the model is also incomplete), dyadic logistic regression analysis will not deliver consistent estimates of household preferences over networks. \\ \\ In this Section we re-visit De Weerdt's (deWeerdt_IAP04) analysis. Instead of positing a taste for transitivity we, inspired by Jackson_et_al_AER12, study whether households have a taste for “supported links". Agent $r$ supports a link from $t$ to $s$ (and also $s$ to $t$) if both arcs $(r,t)$ and $(r,s)$ are present. Jackson_et_al_AER12 posit that agents value support, since agent $r$ can monitor and referee any relationship between $t$ and $s$. Formally we posit that household $t$'s payoff from network $\mathbf{y}$ is:

with $\theta=\left(\beta',\delta,\mathbf{A}',\mathbf{B}'\right)'$ for $\mathbf{A}=\left(A_{1},\ldots,A_{T}\right)'$ and $\mathbf{B}=\left(B_{1},\ldots,B_{T}\right)'$. Here $\mathbf{X}$ is a matrix of dyadic regressors. These regressors are extensively described by deWeerdt_IAP04 and more succinctly defined in Table (ref) below. The $\left\{A_t\right\}_{t=1}^T$ and $\left\{B_s\right\}_{s=1}^T$ terms are household-specific parameters allowing for out- and in-degree heterogeneity. They are also sometimes called ego- and alter-effects or sender- and receiver-effects. \\ \\ Such effects accommodate the reality that some households may generically get greater utility, ceterius paribus, from directing a link, while other households may be a priori more attractive link targets. The $\sum_{r=1}^{T}y_{rt}y_{rs}$ term counts the number of agents $r$ available to support arc $(t,s)$. The parameter $\delta$ indexes how much the payoff from directing arc $(t,s)$ increases with support. This is the “strategic" parameter in our model and the one of primary interest here. \\ \\ Before presenting our estimation results we note that our model is non-standard. We have complete data for $T=116$ households (out of a total of 119 households). Hence $\mathbf{Y}$ includes a total of $T(T-1)=13,340$ strategic decisions! Preferences over this graph are indexed by $\dim\left(\theta\right)=\dim\left(\beta\right)+1+2T = 243$ parameters. Inference is based entirely on a single large game (a “fixed" $N$, “large" $T$, “large" $M=T-1$ analysis). The log-likelihood function does not consist of a sum of independent components, the dimension of $\theta$ grows linearly with $T$ and, finally, any large $T$ analysis would have to consider the properties of the network formation game as $T$ grows large Menzel_ReStud2016). \\ \\ Inspired by Mele_Zhu_RESTAT2023 we conjecture that a triangular array set up, with $\delta$ replaced by $\delta_T=\frac{\delta}{T}$, would generate a sequence of games with a non-trivial limit as $T\rightarrow\infty$. Perhaps this set-up, paired with ideas in FernandezVal_Weidner_JOE16 and Graham_EM17, could be used to show consistency and asymptotic normality of $\hat{\beta}$ and $\hat{\delta}$ (likely with a bias in the limit distribution). These are just conjectures; formal analysis is likely to be non-trivial and raises issues well beyond the scope of this paper. Here will simply report simulated maximum likelihood estimates (SMLEs) of $\theta$. The statistical properties of these SMLEs are, as yet, unknown. \\ \\ Table (ref) reports SMLEs of $\theta$. The simulated log-likelihood is constructed as described in Sections (ref) and (ref) above. We use a quasi-Newton optimization algorithm, differentiating the simulated log-likelihood as detailed in Appendix (ref). Standard errors, reported in parentheses, are constructed from the diagonal elements of the inverse Hessian matrix (constructed by double differentiation of the simulated log-likelihood). These standard errors have unknown statistical properties; here they simply provide measures of the curvature of our criterion function in the neighborhood of its maximum. \\ \\ The first column of Table (ref) reports a naive dyadic probit regression fit. These results mirror those in deWeerdt_IAP04, who used a logit specification. The naive probit results suggest that familial connections and spatial proximity are strong drivers of link formation. There is also some evidence of religion- and wealth-based homophily. The extent of overlap in economic activities does not predict links (notwithstanding that the scope for insurance might be greater across households engaging in different types of economic activities). \\ \\ Columns 2 to 4 of Table (ref) report our SMLEs based on varying numbers of scenario draws ($S=1,10,100$). Our point estimates are remarkably insensitive to the number of scenarios drawn, although theoretical considerations privilege those estimates based on a larger number of scenario draws. Our discussion of the substantive aspects of the SMLEs will be based on those reported in Column 4 (which uses $S=100$ scenario draws). \\ \\ We do not fully understand why our results are relatively stable even for small $S$, we conjecture this may reflect the following factors. First, inspection of (ref) indicates that, for a fixed $S$, our importance sampler provides an unbiased estimate of the likelihood function for the network (the log-likelihood function will not be unbiased). Note also that the summands in (ref) are analytically calculated $T(T-1)$-dimensional “rectangular" probabilities (see Appendix (ref)). The analytical calculation of these rectangle volumes is, we believe, a distinct feature of our algorithm relative to other familiar importance samplers in econometrics (e.g., the GHK algorithm). \\ \\ Consider the case where estimation is based on a single scenario draw (i.e., $S=1$), denote this draw by $\tilde{\mathbf{B}}^{\left(1\right)}$. This scenario is the hypercube formed by $T(T-1) = 13,340$ bucket edges, each with upper and lower bounds of, respectively, $\tilde{\bar{b}}_{ts}^{\left(1\right)}$ and $\tilde{\underline{b}}_{ts}^{\left(1\right)}$. These bucket boundaries are determined by the draws of $U_{ts}$ generated in Steps 2 and 3 of the Scenario Sampler. While these draws are not fully independent of one another -- the truncation point for each $U_{ts}$ draw (corresponding to a link present in the graph) depends on the values of prior draws of $U_{t's'}$ -- there is nevertheless a fair bit of independence across them.

\\ \\ When $S=1$ the criterion function we maximize equals

The first term is a summation of $T(T-1)$ random variables. While these random variables are not fully independent, neither are they fully dependent. Suitable normalized, it is plausible that this term has a limit as $T$ grows large. The second term in this expression, which is an output of the Scenario Sampler, doesn't vary with $\theta$. These considerations suggest that our simulated log-likelihood criterion may be a reasonable estimate even when $S=1$. This merits further study. \\ \\ In looking at the point estimates, appropriately taking into account the game-theoretic details of the model results in a support coefficient about 10 percent smaller than what is produced by the naive probit fit. In contrast the coefficients on the homophily measures, on balance, increase in absolute magnitude by about 10 percent once we properly treat the network as a NE. Overall supported links do appear to generate greater utility. Links between blood relatives, geographic neighbors, co-religionists and households with similar wealth levels also generate greater utility. \\ \\ What we wish to emphasize here is that maximum likelihood analysis, fully accounting for the complications arising from strategic interaction, is possible in a game involving over ten thousand strategic decisions and several hundred utility parameters.

Conclusion

In this paper we have presented an algorithm which facilitates simulated maximum likelihood estimation of very large binary-action supermodular games. The introduction of methods allowing for the empirical analysis of datasets recording the outcomes of strategic interaction among multiple agents is one of the major accomplishments of twenty-first century econometrics. It is our hope that the methods proposed in this paper can be used to empirically study games much larger than is currently common. \\ \\ Much work remains to be done. While we have shown how to compute the (simulated) MLE for some very large games, several of our examples are non-standard. These examples involve a likelihood that does not obviously factor into independent components and/or parameter spaces which grow with the “sample size". \\ \\ Research on how to improve the efficiency of our importance sampler would be most welcome, as would a better understanding of how many scenario draws must be taken in practical real world settings to get reliable point estimates. It also seems likely that extant insights from the literature on simulation-based econometrics could be adapted to improve our basic approach. Some ideas in this general direction are discussed in Appendices (ref) and (ref). \\ \\ Our analysis involves a maintained equilibrium selection assumption. Here we have assumed that the minimal NE is the one that is played in scenarios where multiple NEs are possible. It would be easy to adapt our analysis to the case where instead the maximal equilibrium is chosen. Miyauchi_JOE16 shows that, in some models, point estimates based on these two extremal equilibria can be used to estimate the identified set for $\theta$ in the absence of any assumptions about equilibrium selection. This could be an attractive approach is settings where researchers are unwilling to maintain a particular equilibrium selection assumption. \\ \\ In multi-action games with non-exchangeable actions the assumption that $U_{t1},\ldots,U_{tM}$ are iid is unattractive. Agents that have a taste for smoking may have, on average, a taste for drinking as well. We speculate that a pairing of our basic algorithm with ideas underlying, for example, the GHK simulator might be able to handle this extension. While this seems interesting, it is non-trivial and beyond the scope of this paper. \\ \\ Finally, our analysis is restricted to binary supermodular games. It would also be of interest to explore whether the idea of “scenario sampling" can be extended/adapted to non-binary choices and/or non-supermodular games (e.g., entry games with many possible entrants as in Ciliberto_Tamer_EM2009).

\typeout

\setcounter{page}{0} \pagenumbering{arabic} \setcounter{page}{1}