Robust Network Targeting with Multiple Nash Equilibria

Robust Network Targeting with Multiple Nash Equilibria

Keywords: Treatment choice, simultaneous games, incomplete model, strategic complementarity, multiple Nash equilibria.

Introduction

Many policy problems involve allocating treatment among a network of interacting agents. Examples include technology diffusion parente1994barriers, alvarez2023strategic, teenage smoking nakajima2007measuring, consumer adoption decisions banerjee2013diffusion,keane2013comparing, and education and migration hsiao2022educational. Research in these fields highlights the role of spillover effects, particularly those arising from strategic interactions.

Among other things, these strategic interactions lead to the presence of multiple Nash equilibria, which complicates the process of finding an optimal treatment allocation policy. To handle this multiplicity, counterfactual policy analysis “has made simplifying assumptions which either change the outcome space or impose ad hoc selection mechanisms in regions of multiplicity” tamer2003incomplete. Consequently, this approach “potentially introduces misspecifications and nonrobustness in the analysis of substantive questions” de2013econometric. To address this problem, can we develop a treatment allocation rule that remains optimal even under the least favorable equilibrium?

Focusing on a class of network models where units participate in a simultaneous decision game with strategic complementarity brock2001discrete, ballester2006s, molinari2008identification, jia2008happens, echenique2009testing, lazzati2015treatment,graham2023scenario, this paper develops a method for constructing a maximin optimal treatment allocation rule that is robust to the presence of multiple Nash equilibria. A planner allocates a binary treatment among a target population of $N$ units embedded within a network, where each unit's covariates and the network structure are observable. Each unit then simultaneously chooses a binary action to maximize its own utility, which depends on its own characteristics and treatment, as well as the characteristics, treatments, and expected choice of its neighbors\footnote{This incomplete information setting brock2001discrete, bajari2010estimating, de2012inference, is our primary focus. Section (ref) extends our results to the complete information setting.}. Our goal is to learn a treatment allocation policy that maximizes social welfare for the target population.

To determine the optimal treatment allocation rule for the target population, we assume that there exists data for a social network of units who have been assigned treatment in the past. This sample may differ from the target population in terms of both the number of units and the network structure. Data is assumed to be available for each unit's covariates, decisions, and assignments, as well as those of their neighbors. After assessing how individual outcomes vary in response to different treatment allocations among the training sample, we analyze the optimal treatment allocation strategy, taking into account the covariates and network structure of the target population. Consider, for example, targeted information provision in villages with the aim of increasing microfinance adoption, as discussed in banerjee2013diffusion. By analyzing heterogeneous choices among the units in villages selected by policymakers, we then estimate whom to better target in external villages.

There are both theoretical and practical challenges to studying optimal treatment allocation in the presence of strategic interactions. The primary theoretical challenge is incompleteness jovanovic1989observable of the model when there are multiple Nash equilibria\footnote{See the detailed surveys by de2013econometric, molinari2020microeconometrics, kline2020econometric.}. Without assuming an equilibrium selection mechanism, our model predicts a set of equilibrium outcomes under a counterfactual policy. From a theoretical perspective, one cannot judge which equilibrium outcome is more likely than the others. This paper allows for these multiple equilibria and imposes no assumptions on equilibrium selection. Instead, we provide set-identified equilibrium social welfare for any treatment allocation policy, along with a closed-form expression that characterizes the bounds of this set.

As the counterfactual equilibrium social welfare is only set-identified, we cannot directly target equilibrium welfare when designing a treatment allocation rule. To address this uncertainty, we refine the optimality of treatment allocation using the maximin welfare criterion. This criterion is employed in the robust decision theory literature (e.g., chamberlain2000econometric), and the robust mechanism design literature (e.g., morris2024implementation). Under the maximin welfare criterion, our objective is to design a treatment allocation policy that maximizes social welfare evaluated under the least favourable equilibrium selection rule.

In terms of implementation, there are two challenges. We adopt a parametric utility function specification, and the first challenge is estimating the parameters of this utility function. We assume the existence of a one-period training data set that contains a finite number $n$ of units, along with their covariates and the network structure\footnote{We allow the training data to come from our target population, with caveats about the private information of each unit. A more detailed discussion is provided in Section (ref).}. An existing treatment allocation policy is assumed, and we observe each unit's choice under this policy. We estimate parameters using the two-step maximum likelihood estimator proposed by leung2015two. However, in the context of a network game setting, the asymptotic behavior of this estimator cannot be characterized without assuming how the network structure changes as the number of units increases (i.e., whether the network is dense or sparse). Although non-asymptotic results could elucidate how the sampling uncertainty of this estimator is influenced by network structure, the current literature lacks such analysis. Addressing this gap is one of the primary focuses of our paper.

The second challenge to implementation is finding the maximin optimal treatment allocation, which requires optimizing an of an objective function dependent on a system of simultaneous equations. In the presence of strategic interactions, when a treatment is assigned to a unit, it not only influences their behavior but also that of their neighbors. This, in turn, affects the payoff of their neighbors’ neighbors, propagating feedback effects throughout the network and presenting a complex combinatorial optimization problem. To tackle this complexity, we propose a greedy algorithm. This algorithm sequentially assigns treatment to the agent who yields the highest marginal welfare gain at each step. However, this class of algorithm generally lacks a performance guarantee. We address this by characterizing the performance guarantee through the features of our objective function.

We evaluate the performance of our proposed method based on its regret, which is defined as the difference between the largest achievable welfare and the welfare achieved by our proposed method, evaluated under the least favourable equilibrium selection rule. Regret arises from two sources of uncertainty: The first is due to the use of estimated structural parameters, and reflects sampling uncertainty. The second is due to the use of a greedy algorithm.

This paper makes three theoretical contributions: (\romannumeral 1) It provides a closed-form expression for the identified set corresponding to the equilibrium outcomes under any arbitrary policy intervention. The heavy computation costs due to the large number of equilibria have limited the range of empirical applications in the literature to static models with a small number of players and choice alternatives. Our approach avoids computing the set of equilibria and hence allows for a feasible characterization of the identified region for the equilibrium social welfare; (\romannumeral 2) It presents the first non-asymptotic result on regret with strategic interactions. It shows that, under regularity conditions, the regret introduced by sampling uncertainty shrinks at the rate $\log(n)/\sqrt{n}$; (\romannumeral 3) It offers a theoretical performance guarantee for the regret associated with using a greedy algorithm to solve optimization problems involving systems of simultaneous equations, a topic previously unexplored in the existing literature.

To demonstrate how our method can be implemented and quantitatively evaluate its performance, we apply it to the data of banerjee2013diffusion. We design a policy to maximize the take-up rate of microfinance products among households across various villages. For each village in the sample, we estimate the utility function parameters. These estimates are then used to assess the presence of strategic complementarity in each village. We find that strategic complementarities are present in 16 out of the 43 villages. For these villages, we construct an individualized treatment allocation rule using our greedy algorithm. Empirical results revealed that the occurrence of multiple equilibria can vary depending on the allocation method used. We compare the welfare outcomes achieved by our algorithm with those obtained by the NGO Bharatha Swamukti Samsthe (BSS). Our results indicate that, for all 16 villages exhibiting strategic complementarity, our method achieves notably higher welfare levels, with improvements ranging from $20\%$ to $270\%$, and an average improvement of $116\%.$ Additionally, the lower bound of welfare under our method consistently exceeds the maximal welfare attained under the allocation rule used by BSS and a rule that assigns treatment at random. These substantial welfare gains highlight the benefits of individualized targeting in the presence of strategic interference, which demonstrates the efficacy of our approach in optimizing resource allocation and improving social welfare.

Literature Review

This paper is related to several literatures in economics and econometrics, including strategic interactions, statistical treatment rules, robust decision theory, robust mechanism design, and greedy algorithms.

Pioneering contributions to the econometric aspects of game-theoretic models include works by jovanovic1989observable and bresnahan1991empirical, which explore the empirical challenges associated with models that feature multiple equilibria. The recent literature on the econometrics of strategic interactions includes simultaneous decision games with complete information, such as tamer2003incomplete, bajari2010estimating,bajari2010identification, de2018identifying, sheng2020structural, and chesher2020structural; simultaneous decision games with incomplete information, such as de2012inference,de2020testable, menzel2016inference, and ridder2020two; and sequential decision games: aguirregabiria2007sequential,aguirregabiria2019identification, mele2017structural, leung2019inference, and christakis2020empirical.

Focusing on a game with complete information, tamer2003incomplete obtains bounds for structural parameters while remaining fully agnostic about the equilibrium selection mechanism. Motivated by this, sheng2020structural uses a sub-network approach to provide bounds for structural parameters in a network formation setting. chesher2020structural partially identifies structural parameters using the Generalized Instrumental Variable approach chesher2017generalized. bajari2010estimating point identifies the parameters for a game with incomplete information, along with providing a semi-parametric estimator. However, estimation methods typically require observing repeated samples of the game, which may not be feasible for social network games. Motivated by this, leung2015two studies a two-step maximum likelihood estimator in a large network setting, while ridder2020two studies a two-step GMM estimator in a similar setting. The paper adopts an existing estimator for structural parameters and treats this as an intermediate step in estimating an optimal policy.

One important task in obtaining an optimal policy is predicting the equilibrium outcome under counterfactual policies. In the strategic interaction literature, counterfactual analysis has been studied among others by jia2008happens, aguirregabiria2010dynamic, and canen2020decomposition under various assumptions on the equilibrium selection mechanism. ciliberto2009market does not restrict the equilibrium selection rule but considers only some candidate counterfactual policies. Additionally, lee2009multiple investigates ATM network games by enumerating all Nash equilibria and analyzing how different learning algorithms select among them. None of these studies considers the aggregate equilibrium outcome, which aggregates the equilibrium outcomes of each unit, under a counterfactual policy. Here, we consider a social planner, and hence it is crucial to evaluate the aggregate social welfare. Remaining fully agnostic about the equilibrium selection mechanism, we provide a counterfactual analysis of the aggregate social welfare.

Strategic interactions are closely related to social interaction models. These were introduced by manski1993identification, which examines spillover effects through strategic interactions using a linear social interaction model with unique equilibrium. brock2001discrete extends this model to a nonlinear setting and considers multiple equilibria. goldsmith2013social considers the endogeneity of the network formation process. de2024identifying recovers unknown network structure using a linear social interaction model.

This paper contributes to the growing literature on statistical treatment rules, which were introduced into econometrics by manski2004statistical and dehejia2005program. The recent literature includes stoye2009minimax,stoye2012minimax, hirano2009asymptotics,hirano2020asymptotic, chamberlain2011bayesian, kitagawa2018should, ananth2020optimal, athey2021policy, mbakop2021model, kitagawa2021constrained, sun2021empirical, munro2021treatment, christensen2022optimal, adjaho2022externally, kitagawa2022policy, kitagawa2023individualized,KITAGAWA2023109, viviano2024policy, fernandez2024robust, and munro2024treatment. In contrast to the i.i.d. setting considered in most of these papers, we consider a setting where the spillover effects of treatment assignment are important. A small number of papers in the literature considers spillover effects. These include viviano2024policy, ananth2020optimal, munro2021treatment, and kitagawa2023individualized,KITAGAWA2023109. Apart from kitagawa2023individualized, none of those papers consider spillover effects introduced by strategic interaction or the related complications, such as multiple equilibria.

viviano2024policy and ananth2020optimal focus on estimating direct and indirect treatment effects to derive optimal allocation policies based on data. We focus on the strategic interaction setting where each unit’s behavior is influenced by the behaviors of nearby individuals within a network. These interactions are naturally modeled using game theory jackson2015games, which we adopt in our analysis. In addition, using a game theoretical approach enables us to evaluate social welfare directly through the individual's utility and account for the general equilibrium effects. munro2021treatment focuses on a competitive equilibrium where spillover effects are mediated through the equilibrium price. Their approach uses the mean-field limit to characterize the asymptotic behavior of treatment effects, focusing on settings where a unique mean-field equilibrium price exists. kitagawa2023individualized focuses on a sequential decision game with a Markovian structure, which leads to a unique stationary joint distribution of units' decisions mele2017structural. This stationary distribution allows each state to be revisited instead of converging to multiple distinct equilibria. As a consequence, their stationary welfare differs from the equilibrium welfare that we consider here and we do not require the existence of a potential function. KITAGAWA2023109 considers the spillover effects from vaccination.

Although the source of uncertainty is different, our paper robustly addresses the incompleteness introduced by multiple equilibria in a manner inspired by the robust decision theory literature (see the recent survey by chamberlain2020robust). chamberlain2000econometric,chamberlain2000econometrics consider decision-making when there is uncertainty due to a partially specified subjective distribution. Their robust decision rule maximizes the risk function evaluated at the least-favourable distribution. hansen2001robust,hansen2008robustness achieve robustness by working within a neighborhood of a reference model and maximizing the minimum of expected utility over that neighborhood. manski2003partial faces a similar problem to us where some part of the model is missing from the data, and obtains a robust identification region by incorporating the maximum and minimum value of the unobserved component. giacomini2021 applies the robust Bayes approach of berger1994 to a set-identified model, and shows asymptotic equivalence between the identified set and the set of posterior means obtained from using a multiple priors. See also giacomini2021robust and references therein. christensen2023counterfactual relaxes parametric assumptions about the distribution of latent variables in a structural model. Their robust counterfactual set is obtained by maximizing (minimizing) the counterfactual through the distribution of latent variables over a neighborhood of the prespecified parametric distribution.

Finally, this paper is closely related to network games and mechanism design, as exemplified by morris2000contagion, ballester2006s, galeotti2010network, and galeotti2020targeting for network games, and mathevet2010supermodular, gonccalves2020statistical, fu2021full, morris2024implementation, and brooks2024structure for mechanism design. Network games explore how network characteristics influence behavior. jackson2008social and jackson2015games provide comprehensive summaries. galeotti2020targeting employs a principal component approach to analyze how interventions that change characteristics impact outcomes and develops strategies for optimal interventions within network games. However, they assume a unique equilibrium, whereas this paper focuses on models with multiple equilibria. Following the same setting, sun2023structural examines optimal interventions that alter network structure, while kor2022welfare considers interventions that affect both characteristics and network structure. Nonetheless, these studies differ from ours in terms of utility specification, objective function, and the definition of the action space.

This paper can be viewed as a specific instance of mechanism design, where treatments are allocated to incentivize units’ equilibrium behavior towards achieving desired objectives. Closely related is morris2024implementation, which characterizes the set of outcomes achievable from the smallest equilibrium, referred to as the smallest implementable outcome, in a supermodular game. Moreover, within a convex potential game, they show that the optimal outcome—realized by implementing information to maximize the smallest equilibrium—results in all players selecting the same action. While our implementation approach differs, the lower bound of the set-identified social welfare in this paper is similar in concept to these smallest implementable outcomes. However, it is more complex to characterize this set as the number of players increases. Additionally, morris2024implementation leaves open the question of which implementation strategies are needed to achieve these outcomes, a gap this paper addresses.

Outline.$\quad$ The rest of this paper proceeds as follows: Section (ref) introduces the game setting and the solution concept. Section (ref) discusses counterfactual analysis. Section (ref) focuses on treatment allocation and implementation. Section (ref) presents theoretical results related to the implementation of our proposed method. We apply our proposed method to the Indian micro- finance data, which is studied by banerjee2013diffusion, and demonstrate its performance in Section (ref). Section (ref) extends our analysis to the complete information setting. Section (ref) concludes. All proofs and derivations are shown in Appendix (ref) to Appendix (ref).

Model

Setup

Let $\mathcal{N}=\{1,2,..., N\}$ be the target population. Each unit $i$ has a $K$-dimensional vector of characteristics $X_i$ observable to the researcher. $X_i$ is assumed to have bounded support, and we standardize the measurements of $X_i$ to be nonnegative, such that $X_i\in \mathcal{X}\in\mathbb{R}_{+}^{K}$. Let $X=[X_{1}^{\intercal},...,X_{N}^{\intercal}]\in\mathcal{X}^N$ be an $N \times K$ matrix whose $i$th row contains the characteristics of unit $i$, and let $\mathcal{X}^N$ represent the set of all such possible matrices $\mathcal{X}$. Let $D=\{D_1,...,D_N\}\in\mathcal{D}=\{0,1\}^N$ be a vector of binary treatment allocations. For $i \in \mathcal{N}$, $D_i=1$ if unit $i$ is treated and $D_i = 0$ if not.

The social network is represented by an $N \times N$ binary adjacency matrix, denoted by $G=\{G_{ij}\}_{i,j\in\mathcal{N}}\in\mathcal{G}=\{0,1\}^{N\times N}$. $G$ is assumed to be fixed and exogenous, irrelevant to treatment allocation. $G_{ij}=1$ indicates that units $i$ and $j$ are connected, while $G_{ij}=0$ indicates that they are not. Let $\mathcal{N}_i\coloneqq\{j:G_{ij}\neq 0\}$ denote the set of neighbors of unit $i$. $ \begingroup \def\mathaccent#N##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{N} \endgroup $ denotes the maximum number of edges connected to any unit in the network (i.e., $ \begingroup \def\mathaccent#N##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{N} \endgroup =\max_i\vert\mathcal{N}_i\vert$), while $\underline{N}$ denotes the minimum (i.e., $\underline{N}=\min_i\vert\mathcal{N}_i\vert$). We adopt the convention of no self-links (i.e., $G_{ii}=0$ for all $i \in \mathcal{N}$). This framework can accommodate both directed networks, where $G_{ij}$ and $G_{ji}$ can differ, and undirected networks, where $G_{ij}=G_{ji}$ for all $i,j\in\mathcal{N}$. Additionally, we allow the strength of spillover effects to depend not only on the adjacency matrix $G_{ij}$ but also on the covariates and treatment statuses of units $i$ and $j$.

We consider a counterfactual equilibrium social welfare in the context of a large simultaneous decision game. We use the following notation for our simultaneous decision game. $Y_{i}\in\mathcal{Y}=\{0,1\}$ denotes unit $i$'s decision. The decision vector for all units is denoted by $Y= (Y_1,...,Y_N)\in\mathcal{Y}^N$, with $y\in\{0,1\}^N$ representing the realized decision outcomes. Additionally, we define a vector of idiosyncratic shocks $\varepsilon=\{\varepsilon_1,...,\varepsilon_N\}$, where $\varepsilon_i$ is the shock for unit $i\in\mathcal{N}$.

The game, denoted by $\Gamma$, comprises:

\noindentPlayers: \quad A set of individuals that we label $\mathcal{N}$, a social planner;

\noindentPayoffs: \quad The preferences (utilities) of units are denoted by $\{U_i(y, X, D, G; \theta)\}_{i=1}^N$. Following de2012inference and galeotti2020targeting, we endow units with a quadratic utility function

where $\alpha_i\coloneqq\alpha_i(X,D,G)$ and $\beta_{ij}\coloneqq\beta_{ij}(X,D,G)$ are heterogeneous functions that capture unit $i$'s individual utility and spillover utility. The utility of $Y_i=0$ is normalised to $0$.

Given a network $G$, covariates $X=(X_1,...,X_N)$, and a treatment allocation $D=(D_1,...,D_N)$, the coefficient $\alpha_i$ on unit $i$'s choice depends upon their own covariates and treatment status as well as those of all of their neighbors; the coefficient $\beta_{ij}$ multiplying the quadratic term $y_iy_j$ depends upon their own covariates and treatment status as well as those of unit $j$. Since the choice variable is binary, if $\alpha_i$ and $\beta_{ij}$ are unconstrained, then this specification of the utility function is without loss of generality. We endow these utilities with certain properties, which are specified in Section (ref) and Section (ref).

\noindentInformation:\quad The literature delineates two information environments: complete information and incomplete information. In a complete information setting, players can observe all characteristics of other units. This setting is studied in tamer2003incomplete, ciliberto2009market, bajari2010identification and chesher2020structural. Since we consider a large network setting, it may not be plausible for players to have perfect information about all the other units ridder2020two. Therefore, in our headline setting, we follow brock2001discrete, aguirregabiria2007sequential, bajari2010estimating, and de2012inference, and consider an incomplete information setting. All units and the social planner are assumed to observe characteristics $X$ and the network structure $G$, but the vector of idiosyncratic shocks of units is assumed to be unobservable. The realization of $\varepsilon_i$ is unit $i$'s private information. All players are assumed to have a common belief about the distribution of $\varepsilon$. Formally,

These assumptions are standard in the literature de2012inference,leung2015two,ridder2020two. The third assumption can be replaced by a conditional independence assumption if we assume that $F_{\varepsilon\vert X,D,G}(\cdot\vert X,D,G)$ is known.

\noindentActions: \quad At the beginning of the game, the social planner assigns treatment $D_i$ to each unit $i\in\mathcal{N}$ to maximize the planner's welfare:

subject to the capacity constraint $\kappa$ (i.e., $\sum_{i=1}^N D_i\leq \kappa$). The expectation in Eq.(ref) is taken with respect to choices $Y$ given the observed covariates $X$, network structure $G$, and the treatment allocation rule $D$\footnote{With multiple equilibria and no assumption imposed on the equilibrium selection mechanism, the expectation becomes a set in which each element is conditional on a specific equilibrium selection mechanism. This concept will be further formalized in Section (ref).}. The function $g_i: \mathcal{Y}^N\times \mathcal{X}^N\times \mathcal{D}\times\mathcal{G}\rightarrow \mathbb{R}$ allows social welfare to deviate from the utilitarian welfare function, which corresponds to $g_i(\cdot)=U_i(\cdot)$. We explore two common types of social welfare functions: Utilitarian welfare, and Engagement welfare. Section (ref) discusses each in detail.

After receiving their allocated treatment, units choose action $Y$ simultaneously to maximize their own payoff given the realization of $\varepsilon$. With complete information unit $i$'s decision rule would be:

However, since unit $i$ only has partial information about other units, the realization of $Y_{-i}$ is not observed. Therefore, units make decisions that are best responses given their belief about other units' decisions given the public information and their own type. Formally, in the incomplete information setting,

with

As $\varepsilon$ is i.i.d. by Assumption (ref), this can be simplified to:

We have now established the game setting. To further elaborate, we introduce additional notation. Consider the action set $\mathcal{Y}$, defined as $\{0,1\}$. This set is a totally ordered set, endowed with the usual ordering relation $\leq$, characterized by reflexivity, antisymmetry, and transitivity\footnote{Reflexive: $\leq$ is reflexive if $y\leq y,$ for all $y\in\mathcal{Y}^N$. Antisymmetric: $\leq$ is antisymmetric if $y\leq y'$ and $y'\leq y$ implies $y=y'$. Transitive: if $y\leq y'$ and $y'\leq y''$ implies $y\leq y''$.}. The action profile space $\mathcal{Y}^N$, formed as a direct product of $\mathcal{Y}$, also constitutes a partially ordered set topkis1998supermodularity. It is equipped with the product relation $\leq$, where for any $y, y' \in \mathcal{Y}$, we have $y \leq y'$ if and only if $y_i \leq y_i'$ for all $i \in \mathcal{N}$. Given that $\mathcal{Y}^N$ is a partially ordered set, we can define a greatest and least element on it. A strategy profile $y$ is a greatest (least) element on $\mathcal{Y}^N$ if $y\geq y'$ ($y\leq y'$) for all $y'\in\mathcal{Y}^N$. In addition, The \textit{join} of any two elements $y, y'\in\mathcal{Y}^N$, written as $y\vee y'$, is defined as $\inf\{x\in\mathcal{Y}^N:x\geq y, x\geq y'\}$. The \textit{meet}, denoted as $y\wedge y'$, is symmetrically defined as: $\sup\{x\in\mathcal{Y}^N:x\leq y, x\leq y'\}$. In addition, a partially ordered set is called a \textit{lattice} if the join and meet of any pair of elements exist. A lattice is a \textit{complete lattice} if it contains the supremum and infimum of any subsets of it.

Equilibrium

As the game introduced in the previous section features incomplete information, it is a Bayesian game harsanyi1967games, and its Nash equilibria are Bayesian Nash equilibria (BNE). We use the pure strategy BNE solution concept. This is defined as:

Following bajari2010estimating, we represent the Bayesian Nash equilibrium in the conditional choice probability space. Denote the conditional choice probability (CCP) profile as $\sigma(X,D,G)= \{\sigma_i(X,D,G)\}_{i=1}^N$. An element of the CCP profile:

Combining the specification of $Y_i$ (Eq.(ref) and Eq.(ref)) with Eq.(ref), we have:

Let $\Omega$ be a mapping from $[0,1]^N$ to $[0,1]^N$ that collects Eq.(ref) for all units. This is a non-linear simultaneous equation system. An equilibrium CCP profile $\sigma^*(X,D,G)$ is a fixed point of this simultaneous equation system:

This is one representation of the Bayesian Nash equilibrium. Alternatively, given an equilibrium CCP profile $\sigma^*$, a fixed $X,D,G$, and a realization of $\varepsilon$, we can define a Bayesian Nash equilibrium $\{y_{i}^*\}_{i=1}^N$ as:

As the right hand side of Eq.(ref) is equal to $F_{\varepsilon}(\alpha_i+\sum_{j\neq i}\beta_{ij}\sigma_{j})$, the existence of a fixed point is guaranteed by the Brouwer fixed-point theorem brouwer1911abbildung. As noted in echenique2009testing, this type of simultaneous equation system can have multiple fixed points. In particular, games with strategic complementarity, as in our setting, tend to have a large number of equilibria takahashi2008number. Let $\Sigma\coloneqq\{\sigma:\sigma=\Omega(\sigma)\}$ denote the set of equilibria. Any equilibrium outcome in this set is a reasonable prediction. In other words, for a given $X, D, G$ and $\theta$, the model predicts a set of equilibrium outcomes $\sigma^*$. If we do not assume an equilibrium selection mechanism, this multiplicity introduces incompleteness jovanovic1989observable. Incompleteness dramatically increases the difficulty of counterfactual analysis since the model can only identify a set of equilibrium CCP profiles $\Sigma$ with a newly implemented policy (i.e., a new treatment allocation rule $D$).

With a newly implemented policy, the realized equilibrium depends on an equilibrium selection mechanism. Let $\xi:\Sigma\rightarrow[0,1]$ denote the probability distribution over equilibria, and let $\Delta(\Sigma)\coloneqq\{\xi:\sum_{\sigma^*\in\Sigma}\xi(\sigma^*)=1\}$ denote the set of all the probability distributions. The equilibrium selection mechanism is a mapping from the public information (i.e., $X, D, G$) to one particular element of $\Delta(\Sigma)$. Formally:

If the equilibrium selection mechanism is observable, the conditional choice probability becomes complete by conditioning on $\lambda$. Since

There are two main difficulties in characterizing the equilibrium outcome under a newly implemented policy. First, the equilibrium selection mechanism is not directly observable. The identification of an equilibrium selection mechanism from data is studied in bajari2010identification and aguirregabiria2019identification, among others. This is useful in the identification of parameters, since parameter values are independent of $\lambda$. For counterfactual analysis, however, there is no guarantee that the equilibrium selection mechanism remains fixed when $X,D,G$ changes. The second difficulty is that the cardinality of $\Sigma$ increases dramatically with the number of units in the network. Hence, it is not feasible to evaluate the summation in Eq.(ref). To improve the tractability of counterfactual analysis, we focus on a game with strategic complementarity.

Complementarity and Supermodular Games

Strategic complementarity in games implies that, given an ordering of strategies, a player's choice of a higher action incentivizes other players to similarly choose a higher action bulow1985multimarket. In economics, complementarity is an important and empirically relevant concept molinari2008identification. It has many policy applications, such as price setting alvarez2022price, house prices guren2018house, technology adoption alvarez2023strategic, as well as the additional examples given in molinari2008identification, lazzati2015treatment, and graham2023scenario. The theoretical literature has established that games with strategic complementarities have robust dynamic stability properties milgrom1991adaptive,milgrom1994monotone. This means they converge to the set of Nash equilibria even with simple learning dynamics (fudenberg1998theory; chen2004does). topkis1998supermodularity shows that strategic complementarity and supermodularity are equivalent in finite strategy games. The mathematical property supermodularity simplifies analysis. It captures the idea of increasing returns between the choice variables. Therefore, to analyze the Bayesian Nash equilibrium of our game, we characterize it as a supermodular game. The definition of supermodular game is:

The definitions of a supermodular function and increasing differences are:

topkis1998supermodularity shows that, for a real valued utility function, increasing differences is equivalent to complementarity between units' decisions. Given the definition of a supermodular game above, $U_i$ is a supermodular function on $\mathcal{Y}^N$ if and only if $U_i$ exhibits increasing differences on $\mathcal{Y}^N$ topkis1998supermodularity. Therefore, we have equivalence between complementarity and supermodularity in our game. Topkis's characterization theorem topkis1978minimizing shows that

is a necessary and sufficient condition to guarantee a utility function is a supermodular function on $\mathcal{Y}^N$. In our specification, this is equivalent to $\beta_{ij}\geq 0$ for $j\neq i$.

Assuming that $\beta_{ij}\geq 0$ for $j\neq i$, our game is a supermodular game since $\{0,1\}^N$ is a complete lattice and our utility function is continuous. Tarski's fixed point theorem tarski1955lattice then guarantees the existence of pure strategy Bayesian Nash equilibrium $y^*$. In particular, there always exists a least BNE $\underline{y}^*$ and a greatest BNE $ \begingroup \def\mathaccent#y##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{y} \endgroup ^*$ milgrom1990rationalizability. Tarski's fixed point theorem can be applied to the conditional choice probability space instead of the strategy profile space to obtain an equivalent result. $[0,1]^N$ is also a complete lattice, and $\Omega:[0,1]^N\rightarrow[0,1]^N$ in Eq.(ref) is an increasing function given $\beta_{ij}\geq 0$. Therefore, we have a maximal equilibrium CCP profile $ \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^*$ and a minimal equilibrium CCP profile $\underline{\sigma}^*$. In section (ref), we show how strategic complementarity simplifies counterfactual analysis.

Counterfactual Analysis for the Target Population

The goal of this paper is to obtain a treatment allocation that maximizes the equilibrium social welfare of the target population. To achieve this, we first need to characterize the counterfactual equilibrium social welfare if we implement a policy in the target population, which may have a different network structure to the training sample. As the equilibrium selection mechanism is unobservable, the literature typically obtains a point-identified prediction for welfare by assuming how counterfactual policies affect the equilibrium selection mechanism. For example, jia2008happens assumes that a specific equilibrium is always played, aguirregabiria2010dynamic assumes the equilibrium remains the same after intervention, and canen2020decomposition assumes that the equilibrium selection mechanism is invariant to the intervention. However, it is impossible to test the appropriateness of these assumptions given the existing method. In contrast, following tamer2003incomplete, we are fully agnostic about how policy changes the equilibrium selection mechanism. In other words, the question we focus on is: If we are agnostic about the equilibrium selection mechanism, what counterfactual outcome does the model predict?

Recall that our social welfare function is:

With multiple equilibria and no assumption imposed on the equilibrium selection mechanism, our model provides a set-valued equilibrium probability distribution fot $Y$ conditional on $X, D, G$. Therefore, the expectation in Eq.(ref) is also a set, with each element an expectation conditional on a particular $\lambda$. Formally,

where

This paper considers counterfactual analysis for two standard social welfare functions.

Consider the engagement welfare function. We define bounds for equilibrium welfare, given covariates $X$, network $G$ and an arbitrary treatment allocation rule $D$, as:

Accordingly, let $\underline{\lambda}$ be the least-favorable equilibrium selection mechanism and $ \begingroup \def\mathaccent#\lambda##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\lambda} \endgroup $ the most-favorable equilibrium selection mechanism :

In general it is not possible to solve for these two extreme points. There are two obstacles. First, the number of equilibria increases rapidly with the number of units in the network. Evaluating the expectation with respect to the joint distribution of $Y$ thus becomes infeasible. Second, the space of the equilibrium selection mechanisms $\Lambda$ may be infinite. This complicates any search for the infimum and supremum $\lambda$ across $\Lambda$.

In the existing literature, counterfactual analysis ciliberto2009market often focuses instead on the conditional choice probability (CCP). With no assumptions on the equilibrium selection mechanism, the bounds of the counterfactual CCP are:

These bounds can be computed using off-the-shelf methods (e.g., sheng2020structural for complete information settings). However, exact bounds of social welfare cannot be directly obtained from the bounds of the CCP. This is because:

and

That is, the lower (and upper) bound of unit $i$'s conditional choice probability may be obtained under a different equilibrium selection mechanism to the bound for some unit $j \neq i$. Therefore, bounds for social welfare obtained by summing the bounds on the CCP will generally be loose. However, we show that Eq.(ref) and Eq.(ref) hold with equality in a supermodular game. Formally,

A proof of Theorem (ref) is provided in Appendix (ref). This new result characterizes the most and least favorable equilibrium selection rules for aggregate social welfare. This approach enables us to leverage Tarski's fixed point theorem, which significantly reduces the computational burden by obviating the need to calculate all possible Nash equilibria. Furthermore, it establishes equivalence between the identified set of aggregate social welfare and the aggregation of identified sets of conditional choice probabilities, concepts studied in sheng2020structural and gu2022counterfactual. This equivalence is not guaranteed to hold in the absence of complementarity. When there are values of $\varepsilon$ with unordered multiple equilibria, such as $(Y_1=1, Y_2=0)$ and $(Y_1=0, Y_2=1)$ in the two-unit case, the process of identifying the least and most favorable $\lambda$ is significantly more complicated. Intuitively, the bounds coincide because strategic complementarity guarantees the existence of a least BNE and a greatest BNE for all the values of $\varepsilon$. Since the social welfare function is a monotonically increasing function of $\sigma$, it achieves its lower bound at the least equilibrium $\underline{\sigma}^*$ and its upper bound at the greatest equilibria $ \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^*$. By definition, the conditional choice probability $\Pr(Y_i=1\vert X,D,G,\lambda)$ also achieves its lower bound under $\underline{\sigma}^*$ and its upper bound under $ \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^*$ . The same argument can be applied to utilitarian social welfare to obtain the following corollary.

A proof of Corollary (ref) is provided in Appendix (ref). This result implies that it is sufficient to compute the minimal and maximal equilibrium CCP profile for the utilitarian welfare in the incomplete information setting. This result does not hold in the complete information setting, where we provide an alternative approach to compute the bounds of the identified set.

The details of the computation of the maximal and minimal equilibrium conditional choice probabilities (CCPs) are discussed in Section (ref). The arguments above apply not only to the counterfactual analysis of treatment allocation policies but also to policy interventions that alter covariates or the network structure.

Treatment Allocation

Our model allows for multiple equilibria, but can only predict a set of possible equilibrium outcomes, denoted as $W_{X,G}(D)$. Consequently, the expected value calculation that determines social welfare is not well-defined without specifying the equilibrium selection mechanism. Drawing on game theory morris2024implementation and robust decision theory chamberlain2000econometric, we apply the maximin welfare criterion to select a treatment allocation rule. This approach involves a social planner opting for choices that lead to higher welfare while preparing for the worst-case scenario of the least favorable equilibrium. Essentially, the planner anticipates the minimal equilibrium will be realized. For example, segal2003coordination discusses scenarios in contracting where the worst-case equilibrium corresponds to the Pareto-efficient outcome for the parties involved. Moreover, in settings where action 0 is the default, games exhibiting strategic complementarity tend to converge toward their minimal equilibrium.

The planner chooses $D$ to maximise welfare under the assumption that the minimal equilibrium, conditional on the chosen $D$, will be realized. We denote the set of feasible allocations by $\mathcal{D}_\kappa\coloneqq\{D\in\mathcal{D}:\sum_{i=1}^N D_i\leq \kappa\}$. Formally:

Recall that, by Theorem (ref), the lower bound of equilibrium social welfare equals the summation of individual welfares. Thus, the maximin welfare optimisation problem simplifies to:

where $W_{X,G,\underline{\lambda}}(D)$ is the social welfare function evaluated at the minimal equilibrium. This formulation converts the maximin welfare problem into a straightforward maximization problem, providing a clear framework for solving the optimal treatment allocation problem.

Implementation

Identification

The preceding discussion has assumed that true parameter values are observed. To implement our proposed method, we first describe the identification of structural parameters using a training sample . Details on the estimation procedure are provided in Section (ref).

The discussion of counterfactual analysis in Section (ref) makes no assumptions about the functional form of parameters $\{\alpha_i\}_{i\in\mathcal{N}}$ and $\{\beta_{ij}\}_{i,j\in\mathcal{N}}$. However, observable data is limited to units' choices, covariates $X$, the network structure $G$, and a predetermined treatment allocation $D$. In practice, we are restricted by what it is possible to identify given this data.

For identification, we follow bajari2010estimating and adopt the inverse-CDF procedure\footnote{This approach builds on hotz1993conditional and aguirregabiria2007sequential.}. Let $\varepsilon^n$ be the private information in the training data, which is distinct from $\varepsilon$ in the target population. Recall from Eq.(ref) that, given an equilibrium conditional choice probability profile in the training data $\sigma^{data}$, unit $i$ chooses their actions according to the decision rule

The equilibrium CCP profile is thus:

Taking the inverse of the CDF of $\varepsilon$ on both sides in Eq.(ref) yields:

Even assuming that the equilibrium CCP profile in the training data is observable, identifying all the parameters in Eq.(ref) remains challenging. Determining all utility parameters involves solving for $N\times N$ unknown parameters on the right-hand side of the above equation. However, the left-hand side of Eq.(ref), only provides information about $N$ scalars. Given these limitations, we define our utility function as follows to ensure identifiability and allow for the analysis of general treatment effects:

where $m_{ij}=m(X_i,X_j)$ is a (bounded) real-valued function of personal characteristics. $m_{ij}$ measures the distance between unit $i$'s characteristics and unit $j$'s characteristics; the spillover effect is weighted by how similar two units appear. The utility that unit $i$ derives from an action is the sum of the net benefits that they accrue from their own actions and from those of their neighbors. We assume that a unit's utility is only affected by the actions of their direct neighbors, not one-link-away contacts. The payoff of action $Y_i=1$ has six components. When unit $i$ chooses action $Y_i=1$, they receive utility $\theta_0$ irrespective of their allocated treatment. They also receive additional utility $\theta_1D_i$ depending upon their own treatment status. Their utility also includes a heterogeneous component $X_i^{\intercal}(\theta_2+\theta_3D_i)$, which depends upon their characteristics $X_i$. Next, there is a spillover effect from the action of unit $j$. If unit $j$ is a neighbor of unit $i$ that receives treatment, then this provides $\theta_4m_{ij}$ additional utility to unit $i$. The fifth and sixth components represent strategic complementarity. If unit $j$ is a neighbor of unit $i$ and selects $Y_j = 1$, then unit $i$'s payoff is increased by $\theta_5 m_{ij}$ The final component corresponds to choice spillovers between neighbors who receive treatment. If both unit $i$ and unit $j$ receive treatment and both choose action $1$, unit $i$ receives additional utility $\theta_6m_{ij}$.

Accordingly, the structural parameters $\theta$ are uniquely determined by the conditional choice probabilities in the training sample, thus identifying the payoff function. This discussion provides only an informal overview of the identification process; a formal proof is available in bajari2010estimating.

Estimation

For estimation, we employ the two-step maximum likelihood estimation procedure of leung2015two. The first step involves estimating the equilibrium conditional choice probability from the training data. In the second step, structural parameters are estimated by maximizing the likelihood function given the estimated CCP profiles. To distinguish the training data from the target population, we denote covariates as $\mathsf{X}=\{\mathsf{X}_i\}_{i=1}^{n}$, the treatment allocation as $\mathsf{D}=\{\mathsf{D}_i\}_{i=1}^{n}$, decisions as $\mathsf{Y}=\{Y_i\}_{i=1}^{n}$, and the network structure as $\mathsf{G}=\{\mathsf{G}_{ij}\}_{i,j=1}^{n}$. In addition, let $S = (\mathsf{X},\mathsf{D},\mathsf{G})$ .

Let $\{\hat{\sigma}_i^{data}\}_{i=1}^N$ be the CCP in the training data. Given that the training dataset contains only a single large network, two necessary conditions on the training data are required to estimate the conditional choice probability: symmetric equilibrium\footnote{A symmetric equilibrium implies that two units will exhibit identical conditional choice probabilities if they receive the same treatment, share identical covariates, and have comparable neighbors, specifically in terms of the neighbors' treatments and covariates.} leung2015two and network decaying dependence condition xu2018social. In general, each unit's choice depends on all public information across the network $G$ (i.e., $X$ and $D$ of all units), although direct payoffs may depend only on immediate spillovers. Under the network decaying dependence condition, it is sufficient to consider only interactions within a relatively small distance.

Several estimation approaches have been proposed for CCP. These including the empirical frequency estimator hotz1993conditional, sieve estimation bajari2010estimating, flexible logit estimation arcidiacono2011conditional, and logit Lasso estimation chernozhukov2022locally. Here we leave aside the question of the most suitable procedure. Instead, we assume the existence of an estimator that satisfies the following statistical property:

This assumption is satisfied by the empirical frequency estimator leung2015two,ridder2020two and logit/probit estimation\footnote{By Hoeffding's inequality, the frequency estimator easily satisfies the Assumption (ref). The probit/logit estimator satisfies the Assumption (ref) by the same argument as the second-stage MLE estimator in Section (ref).}. The ultimate goal is to choose $\hat{\theta}$ that maximizes the likelihood function. As $\sigma^{data}$ is unobserved, we replace $\sigma^{data}$ in the likelihood function with $\hat{\sigma}^{data}$ and estimate $\boldsymbol{\theta}$ by maximizing the quasi-likelihood function $\hat{Q}_n(\hat{\sigma}^{data},\boldsymbol{\theta})$.

where

In addition, $Z_i$ denotes the vector of regressors that would be obtained if we replaced $\hat{\sigma}^{data}_i$ in $\hat{Z}_i$ with the true conditional choice probability $\sigma^{data}_i$.

Computation of Equilibria

After obtaining estimated parameters, we compute the set of equilibrium social welfare for given covariates $X$, network structure $G$, and a treatment allocation $D$ in the target population. The lower bound and upper bound of this set are: $\Pr(Y_i=1\vert X,D,G,\underline{\lambda};\hat{\theta})$ and $\Pr(Y_i=1\vert X,D,G,\overline{\lambda};\hat{\theta})$ for all unit $i\in\mathcal{N}$. We first rewrite these two conditional probabilities as:

From Theorem (ref), $\Pr(Y_i=1\vert X,D,G,\lambda)$ achieves its upper (lower) bound when the equilibrium is $ \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^*$ ($\underline{\sigma}^*$) for all $i\in\mathcal{N}$. Therefore,

where $\hat{\bar{\sigma}}_i^*$ and $\hat{\underline{\sigma}}_i^*$ represent the estimators for the maximal and minimal equilibria, respectively. Hence, we need only compute the least and greatest equilibrium CCP profile. topkis1979equilibrium provides an easily implemented algorithm that is guaranteed to converge to the least and greatest equilibrium point of a supermodular game. Hold $X,D,G$ fixed. To obtain the greatest fixed point $ \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^*$, begin with $ \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^0=\{1,...,1\}$. Define a sequence $\{ \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^t\}_{t=0}^T: \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^{t+1}= \Omega( \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^{t})$. By construction, $ \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^0\geq \Omega( \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^0)$. Since $\Omega(\cdot)$ is an increasing function, $\Omega( \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^0)\geq \Omega( \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^1)$. Therefore, $ \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^0\geq \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^1\geq ...\geq \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^T$. Suppose the iteration convergences on the $M$-th step. Then $ \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^M$ is the greatest equilibrium since, for all the other $\sigma^*$, $ \begingroup \def\mathaccent#\sigma##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\sigma} \endgroup ^M=\Omega^M(\sigma^0)\geq \Omega^M(\sigma^*)=\sigma^*$.

With a symmetric argument, we can obtain the least equilibrium CCP profile. Here we begin with $\underline{\sigma}^0=\{0,...,0\}$. Define a sequence $\{\underline{\sigma}^t\}_{t=0}^T: \underline{\sigma}^{t+1}= \Omega(\underline{\sigma}^{t})$. By construction, we have $\underline{\sigma}^0\leq \Omega(\underline{\sigma}^0)$. Again, $\Omega(\underline{\sigma}^0)\leq \Omega(\underline{\sigma}^1)$. Therefore, $\underline{\sigma}^0\leq \underline{\sigma}^1\leq ...\leq \underline{\sigma}^T$. Suppose the iteration convergences on the $M$-th step. Then $\underline{\sigma}^M$ is the least equilibrium since, for all the other $\sigma^*$, $\underline{\sigma}^M=\Omega^M(\sigma^0)\leq \Omega^M(\sigma^*)=\sigma^*$.

Greedy Algorithm

The previous sections describe the estimation of parameters and computation of the least equilibrium CCP profile. In this section, we propose an algorithm to allocate treatment in a manner that maximizes the worst-case social welfare given the estimated parameters. Define the empirical welfare function to be the welfare function with estimated structural parameters:

We seek to maximize the empirical welfare evaluated at the minimal equilibrium:

As shown in Eq.(ref), $\underline{\sigma}^{*}$ is a solution to a non-linear simultaneous equation system. The conditional choice probability $\underline{\sigma}^*_i$ of unit $i$ depends non-linearly on the conditional choice probability $\underline{\sigma}^*_j$ and treatment assignment of their neighbors $\{D_j:j\in\mathcal{N}_i\}$. Therefore, when a treatment is assigned to one unit, it not only influences their behavior but also leads to spillover effects through the network. Hence, Eq.(ref) is a complicated combinatorial optimization problem. We propose a greedy algorithm\footnote{A greedy algorithm is a heuristic approach used in optimization problems; it makes a series of choices that appear to offer the most immediate benefit, building a solution step by step to achieve locally optimal results.} (Algorithm (ref)) to solve this problem heuristically.

Intuitively, our greedy algorithm assigns treatment to the unit that contributes most to the welfare objective, and repeats this until a capacity constraint binds. Specifically, in each round, Algorithm (ref) computes the marginal gain of receiving treatment for each untreated unit, evaluated at the least equilibrium CCP profile. We refer to the unit whose treatment induces the largest increase in the worst-case welfare as the most influential unit for that round.

Theoretical Analysis

In this section, we analyze the theoretical properties of our proposed treatment allocation method. To simplify notation, denote the welfare of the targeted population $W_{X,G,\underline{\sigma}^*}(D)$ as $W(D)$, and empirical welfare $W_{X,G,\underline{\sigma}^*}^n(D)$ as $W_n(D)$. In addition, let $W(D^*)$ denote the welfare of the target population at its global optimizer $D^*$, and $W(\hat{D}_{G})$ denote the welfare of the target population welfare under the treatment allocation rule obtained by our proposed method. Let the regret of the proposed treatment allocation policy be:

We evaluate the performance of our proposed treatment allocation method using expected regret, which is defined as:

where the expectation $\mathbb{E}_{\varepsilon^{n}}[\cdot]$ is taken with respect to the uncertainty in the training data\footnote{In the incomplete information setting, the unobserved variables represent units' private information. If the units in the training data are the target population, this may coincide for the training data and the target population. In this case, the expectation in the regret is taken with respect to the uncertainty in the target population. All discussions in this section are otherwise unchanged.} conditional on the observed covariates $\mathsf{X}$, treatment allocation $\mathsf{D}$, network $\mathsf{G}$, and equilibrium $\sigma^{data}$. This is because the randomness in our proposed method primarily arises from utilizing the estimated parameters, which involve only the training data. This criterion captures the average welfare loss when implementing estimated policy $\hat{D}_{G}$ relative to the maximum feasible population welfare. Recall that $W_n(\Tilde{D})$ is the maximum for empirical welfare. We decompose regret into (eight terms):

The first term measures the deviation arising from the use of the empirical social welfare function. This term is bounded by:

The second term measures the performance of the population welfare maximizer in the empirical social welfare function. This term is bounded by:

The third term measures the loss caused by using a greedy algorithm to solve the optimization problem. This is discussed in Section (ref). The final term also measures regret introduced by using the empirical social welfare function. This term is bounded by:

Combining all the above results, we conclude that expected regret is bounded by:

In the remainder of this section, we provide a non-asymptotic upper bound for expected regret.

Sampling Uncertainty

For illustrative purposes, this section focuses on engagement welfare. We begin by addressing the regret resulting from the use of estimates in place of true parameters in the payoff function. This represents the sampling uncertainty of the proposed method. We impose the following assumption on the parameter space:

Assumption (ref) is standard. We now proceed to characterize the sampling uncertainty associated with using the empirical welfare function.

A proof of Lemma (ref) is provided in Appendix (ref). Lemma (ref) enables us to characterize the regret of maximizing the empirical welfare through the sampling uncertainty of the structural parameter estimators (i.e., $\mathbb{E}_{\varepsilon^{n}}\big[\Vert \hat{\theta}-\theta\Vert_1 \big\vert S,\sigma^{data}\big]$). As there is no closed-form expression for MLE $\hat{\theta}$ in our case, we study the sampling uncertainty of $\hat{\theta}$ through the sampling uncertainty of its associated empirical process

where the empirical process $\mathbb{G}_n(\theta)$ is defined as

and

Recall that $\hat{Z}_i$, as defined in Eq.(ref), serves as the regressor in our likelihood function. Since we are using a quasi-likelihood ML estimator, the criterion function $\hat{\mathbb{M}}(\theta)$ is evaluated at the estimated equilibrium in the data $\hat{\sigma}^{data}$. As a result, Eq.(ref) contains two sources of sampling uncertainty: uncertainty from $\hat{\theta}$, and uncertainty from $\hat{\sigma}^{data}$. The difference between $\mathbb{G}_n(\hat{\theta})$ and $\mathbb{G}_n(\theta_0)$, is given by:

To study the relationship between the estimator and its associated empirical process, we start with a second-order Taylor expansion with Lagrange remainder for both terms in Eq.(ref):

for some $\acute{\theta}\in\mathbb{R}^{d_{\theta}}$ and $\grave{\theta}\in\mathbb{R}^{d_{\theta}} $ on the segment from $\theta_0$ to $\hat{\theta}$. Let $\eta_{max}^0$ denote the largest eigenvalue (in magnitude) of $\nabla_{\theta}^2\hat{\mathbb{M}}(\acute{\theta})$, and $\eta_{max}^1$ denote the largest eigenvalue of $\nabla_{\theta}^2M(\grave{\theta})$. By Assumption (ref) (ii), the Hessian matrix is symmetric. Therefore, by the Courant-Fischer Theorem\footnote{The largest eigenvalue $\eta_{max}$ of a $C\times C$ symmetric matrix $M$ is given by the maximum Rayleigh quotient (i.e., $\eta_{\max}=\max_{A\in\mathbb{R}^{C}\setminus\{0\}}\frac{A^{\intercal}MA}{A^{\intercal}A}$).}, we can characterize the relationship between the parameter sampling uncertainty and the deviation of the criterion function through:

Combining Eq.(ref) with Eq.(ref) and Eq.(ref) yields

Applying the mean value Theorem to the left-hand side of Eq.(ref), we have

for some $\Tilde{\theta}\in\mathbb{R}^{d_{\theta}}$ on the segment from $\theta_0$ to $\hat{\theta}$. Since $\hat{\theta}$ is the maximizer of $\hat{\mathbb{M}}(\cdot)$ and $\theta_0$ is the maximizer of $M(\cdot)$, Eq.(ref) must be positive given the definition of $\mathbb{G}_n$. By the Cauchy–Schwarz inequality,

Combining Eq.(ref) and Eq.(ref),

Assuming $\hat{\theta}$, an MLE estimator, lies in the interior of the parameter space, the Hessian matrix $\nabla_{\theta}^2\hat{\mathbb{M}}(\acute{\theta})$ is negative definite. Therefore, $\eta_{max}^0$ is negative. In addition, as $\theta_0$ is the maximizer of $M(\theta)$, $\eta_{max}^1$ also must be negative. Hence,

If $\eta^0_{max}$ and $\eta^1_{max}$ did not depend on the sample size $n$ (i.e., if they were constant), we could study the finite sample properties of $\Vert\hat{\theta}-\theta_0 \Vert_1$ through the finite sample properties of the empirical process $\nabla_{\theta}\mathbb{G}_n(\Tilde{\theta})$. However, the Hessian matrix is a function that depends on the sample, so $\eta_{\max}^0$ and $\eta_{\max}^1$ also depend on $n$. This prevents us from characterizing the finite sample properties of our estimator.

To overcome this difficulty, we establish a uniform constant upper bound for the largest eigenvalue of the Hessian matrices, which guarantees their strict negativity. We denote the uniform constant upper bound for the largest eigenvalue as maximal largest eigenvlaue and as smallest To obtain a over all the possible samples, we impose the following three assumptions:

Assumption (ref) imposes a regularity condition on the shape of the CDF function. The following are two examples of common distributions that satisfy this assumption:

Assumption (ref) guarantees that the average number of treated units in the training data is non-zero for any network size. Building on Eq.(ref), the following Lemma uniformly characterizes the relationship between the sampling uncertainty of $\hat{\theta}$ and the sampling uncertainty inherent in the empirical process $\mathbb{G}_n(\cdot)$. Formally:

Proof of Lemma (ref) is provided in Appendix (ref), where we establish a uniform upper bound for the largest eigenvalues (i.e., $\eta_{max}^0$ and $\eta_{max}^1$), termed the maximal largest eigenvalue. We show that this value is strictly negative and is encapsulated within the constant $C_2$. As $C_2$ in Lemma (ref) is a constant, characterising the concentration of the empirical process $\nabla_{\theta}\mathbb{G}_n(\Tilde{\theta})$ is sufficient. The next section does so.

Finite Sample Result

Recall we are using a two-step ML estimation procedure, so the first step of estimation introduces additional sampling uncertainty through $\hat{\sigma}^{data}$. We incorporate these two layers of sampling uncertainty in the following lemma:

A proof of Lemma (ref) is provided in Appendix (ref). Lemma (ref) analyzes the finite sample property of the empirical process (i.e., $\mathbb{E}_{\varepsilon^{n}}\big[\Vert\nabla_{\theta}\mathbb{G}_n(\theta )\Vert_1\big\vert S,\sigma^{data}\big]$). By combining the results of Lemma (ref), Lemma (ref) and Lemma (ref), we have our main theorem. This theorem characterizes the sampling uncertainty of using the empirical welfare:

A proof of Theorem (ref) is provided in Appendix (ref). This new result characterizes the finite sample properties of the sampling uncertainty that emerges when utilizing empirical welfare in settings of strategic interaction. It shows that the regret associated with empirical welfare converges at a rate influenced by the size of the network in the training data, as well as by the covariates and the chosen distribution for private information. Furthermore, this result characterizes the performance of the two-step maximum likelihood estimation from a finite sample perspective. This analysis can be extended to general M-estimators, including the Generalized Method of Moments and broader MLE frameworks.

Regret due to our Greedy Algorithm

Now, we evaluate the second term of Eq.(ref), which is the regret introduced by our greedy algorithm,

In general, the gap between a greedy optimizer and the global optimizer in terms of the value of the objective function is unknown. For monotone non-decreasing submodular set functions, nemhauser1978analysis shows that a greedy algorithm achieves results within $(1-1/e)$ of the global maximum value. Although our optimization problem does not involve a submodular function, our empirical findings in Section (ref) indicate that our greedy algorithm performs well, a result echoed in other applications such as experimental design lawrence2002fast. Building on these findings, bian2017guarantees provides a theoretical performance guarantee for using a greedy algorithm on non-submodular functions by leveraging the submodularity ratio and curvature of the objective function.

Submodularity, the submodularity ratio, and the curvature of a set function $f$ are defined as follows.

Submodularity is similar to diminishing returns. It states that adding an element to a smaller set yields a greater benefit than adding it to a larger set. lovasz1983submodular highlights that, in discrete optimization, submodularity plays a role analogous to convexity in continuous optimization. The submodularity ratio measures how close a set function is to being submodular das2011submodular. Curvature quantifies the extent to which a set function deviates from being additive.

We evaluate the theoretical performance of our greedy algorithm in scenarios where the treatment exerts both direct and indirect positive effects on equilibrium welfare, as indicated by positive values for $(\hat{\theta}_1+X_i^{\intercal}\hat{\theta}_3)$ and $\hat{\theta}_5$. Additionally, our empirical analysis explores a variety of other scenarios, including those with a negative direct effect but a positive indirect effect, among others. The results indicate that the algorithm performs well across a range of conditions.

To characterize the submodularity ratio and curvature of the objective function, we first represent it as a set function, which is a real-valued mapping defined over treatment allocations sets, $\mathcal{D}\subset \mathcal{N}$ (i.e., $\mathcal{D}=\{i\in\mathcal{N}:D_i=1\}$):

Let $\gamma$ denote the submodularity ratio. For a nondecreasing function, $\gamma$ ranges between $[0,1]$ and is $1$ if and only if the function is submodular. Similarly, the curvature, denoted by $\xi$, of a nondecreasing function ranges between $[0,1]$, and is $0$ if and only if the function is supermodular. As our objective function involves a system of simultaneous equations, evaluating its curvature and submodularity ratio directly is challenging. Instead, we focus on the upper bound for curvature and submodularity, and ensure that their values remain within $(0,1)$. Combining this result with bian2017guarantees of leads to:

A proof is provided in Appendix (ref). This proof is similar to kitagawa2023individualized. The first part of Proposition (ref) implies that the performance guarantee is a non-trivial bound. Although the curvature and submodularity ratio of our objective function are unknown, for a particular application, it is possible to evaluate them empirically. As a consequence,

where $\mathcal{O}(1)$ captures the $\mathbb{E}_{\varepsilon^{n}}[W_n(\Tilde{D}) \vert S,\sigma^{data}]$. Combining Eq.(ref) with Theorem (ref), we obtain our main theorem:

Theorem (ref) is our key result. The first term in Eq.(ref) characterizes the sampling uncertainty, whose convergence rate depends on the network size. The dependence upon the parameters in the utility function, network structure, and private information distribution are shown implicitly via the terms $C_1$ in Lemma (ref), $C_5$ and $C_6$ in Lemma (ref), and $C_4$ in Lemma (ref). The second term comes from the use of a greedy algorithm, and converges to a constant.

Empirical Application

We illustrate our proposed method using data from banerjee2013diffusion, which explores the impact of information provision on microfinance adoption. banerjee2013diffusion studies a microfinance loan program. This program was introduced by Bharatha Swamukti Samsthe (BSS), a non-governmental microfinance institution in India, and implemented across 43 villages in Karnataka. BSS invited influential units, such as teachers, leaders of self-help groups, and shopkeepers, to an informational meeting about the availability of microfinance (the treatment). In total, 1262 units were assigned treatment, an average of 25.75 per village. After the intervention, researchers collected data on the network structure and household characteristics—including access to electricity, latrine quality, and per capita counts of beds and rooms in all participating villages. The number of households in each village varied from 107 to 341, with 10 to 51 households per village receiving information about the program. The program commenced in 2007, and the survey of microfinance adoption was completed by early 2011. We treat each household’s decision to purchase microfinance as an equilibrium outcome within a simultaneous decision network game.

We consider each village as a distinct target population. Structural parameters in the payoff function for each village are estimated separately using the two-step maximum likelihood estimation (MLE) method of leung2015two. This setup assumes that the training data, which includes several villages, acts as a representative sample, with each village in the training dataset mirroring a corresponding village in the target population in terms of covariates and network structure.

In the first stage of our analysis, following arcidiacono2011conditional, we estimate the conditional choice probability using a flexible Logit approach (Chi-square goodness of fit test result is provided in Appendix (ref)). This includes each unit's covariates and their second powers, as well as the covariates of directly linked neighbors and interactions among these covariates, which is under the network decaying dependence assumption xu2018social. Although our estimator allows for incorporating covariates from neighbors at higher levels of linkage, we focus on directly linked neighbors' covariates in this estimation. We treat these estimates as the true parameters and assess the presence of strategic complementarity in each village. We find strategic complementarities in 16 of the 43 villages in the dataset\footnote{The indices of those 16 villages in the original data set are: 1, 4, 6, 7, 12, 14, 17, 18, 20, 24, 25, 29, 31, 39, 40, and 41. To enhance clarity, we discard their original indices and re-label them as villages 1 to 16.}, which are the focus of this exercise. We assume the policymaker utilizes all available covariates to determine the treatment allocation mechanism. We assume that the private information follows a logistic distribution, and we define the measure of closeness between units $i$ and $j$ to be $m(X_i,X_j) = \frac{1}{1+\vert X_i-X_j\vert}$.

Policy evaluation

In this application, the objective is to maximize engagement welfare, measured as the microfinance participation rate, evaluated at the minimal equilibrium under a treatment capacity constraint (as in Eq.(ref)) within our target population. To ensure comparability with the original study, we set the capacity constraint equal to the number of treatments used by Bharatha Swamukti Samsthe (BSS). We compare our method (`Robust') with two different treatment allocation regimes: the allocation rule adopted by BSS in the original study (`Original'), and a random allocation rule (`Random').

Table (ref) presents predicted village-level microfinance take-up probabilities under three different treatment allocations. For each allocation rule, we report both the upper and lower bounds of the prediction set. The first column lists the 16 villages that exhibit strategic complementarities. The second column (Sample Avg.) contains the empirical average take-up rate for these villages. The third column (Welfare under Original) shows the average adoption rates for the original treatment allocation used by BSS. Four villages—Villages 2, 3, 6, and 12—exhibit multiple equilibria under this rule. To further assess our proposed method's performance, we generate 500 random treatment allocations within the capacity constraint for each village. The average purchasing probability across these 500 allocations is reported in the fourth column (Welfare under Random). Under random allocation, multiple equilibria arise in Villages 2, and 9, highlighting that the occurrence of multiple equilibria can vary with the allocation method used. The share of households adopting microfinance according to the robust optimal treatment allocation is shown as Welfare under Robust, \textbf{where the multiple equilibria only presents in the Village 2}.

Note first that the equilibrium average share of households adopting microfinance under the original allocation closely tracks the observed data for all villages except for Village 7 \footnote{The goodness of fit test indicates that the estimation for Village 7, referred to as Village 17 in Table (ref), may not adequately fit the data, potentially due to inaccuracies in the first-stage Conditional Choice Probability (CCP) estimation.}. Second, we find that the equilibrium average share of households purchasing microfinance under random allocation is similar to the original BSS allocation method. When comparing our robust optimal treatment allocation regime with the original allocation rule, our method consistently outperforms the original rule in terms of both minimal and maximal equilibrium welfare. As depicted in Figure (ref), improvements in welfare with minimal equilibrium vary from $20\%$ to $270\%$. Notice that the welfare at the minimal equilibrium of our approach surpasses the maximal welfare under the other two approaches. This suggests that the information diffusion facilitated by the original treatment may not have significantly impacted adoption rates. Additionally, wang2024graph finds that households with higher centrality, such as the leaders selected by BSS, tend to have a lower borrowing probability compared to less central households. It is possible that more central households have greater access to alternative borrowing sources within their networks, thus diminishing their need for microfinance, and reducing the spillover effects through strategic interactions.

Extension

Complete Information Game

In a complete information setting, units observe all the characteristics of other units participating in the game. This means that units are informed of others' choices before making their own decisions, allowing them to play the best response to the observed actions rather than basing their actions on beliefs, as is common in a private information setting. As a consequence, unit $i$'s decision rule is:

One main distinction from incomplete information settings is that the solution concept transitions to a pure-strategy Nash equilibrium. A pure-strategy Nash equilibrium is defined by a set of actions $y^*=\{y_1^*,...,y_N^*\}$ such that

for any $y_i'\in\mathcal{Y}$ and for all $i\in\mathcal{N}$. We denote the set of all such equilibria as $\Sigma(X,D,G,\varepsilon)\coloneqq\{y^*\}$, given covariates $X$, treatment allocation $D$, network structure $G$, and the idiosyncratic shock $\varepsilon$. To simplify the notation, we subsequently refer to it as $\Sigma(\varepsilon)$. Let $\xi:\Sigma\rightarrow[0,1]$ denote the probability distribution over equilibria, and let $\Delta(\Sigma)\coloneqq\{\xi:\sum_{y^*\in\Sigma}\xi(y^*)=1\}$ denote the set of all the probability distributions.

In scenarios with strategic complementarity, there exists a maximal and a minimal Nash equilibrium, denoted by $ \begingroup \def\mathaccent#y##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{y} \endgroup ^*$ and $\underline{y}^*$. For our counterfactual analysis, which is analogous to the framework established in Theorem (ref) under an incomplete information setting, we propose the following:

The proof of Proposition (ref) mirrors that of Theorem (ref), with the primary modification being the substitution of Bayesian Nash equilibrium with Nash equilibrium. Computing the conditional choice probability differs from the previous analysis since it is no longer a simultaneous equation system. With complete information, the conditional choice probability is given by:

The above expression is hard to compute. To further simplify the computation, let us define event $A\coloneqq\left\{\exists y_{-i}:(1,y_{-i})\in \Sigma(\varepsilon) \right\}$ and event $B\coloneqq \left\{\exists y_{-i}, (0,y_{-i})\in \Sigma(\varepsilon) \right\}$. Given $\Pr(A\cap B^c\vert X,D,G) = \Pr(A\cup B\vert X,D,G)-\Pr(B\vert X,D,G)$, we hence have:

As a consequence, it is enough to compute $\Pr(Y_i=1\vert X,D,G, \begingroup \def\mathaccent#\lambda##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\lambda} \endgroup )$ and $\Pr(Y_i=0\vert X,D,G, \begingroup \def\mathaccent#\lambda##2{ \kern0.8\dimexpr\macc@kerna \overline{\kern-0.8\dimexpr\macc@kerna\macc@nucleus\kern0.2\dimexpr\macc@kerna} \kern-0.2\dimexpr\macc@kerna } \macc@depth\@ne \let\math@bgroup\@empty \let\math@egroup\macc@set@skewchar \mathsurround\z@ \frozen@everymath{\mathgroup\macc@group\relax} \macc@set@skewchar\relax \let\mathaccentV\macc@nested@a \macc@nested@a\relax111{\lambda} \endgroup )$, which are given by:

Let us define \(i^C\) as the complement of unit \(i\) and their neighbor set, i.e., \(i^C \coloneqq \mathcal{N} \setminus (\mathcal{N}_i \cup \{i\})\). Define \(y_{\mathcal{N}_i}\) as the collection of neighbors' choices of unit \(i\). Consequently, \(y_{-i}\) can be expressed as \((y_{\mathcal{N}_i}, y_{i^C})\), where \(y_{i^C}\) represents the choices of units in \(i^C\). For the optimization problems defined in Eq.(ref) (maximization) and Eq.(ref) (minimization), it is necessary to explore all possible equilibria for each value of \(\varepsilon\) within the network game. Given our utility function specification, the choice of unit \(i\) depends only on \(k \in i^C\) through the choices of units directly connected with \(i\). Thus, we can simplify the maximization problem in Eq.(ref) to:

with constraints:

These constraints (Eq.(ref) and Eq.(ref)) ensure that \((1, y_{\mathcal{N}_i}, y_{i^C})\) forms a Nash equilibrium. In the optimization, \(U_i(1, y_{\mathcal{N}_i}, X, D, G)\) does not depend directly on \(y_{i^C}\) but needs to confirm that \((1, y_{\mathcal{N}_{i}}, y_{i^C})\) is a Nash equilibrium for any given \(y_{\mathcal{N}_{i}}\). If for some \(y_{\mathcal{N}_{i}}\), multiple \(y_{i^C}\) ensure \(y_{-i}\) as a Nash equilibrium, the existence of any \(y_{i^C}\) that satisfies this condition is sufficient for our purposes. We search for \(y_{\mathcal{N}_{i}} \in \mathcal{Y}^{\vert \mathcal{N}_i \vert}\) that maximizes \(U_i(y_{\mathcal{N}_i}, X, D, G)\), denoted as \(y^*_{\mathcal{N}_{i}}\). Given the supermodular nature of our game, where neighbors' choices are strategic complements to unit \(j\)'s choice, we select \(y_{i^C}\) such that \((y_{\mathcal{N}_{i}}, y_{i^C})\) constitutes the largest Nash equilibrium for the given \(y_{\mathcal{N}_{i}}\), leveraging the increasing monotonicity between \(y_{\mathcal{N}_{i}}\) and \(y_{i^C}\). We then search the $y_{\mathcal{N}_{i}}$ that maximizes the objective function.

Conclusion

This paper proposes a method for constructing individualized treatment allocations to maximize equilibrium welfare robust to the presence of multiple equilibria in large simultaneous decision games with complementarity. Our approach, takes into account the inherent complexity introduced by the presence of multiple Nash equilibria, and the resulting incompleteness. We refrain from making assumptions about the equilibrium selection mechanism, which leads to both analytical and numerical challenges in evaluating counterfactual equilibrium welfare. Due to the inherent uncertainties in our model, we use the maximin welfare criterion to evaluate treatment allocation rules. This leads to treatment allocation rules that are optimized to maximize the worst-case equilibrium social welfare, ensuring their robustness. The use of a greedy optimization algorithm further enhances the applicability of our approach.

We acknowledge that several questions remain open, and there are multiple ways in which our work can be extended. First, we have not explored counterfactual analysis within the broader framework of general simultaneous decision games. Second, although we parametrize the utility function and the distribution of idiosyncratic shock in this work, adopting a non-parametric utility function and a non-parametric distribution of idiosyncratic shock could significantly enhance the robustness and applicability of our approach. Third, while we have assumed independence among idiosyncratic shocks, recent literature, such as grieco2014discrete and de2020testable, have begun to relax this assumption, suggesting another avenue for refining our model.

\linespread{1}