Individualized Treatment Allocation in Sequential Network Games

Individualized Treatment Allocation in Sequential Network Games

Keywords: Treatment choice, Markov random field, Gibbs distribution, variational approximation, mean field games, graphical potential game.

Introduction

The question of how best to allocate treatment to units interacting in a network is relevant to many policy areas, including the provision of local public goods bramoulle2007public, the diffusion of microfinance (banerjee2013diffusion; and akbarpour2025just), and vaccination (galeotti2013strategic; and KITAGAWA2023109). Obtaining an optimal individualized allocation, however, is often infeasible due to analytical and computational challenges. As a consequence, practical counterfactual policy analysis in the presence of network spillovers is limited to simulating and comparing outcome distributions or welfare values across a few benchmark candidate policies. This leaves the magnitude of the potential welfare gains of an optimal individualized assignment policy unknown.

Focusing on a class of social network models in which interacting agents play sequential decision games (jackson2002evolution; nakajima2007measuring; mele2017structural; and christakis2020empirical), this paper develops a method to obtain optimal treatment assignment rules that maximize a social welfare criterion. We consider an individualized allocation of binary treatments over agents who are heterogeneous in terms of their own observable characteristics, their network configurations, and their neighbors' observable characteristics. Each agent chooses a binary outcome so as to maximize their own utility. This choice depends upon the agent's own characteristics and treatment as well as their neighbors' characteristics, treatments and choices. The sequential decisions of randomly ordered agents induce a unique stationary distribution of choices nakajima2007measuring,mele2017structural. We specify the planner's welfare criterion to be the mean of the aggregate outcomes (i.e., the sum of the means of binary outcomes over all agents in the network) at the stationary distribution that is associated with a given treatment allocation. We aim to maximize the welfare evaluated at the stationary outcome distribution with respect to the individualized allocation of treatments. Consider, for example, targeted information provision in villages with the aim of increasing microfinance adoption, as discussed in banerjee2013diffusion. By comparing the stationary distribution of adoption decisions among units after they receive treatments, we determine whom to target in the village to maximize the adoption rate subject to a capacity constraint.

There are analytical and computational challenges to solving the maximization problem for optimal targeting. First, fixing an allocation of treatments, the sequential decision games induce a Markov random field (MRF) and the stationary outcome distribution has a Gibbs distribution representation. The analytical properties of the mean of the aggregate outcomes, however, are difficult to characterize. To approximate the joint distribution of outcomes, the literature on MRFs performs numerical methods such as Markov Chain Monte Carlo (MCMC) geman1984stochastic. If the size of the network is moderate to large though, MCMC can be slow to converge. It is, therefore, practically infeasible to perform MCMC to evaluate the welfare at every candidate treatment assignment policy in brute force search for optimal treatment allocation. Second, obtaining an optimal individualized assignment is a combinatorial optimization problem with respect to a binary vector of length $N$ with at most $\kappa \geq 1$ number of ones, where $N$ is the number of agents in the network and $\kappa$ is the capacity for the treatment. Brute force search yields the global optimum; however, it requires evaluating welfare under $\binom{N}{\kappa}$ different allocations.

We tackle these challenges by proposing a novel method for approximately solving the combinatorial optimization problem for individualized assignment. Our approach builds on variational approximation, which approximates the stationary distribution of the outcomes by a more tractable parametric family of distributions that minimizes the Kullback-Leibler divergence with the target Gibbs distribution. We then optimize the variationally approximated equilibrium welfare with respect to the assignment vector by a greedy algorithm, which assigns the treatment sequentially to the unit who generates the largest welfare gain given the previous assignments. The variational approximation step reduces the computational burden of running MCMC at each candidate policy. The greedy optimization further reduces the computational complexity of the combinatorial optimization, since it suffices to evaluate the equilibrium welfare only at the order of $N \times \kappa$ times.

In addition to the novel proposal of how to obtain targeting policy, this paper comes with a couple of new theoretical contributions. First, we provide a theoretical justification for maximizing the welfare criterion under a variational approximation by showing that the associated approximation gap of welfare shrinks to zero as the size of network increases. To show this claim, we derive and exploit a novel transportation inequality that bounds the welfare regret by the Kullback-Leibler divergence, and justifies the use of variational approximation to search for welfare-optimal treatment allocation. Second, we derive a theoretical regret bound to gauge the welfare performance of our greedy algorithm compared with the computationally infeasible brute force optimization.

To highlight this paper's unique contributions, we abstract from estimation of the structural parameters underlying the sequential decision game and assume that they are known. See geyer1992constrained, snijders2002markov, wainwright2008graphical, chatterjee2013estimating, mele2017structural, boucher2017my, and 10.1162/rest_a_01023 for identification and estimation of these parameters, and wang2024robust for how to incorporate estimation uncertainty into welfare regret bounds. In practical terms, our proposed method is useful for computing an optimal assignment of treatment, with point estimates of the structural parameters plugged-in.

To assess the performance of our proposal, we perform extensive numerical studies. In a small network setting where we can feasibly find a globally optimal policy by brute force, our simulations demonstrate that our greedy algorithm closely replicates a global optimum obtained by grid search. We augment these numerical studies with an empirical application that illustrates the implementation and welfare performance of our method. Specifically, we apply our procedure to Indian microfinance data that has been previously analyzed by banerjee2013diffusion. The data contains information about households in a number of villages, their relation to other households in their village, and whether they chose to purchase a microfinance product. For each village in the sample, we estimate the structural parameters of an assumed utility function using the method outlined in snijders2002markov. Plugging in the parameter estimates, we obtain an individualized treatment allocation rule using our algorithm. We compare the village welfare attained by our proposed algorithm with the welfare achieved by the centrality-based allocation performed by an NGO called Bharatha Swamukti Samsthe (BSS). As new empirical findings to the literature, the welfare comparisons show that targeting central units in a network as done by NGO is suboptimal, implying that in addition to the network structure, the magnitudes of strategic interactions and treatment spillovers are important factors to consider when designing the treatment allocation. For all $43$ villages in the sample, our method is associated with a higher welfare-level, with the magnitude of improvement varying from $9.82\%$ to $137.46\%$ (average improvement is $40.69\%$) of the welfare levels attained by the NGO's allocations. The magnitude of the welfare gain is substantial and demonstrates the benefits of individualized targeting under interference.

Literature Review

This paper intersects with several literatures in economics and econometrics, including graphical game analysis, MRF and variational approximation, discrete optimization of non-submodular functions, and statistical treatment rules.

Graphical game analysis has a long history in economics, see rosenthal1973class, kakade2003correlated, ballester2006s, roughgarden2010algorithmic, kearns2013graphical, babichenko2016graphical, de2018identifying, leung2020equilibrium and Parise2023graphon. The most relevant paper to our work are mele2017structural and christakis2020empirical, which study strategic sequential network formation. mele2017structural formulates the network formation game as a potential game monderer1996potential, and characterizes the stationary distribution of the network as a Gibbs distribution. We apply a similar technique to generate the stationary distribution of actions in our game, while the main focus is to develop a method for approximating optimal targeting in terms of equilibrium welfare. kashaev2023peer introduces a similar sequential structure into a discrete choice model with peer effect and estimates the model with panel data. badev2021nash extends the setting in mele2017structural to study how behavioral choices change the network formation. ballester2006s and galeotti2020targeting also study targeted interventions on networks, while the utility specification, the objective function, and the action space specified therein differ from ours.

MRF offer a way to represent the joint distribution of random variables as a collection of conditional distributions. We model an individual's choice of outcomes as the maximization of a latent payoff function that depends upon a treatment allocation and their neighbors' choices, and derive an MRF representation of the joint distribution of outcomes. wainwright2008graphical covers key results on variational approximation and MRF, and chatterjee2016nonlinear provides an approximation error bound to variational approximation applied to MRF for binary outcomes. To the best of our knowledge, this literature has not studied how to obtain an optimal intervention in terms of a criterion function defined on the joint distribution of outcomes characterized as a MRF.

Although it does not introduce sampling uncertainty, this paper shares some motivation with the literature on statistical treatment rules manski2004statistical, dehejia2005program. In econometrics and machine learning, welfare regret typically arises due to uncertainty surrounding the value of underlying parameters (i.e., estimation). In this work, regret arises from our use of variational approximation and of a greedy algorithm (i.e., identification). See stoye2009minimax,stoye2012minimax, hirano2009asymptotics,hirano2020asymptotic, chamberlain2011bayesian,chamberlain2020robust, tetenov2012statistical, and christensen2022optimal for decision theoretic analyses of statistical treatment rules. There is also a growing literature on learning individualized treatment assignments including kitagawa2018should, athey2021policy, kasy2021adaptive, kitagawa2021constrained, mbakop2021model, sun2021empirical, and adjaho2022externally, among others. These works do not consider settings that allow for the network spillovers of treatments or outcomes.

There are some recent works that introduce network spillovers into statistical treatment choice. viviano2025policy and ananth2020optimal consider treatment assignment rules taking into account the spillover effects of the treatments. In contrast to them, we consider spillovers through strategic interactions together with the treatment spillovers, and focus on fully individualized treatment assignment rules rather than a treatment rule as a constrained function of one's observable characteristics and network information. munro2023treatment studies targeting analysis taking into account spillovers through the market equilibrium. KITAGAWA2023109 considers the allocation of vaccines over an epidemiological network model (a Susceptible-Infected-Recovered network) in simple two-period transition model. wang2024robust studies targeting over agents who play a simultaneous game with multiple equilibria. In a different context of treatment choice, kitagawa2022stochastic applies variational approximation to a quasi-posterior distribution for individualized treatment assignment policies and studies welfare regret performances when assignment policies are drawn randomly from the variationally approximated posterior.

Model

Setup

Let $\mathcal{N}=\{1,2,..., N\}$ be the set of individuals in a network. Each unit has a $k$-dimensional vector of observable characteristics that we denote by $X_i$, $i\in\mathcal{N}$. Assuming that the support of $X_i$ is bounded, we normalize the measurements of $X_i$ to be nonnegative, such that $X_i\in\mathbb{R}_{+}^{K}$. Let $\mathcal{X}=(X_{1},...,X_{N})$ be a matrix that collects the characteristics of units in the population, and let $\mathcal{X}^N$ denote the set of all possible matrices $\mathcal{X}$. Let $\overline{X}\coloneqq(\max_{i\in\mathcal{N}}X_{1i},...,\max_{i\in\mathcal{N}}X_{ki})$. Let $D=(d_1,...,d_N)$ denote a vector of treatment allocation, where $d_i\in\{0,1\}$, $i\in \mathcal{N}$, indicates whether unit $i$ is treated ($d_i=1$) or untreated ($d_i=0$).

The social network is represented by an $N\times N$ binary matrix that we denote by $G=\{G_{ij}\}_{i,j\in\mathcal{N}}$, and that is fixed and exogenous in this work. $G_{ij}=1$ indicates that units $i$ and $j$ are connected in the social network, whilst $G_{ij}=0$ indicates that they are not. Let $\mathcal{N}_i$ indicate 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 for one 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$); $\underline{N}$ denotes the minimum number of edges for one unit in the network (i.e., $\underline{N}=\min_i\vert \mathcal{N}_i\vert$). As a convention, we assume there are no self-links (i.e., $G_{ii}=0,\:\forall i\in\mathcal{N}$). We further assume that the following property holds for the network structure$\colon$

The symmetric property of interaction in Assumption (ref) is a necessary condition for our interacted sequential decision game to be a proper potential game (Definition (ref) below) that can yield a unique stationary outcome distribution. The size of the spillover between units $i$ and $j$ depends not only upon $G_{ij}$ but also upon the treatment allocation and covariates, as we specify further below.

Let $y = (y_1, \dots, y_N) \in \mathcal{Y}^N$, $\mathcal{Y}=\{0,1 \}$, be a profile of actions of the $N$ individuals in the network. Let the preferences (utilities) of individuals be given by $\{U_i(y,\mathcal{X},D,G;\boldsymbol{\theta})\}_{i=1}^N$, which depend on own and others' actions $y$, planner's treatment allocation $D$, observable characterstics $\mathcal{X}$, network structure $G$, and the structural parameters $\boldsymbol{\theta}$. We specify the individual utility function as a quadratic function of own and neighbors' choices:

where we let coefficients ($\alpha_i,\beta_{ij}, \gamma_{ij})$ depend on their own covariates and treatment status as well as those of their neighbor unit $j$. Given a network $G$, covariates $\mathcal{X}$, and a treatment allocation $D$, the coefficient $\alpha_i$ on unit $i$'s choice represents the change in utility with respect to own action, and $\beta_{ij}+ \gamma_{ij}$ and $\gamma_{ij}$ represent the spillovers of unit $j$'s action to $i$'s utility when $y_i=1$ and $y_i=0$, respectively.

In our empirical application, we specify

and

where $m_{ij}=m(X_i,X_j)$ is a (bounded) nonnegative real-valued function of personal characteristics measuring the distance between the characteristics of units $i$ and $j$. As shown in Proposition (ref) and Theorem (ref) below, independent of their functional form specifications, $\gamma_{ij}$'s are not identifiable parameters since they do not appear in the stationary outcome distribution. $A_N$ is a term that controls the magnitude of spillovers to make the unknown parameters ($\theta_4,\theta_5,\theta_6$) independent of the size of the network; $A_N = \mathcal{O}(1/N)$ corresponds to a dense network and $A_N = \mathcal{O}(1)$ corresponds to a sparse network. Our framework does not restrict the density of network as far as the strategic interaction term, $\sum_{j\in\mathcal{N}_i}A_Nm_{ij}(\theta_5+\theta_6d_id_j)$, is bounded as network size increase.

Running example: Information Injection on Microfinance banerjee2013diffusion

A network corresponds to a village consisting of $N$ households connected by a friendship network \(G\). Each household \(i\) makes a microfinance adoption decision \(Y_i\). Treatment $d_i$ indicates whether household \(i\) attends an information seminar on available microfinance products. Household $i$'s adoption decision could depend on whether their friends had attended the information seminar due to the information diffusion through friendship (i.e., spillover effects). Moreover, their adoption decision can depend on whether their friends adopt or not. e.g., households whose friends become wealthy due to microfinance are attracted to microfinance more than those households whose friends do not adopt microfinance. The NGO observes: the household characteristics \(X\), and social network $G$, and chooses a treatment allocation \(D\) to maximize the overall adoption rate in the village.

Potential Game

Before introducing the sequential structure of the game and deriving the stationary outcome distribution, we first formulate potential games. The concept of a potential game has been used to study strategic interaction since rosenthal1973class, providing a tool to analyze the Nash equilibria of (non) cooperative games in various settings (e.g., jackson2010social, and bramoulle2014strategic).

The change in potentials from any player's unilateral deviation matches the change in their payoffs. Nash equilibria of the simultaneous move game with the pay-offs $(U_i(y_i,y_{-i}): i=1, \dots, N)$ must be the local maximizers of the potential. monderer1996potential states that

is a necessary and sufficient condition for a game featuring a twice continuously differentiable utility function to be a potential game. For the discrete outcome case, a condition\footnote{ Replacing the second-order derivative in Eq.(ref) with second-order differences. See monderer1996potential for further details.} that is analogous to Eq.(ref), is a necessary and sufficient condition for the existence of a potential function. chandrasekhar2014tractable, and mele2017structural also use a potential game framework to analyze Nash equilibria in a network game. This condition, however, requires that $\beta_{ij}=\beta_{ji}$ for all $i \neq j\in\mathcal{N}$, \footnote{ For a potential function to exist, after eliminating zero terms, we require that $U_i(1,0,y_{-ij})-U_i(1,1,y_{-ij})+U_j(1,1,y_{-ij})-U_j(0,1,y_{-ij})=0$. This implies that $-\beta_{ij}+\beta_{ji}=0$.} which restricts the spillover effect of unit $i$'s choice on unit $j$. By assuming our game is a potential game, we ensure the existence of at least one pure strategy Nash equilibrium monderer1996potential. The next proposition shows a potential function for the utility function specified in Eq. (ref).

Proof of Proposition (ref) is provided in Appendix (ref). Notice that the potential function is not the summation of the utility function across all units; summation of the utility function counts the interaction terms twice and violates Eq.(ref). As we show in Theorem (ref) below, the likelihood depends only on the potential function so that $\gamma_{ij}$ cannot be identified by the data.

By characterizing our game as a potential game, we can employ the stationary outcome distribution that we derived in Theorem (ref) to evaluate the planner's expected welfare.

Running example: Information Injection on Microfinance banerjee2013diffusion

To guarantee the existence of a potential function, our analysis imposes the structure of bilateral spillovers and their symmetries. The bilateral structure of the spillovers is a common specification in the peer effect model, e.g., nakajima2007measuring. The symmetry of the magnitude of the spillovers of household $i$, $\beta_{ij} = \beta_{ji}$, can restrict heterogeneity of units. For instance, in the context of microfinance program with the source of spillovers being consumption externality through comparisons with friends, the symmetry assumption holds if friends share unobserved heterogeneity such as prone to jealousy.

Sequential Decision Process

We now introduce sequential games and corresponding stationary outcome distributions. Let $t \in \{ 1,2, \dots \}$ index a period and $Y_i^t\in\mathcal{Y}$ be unit $i$'s choice (outcome) made at time $t$. Let $Y^t = (Y_1^t,...,Y_N^t ) \in \mathcal{Y}^N$ and we view $\{ Y^t: t = 1,2,\dots \}$ be a stochastic process with its realization denoted by $\{ y^t = (y_i^t)_{i=1}^N : t=1,2, \dots \}$. We denote the outcome vector excluding $y^t_i$ by $y_{-i}^t$.

In the initial period $t=0$, the social planner observes the connections in the social network and individuals' attributes, and decides the treatment allocation $D$. Then, at the beginning of every period $t=1,2,\dots$, an individual $i$ is randomly chosen from $\mathcal{N}$ by nature. The chosen unit $i$ can set own action (outcome) $y_i^t$ given the action profiles of the others in the previous period $y_{-i}^{t-1}$. All the other units maintain the same choices as in the last period.

Let $O^t \in \mathcal{N}$ indicate a unit chosen by the nature in period $t$. The next assumption restricts the dependence of $\{O^t: t=1,2,\dots\}$ on other variables in the model.

We assume that the selected unit $i$ in period $t$ chooses own action $y_i^t$ so as to maximize their current utility myopically, observing the attributes, treatment status, and the actions of their neighbors. Before doing so, however, the selected unit $i$ receives idiosyncratic shocks $(\varepsilon_{1it}, \varepsilon_{0it})$. Unit $i$ then chooses $Y_i^t=1$ if and only if:

The next assumption specifies the distribution of the idiosyncratic shocks.

Note that the Nash equilibrium of the potential game in Section (ref) is defined with the utilities without the utility shocks. Hence, the shocks $(\varepsilon_{1it},\varepsilon_{0it})$ added in the sequential setting should be interpreted as optimization errors of the selected individual, rather than her unobserved characteristics.

Under Assumption (ref), the conditional probability of unit $i$ choosing $Y_i^t=1$ is:

Given initial value $y^0$, sequence $[Y^1,...,Y^t, \dots]$ evolves as a Markov chain such that:

for $y\in\{0,1\}$. Under Assumptions (ref) to (ref), this Markov chain is irreducible and aperiodic,\footnote{ It is irreducible since every configuration could happen in a finite time given our assumption on the selection process. It is aperiodic since the selected unit has a positive probability to choose the same choice as in the last period.} which has a unique stationary distribution.

The individual decision process is a stochastic best response dynamic process blume1993statistical, which evolves as a Markov chain of decisions. jackson2002evolution shows that the sequential decision process plays the role of a stochastic equilibrium selection mechanism in the static potential game of Section (ref). lee2009multiple performs counterfactual predictions of policy interventions in the presence of multiple equilibria, with best response dynamics playing the role of an equilibrium selection mechanism.

Stationary Distribution

Given the Markov chain structure of $\{ Y^t \}$, the stationary joint distribution of the outcomes in our sequential decision game is given by the next theorem. We denote the random variable following the stationary oucome distribution by $Y \in \mathcal{Y}$.

Theorem (ref) shows that, given the parametric specification of the distribution of shocks (Assumption (ref)), the joint distribution of the outcomes is given by a Gibbs distribution characterized by the potentials.\footnote{hsieh2020specification obtains the same Gibbs distribution by introducing configuration specific shocks.} The set of Nash equilibria of the potential game corresponds to the set of modes of the stationary distribution.

We can view the joint distribution of the outcomes in the stationary as a Markov random field (see, e.g., bremaud2013markov). The random field $\{Y_i\}_{i=1}^N$ is a collection of random variables on the state space $\mathcal{Y}$. This random field is a Markov random field if for all $i\in\mathcal{N}$ and $y\in\mathcal{Y}^N$:

where $Y_{j \in \mathcal{N}_i}$ is the subvector of $Y$ restricted to $i$'s neighbors.

Given the specification of our utility function, the conditional distribution of $Y_i$ satisfies this Markov property. By connecting $Y$ to MRF, the Hammersley-Clifford Theorem clifford1971markov, besag1974spatial establishes that the joint distribution of $Y$ must follow a Gibbs distribution, which is consistent with the result of Theorem (ref).

The stationary distribution of the outcomes shown in Theorem (ref) is structural in the sense that the specification of the potential function in the Gibbs distribution relies on the functional form specification of the latent payoff function of agents. An advantage of the current structural approach is that we are transparent about the assumptions that we impose on the behavior of agents, on the structure of social interaction, and on the equilibrium concept. The structural approach, accordingly, disciplines the class of joint distributions of observed outcomes to be analyzed. As an alternative to the structural approach, we can consider a reduced-form approach where we model the conditional distribution of the observed outcomes given the treatment vector. Maintaining the family of Gibbs distributions, the reduced-form approach corresponds to introducing a more flexible functional form for the potential functions without guaranteeing that it is supported as a Nash equilibrium of the potential game.

Running example: Information Injection on Microfinance banerjee2013diffusion

The structure of sequential game introduced above can model the communication process among the villagers, e.g., in each short time window $t$, a villager can revise her/his decision of taking up the treatment by knowing the decisions of the friends. After many periods of interactions, the framework leads to the joint distribution of households' take-up decisions as presented in Theorem (ref). In practical terms, we view a snapshot of the take-up status $Y$ in a given period after treatment assignment as a draw from the stationary Gibbs distribution of dimension $N$. The sequential structure is a theoretical device to obtain the stationary outcome distribution, and we do not require the training sample for estimating the structural parameters to be panel data with observations of $\{ Y^t \}$.

Treatment Allocation

The objective of the social planner is to select a treatment assignment $D^* \in \{0, 1 \}^N$ that maximizes equilibrium mean outcomes subject to a capacity constraint that the number of individuals that are treated cannot exceed $\kappa > 0$:

where $\mathbb{E}_P[Y_i\vert \mathcal{X},D,G;\boldsymbol{\theta}]$ is the expectation with respect to the stationary joint distribution shown in Theorem (ref).

In this work, we assume that the structural parameters $\boldsymbol{\theta}$ underlying the potential game are given and abstract from uncertainty in parameters estimation. There have been several estimation approaches studied in the literature which utilize MCMC geyer1992constrained,snijders2002markov, pseudo-likelihood besag1974spatial,boucher2017my, and variational approximations wainwright2008graphical.

Our proposal fits to the following scenario of empirical policy design. First, a planner estimates the structural parameters using a training sample of networks that have implemented the treatments. Next, using our proposed method, the planner informs optimal allocations of treatments to the networks which have not implemented the treatments, assuming that the structural parameters are invariant among them.

Welfare Approximation

We cannot directly maximize the equilibrium welfare in $D$; instead, we seek to maximize the approximated welfare. We now discuss what prevents us from maximizing the equilibrium welfare.

The objective function $W(D)$ from Eq.(ref) is:

We define the partition function as $\mathcal{Z}\coloneqq \sum_{\delta\in\{0,1\}^N} \exp[\Phi(\delta,\mathcal{X},D,G;\boldsymbol{\theta})]$. Since the partition function $\mathcal{Z}$ sums all possible configurations (of which there are $2^N$), it is infeasible to evaluate the expectation when $N$ is moderate to large, e.g., when $N> 276$, there are more configurations than atoms in the observable universe de2020econometric.

Given this well-known problem, we seek to approximate the distribution $P$ using a tractable distribution $Q$. Let $\mu_i^P\coloneqq\mathbb{E}_{P}[Y_i\vert \mathcal{X},D,G]$ and $\mu_i^Q\coloneqq\mathbb{E}_{Q}[Y_i\vert \mathcal{X},D,G]$. Since we have:

The approximation error can be bounded by:

In what follows, we bound the approximation error in Eq. (ref) first by the Wasserstein distance (Lemma (ref)) and next by the Kullback–Leibler (KL) divergence $\mathbb{KL}(Q\Vert P)$ (Theorem (ref)).

Proof of Lemma (ref) is provided in Appendix (ref). To obtain an upper bound of the Wasserstein 1-distance in terms of $\mathbb{KL}(Q\Vert P)$, we develop a version of Talagrand's transportation inequality for Gibbs distributions.\footnote{A distribution $P$ on $\mathbb{R}^N$ satisfies Talagrand's transportation inequality with constant $C>0$ if for any probability measure $Q$ absolutely continuous w.r.t. $P$, we have \refstepcounter{equation} $$W_2(P,Q)\leq C\sqrt{\mathbb{KL}(Q\|P)}, \hspace{1cm}(\theequation)$$ where $W_2(P,Q)= \inf_{\omega \in \Omega(P,Q)} \mathbb{E}_\omega\bigl[d^2_{\mathrm{H}}(Y, Y')\bigr]$ . Since $d_H(Y,Y')\leq d_H^2(Y,Y')$ holds for any $Y,Y' \in \{0,1\}^N$, Talagrand's transportation inequality implies $W_1(P,Q)\leq W_2(P,Q)\leq C\sqrt{\mathbb{KL}(Q\Vert P)}$ for any $Q$ absolutely continuous w.r.t. $P$.} Availability of Talagrand's inequality hinges on the following assumption called as Dobrushin’s condition dobrushin1970prescribing, which restricts the magnitude of the spillover effects:

With the utility specification of Eq.(ref) and (ref), this condition can be rewritten as:

With Dobrushin's condition added, we obtain the following key lemma:

Proof of Lemma (ref) is provided in Appendix (ref). To our knowledge, the trasportation inequality in this lemma is new and can be of independent interest. Combining Lemmas (ref) and (ref), we have the following theorem that bounds the welfare approximation error by the KL divergence.

This novel transportation inequality links the approximation error of the welfare to the Kullback–Leibler divergence. A similar inequality holds for a class of social welfare functions as long as their approximation errors can be bounded by the Wasserstein distance. Given such bound, in the next section, we obtain a best approximation of $P$ by $Q$ by minimizing $\mathbb{KL}(Q\Vert P)$ with respect to $Q$ subject to that $Q$ belongs to a simple class of distributions of $Y$. The reason that we focus on minimizing the KL divergence rather than the Wasserstein distance is because minimizing the KL divergence is computationally more tractable when $P$ is a Gibbs distribution. This computational advantage is well known and exploited in the literature of variational approximation for exponential random graphs wainwright2008graphical; see Section (ref) below.

Mean Field Method

Using an independent Bernoulli distribution to approximate the target distribution is called naive mean field approximation wainwright2008graphical. This method can be viewed as a specific method in the general approach of variational approximation, which approximates a complicated probability distribution by a distribution belonging to a class of analytically tractable parametric distributions. In Eq.(ref), $P$ corresponds to the target distribution to be approximated and $Q$ corresponds to a simple parametric distribution approximating $P$. We consider the class of independent Bernoulli distributions as a parametric family for $Q$, since it delivers a feasible and fast optimization algorithm and the magnitude of its approximation error is already established in the literature.

The probability mass function of an independent Bernoulli distribution $Q$ is expressed as:

Let $\mu^Q$ be an $N\times 1$ vector that collects $\{\mu_i^Q\}_{i=1}^N$. The Kullback–Leibler divergence between $Q$ and $P$ equals:

where $\alpha\coloneqq( \alpha_i)_{i\in\mathcal{N}}'$ is a $N\times 1$ weighting vector and $\mathcal{B}\coloneqq(\beta_{ij})_{i,j\in\mathcal{N}}$ is a $N\times N$ matrix. The last line holds since the diagonal entries of $\mathcal{B}$ are zero and

Recall $\mathcal{Z}$ in Eq.(ref) sums over all possible configurations. $\mathcal{Z}$ is, therefore, independent of $Y$ (i.e., it is constant). We define $\mathcal{A}(\mu^Q,\mathcal{X},D,G)$ as:

As such, minimizing $\mathbb{KL}(Q\Vert P)$ is equivalent to maximizing $\mathcal{A}(\mu^Q,\mathcal{X},D,G)$ wainwright2008graphical. We denote by $\Tilde{\mu}$ the result of the following optimization:

Then the approximated distribution $Q^*$ is expressed as:

The first order condition of Eq.(ref) is:

Despite the fact that our approach speaks to a general specification of the utility function, we use the specification of Eq.(ref) and (ref) to derive the theoretical results in the following sections for illustrative purposes. Although the objective function (Eq.(ref)) is non-concave, the next proposition shows that it has a unique maximizer.

Proof of Proposition (ref) is provided in Appendix (ref). The global optimum is obtained by solving the first-order conditions (Eq.(ref)) iteratively and exploiting the contraction mapping property that we can show under Assumption (ref). The iteration algorithm has been used in the literature wainwright2008graphical, while to our knowledge, the conditions for the contraction mapping property and convergence to the global optimum shown in Proposition (ref) are new.

The following theorem shows how the approximation error due to variational approximation (measured in terms of the Kullback-Leibler divergence) depends on the size of the network.

This theorem follows as a corollary of chatterjee2016nonlinear. Proof of Theorem (ref) is provided in Appendix (ref). Theorem (ref) shows that the upper bound on the approximation error depends not only on the size of the network $N$ but also on the magnitude of the spillover effect $A_N \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 $. However, by our construction, $A_{N}\bar{N}$ is set constant independent of $N$ regardless of whether the network is dense ($A_{N} = 1/N$) or sparse ($A_{N}$ is constant), Theorem (ref) clarifies that the leading term in the approximation error bound Eq.(ref) grows at $\mathcal{O}(N)$.

Recall from Eq.(ref) and Eq.(ref) that the error due to approximating the welfare at $P$ by the welfare at $Q^*$ can be bounded by $\sqrt{\mathbb{KL}(Q^*\Vert P)}\leq \mathcal{O}(N^{1/2})$. If our objective is to maximize $\frac{1}{N}\sum_{i=1}^N \mu_i^P$, Theorem (ref) implies that the approximation error of $\frac{1}{N}\sum_{i=1}^N \mu_i^{Q^{\ast}}$ can be bounded from above by $\frac{1}{N}\sqrt{\mathbb{KL}(Q^*\Vert P)}\leq \mathcal{O}(N^{-1/2})$, which converges to zero as $N$ becomes large.

Implementation

Having shown how to approximate the average outcome of the Gibbs distribution using the mean field method, this section proposes an algorithm to optimize the approximated welfare in treatment allocation $D$.

Suppose that the set of feasible allocations is subject to a capacity constraint, $\sum_{i=1}^N d_i\leq \kappa$, where $\kappa\in\mathbb{N}_{+}$ specifies the maximum number of units that can be treated. We denote the set of feasible allocations by $\mathcal{D}_{\kappa} \equiv \{D\in\{0,1\}^N:\sum_{i=1}^N d_i\leq \kappa\}$, and the approximated welfare by:

We seek to maximize the approximated welfare:

As shown in the Eq.(ref), $\{\Tilde{\mu}_i\}_{i=1}^N$ is a large non-linear simultaneous equation system. The approximated mean value $\Tilde{\mu}_i$ of each unit $i$ depends upon the approximated mean value $ \Tilde{\mu}_{j}$ and the treatment assignment $d_j$ of her neighbor, unit $j$. Hence, the optimization problem (Eq.(ref)) becomes a complicated combinatorial optimization. We propose a greedy algorithm (Algorithm (ref)) to solve this problem heuristically.

The idea of our greedy algorithm is to assign treatment to the unit that contributes most to the welfare objective, repeating this until the capacity constraint binds. Specifically, in each round, Algorithm (ref) computes the marginal gain of receiving treatment for each untreated unit. We refer to the unit whose treatment induces the largest increase in the approximated welfare as the most influential unit in that round. We provide a theoretical performance guarantee for our greedy algorithm in Section (ref), and numerically examine its performance in Section (ref).

In Algorithm (ref), we use a variational approximation method to compute $\Tilde{\mu}$ for each assignment rule and for each round (i.e., there are $\mathcal{O}(N)$ operations in each round). Alternatively, MCMC can be used to simulate the mean value $\mu$ of the unique stationary distribution (Eq.(ref)) instead of computing the variationally approximated $\Tilde{\mu}$. Since MCMC may require exponential time for convergence chatterjee2013estimating though, simulating $\mu$ is infeasible for a large network (i.e., MCMC needs to be run $\mathcal{O}(\kappa N)$ times).

Theoretical Analysis

In this section, we analyze the regret of the treatment allocation rule computed using our greedy algorithm. Given $D^*\in\operatorname*{arg\,max}_{D\in\mathcal{D}_{\kappa}}W(D)$ is a maximizer of $W(D)$, then $W(D^*)$ denotes the maximum value of $W(D)$. Regret is the gap between the maximal equilibrium (oracle) welfare $W(D^*)$ and the equilibrium welfare attained at the treatment allocation rule computed using our greedy algorithm $W(D_G)$. We decompose regret into four terms:

The first term corresponds to the approximation error of using variational approximation; the second term comes from using the maximizer of the approximated equilibrium welfare $\Tilde{D}$; the third term comes from using our greedy algorithm instead of using the maximizer of the variationally approximated welfare; and the last component is again introduced by using the approximated equilibrium welfare $\Tilde{W}(D)$.

By Theorem (ref), the first term in the right-hand side of Eq.(ref) can be bounded above at the order of $O(N^{1/2})$. The second term in the right-hand side of Eq.(ref) captures the regret of the approximated welfare due to greedy optimization. To obtain a nontrivial analytical bound for it, we assume nonnegative treatment and spillover effects as stated in the next assumption.

Assumption (ref) (i) restricts the signs of both own treatment effects and spillover treatment effects, while (ii) constrains the magnitude of the own treatment effects in relation to the network size. These sign restrictions on $\bm{\theta}$ are plausible in many applications, such as allocating vaccinations to increase social health, providing discount coupons to stimulate purchases, and assigning tax auditing to reduce tax evasion.

Combining Eq.(ref), Eq.(ref), and Eq.(ref), we obtain the next theorem:

Theorem (ref) is our key result. It characterizes the guaranteed convergence rate of the overall regret, showing its dependence on the network complexity and the network size. The dependence upon the parameters in the utility function is shown implicitly via the terms $C_1$ and $C_2$ in Theorem (ref). If we examine the average equilibrium welfare, then the regret bound becomes:

The first term is the approximation error and shrinks to zero as $N$ goes to infinity. Given that $\Tilde{W}(\Tilde{D})$ can be a function of $N$, the regret that is associated with our greedy algorithm can converge to a constant.

Data and Applications

We illustrate our proposed method using the dataset of banerjee2013diffusion, which examines take-up of a microfinance initiative in India.\footnote{The dataset is available at \href{https://doi.org/10.7910/DVN/U3BIHX}{https://doi.org/10.7910/DVN/U3BIHX}.} A detailed description of the study can be found in the original paper. This study features 43 villages in Karnataka that participated in a newly available microfinance loan program. Bharatha Swamukti Samsthe (BSS)---an Indian non-governmental microfinance institution administering the initiative---provided information about the availability of microfinance and program details (the treatment) to individuals that they identified as `leaders' (e.g., teachers, shopkeepers, savings group leaders, etc.) so as to maximize the number of households that chose to adopt the microfinance product. The data provide network information at the household level (network data is available across 12 dimensions, including financial and medical links, social activity, and known family members) for each village. We use all available households characteristics that are available in the dataset (quality of access to electricity, quality of latrines, number of beds, number of rooms, the number of beds per capita, and the number of rooms per capita) as covariates. The program started in 2007, and the survey for microfinance adoption was finished in early 2011. We treat each household's choice about whether to purchase microfinance or not as observations drawn from a stationary distribution of the sequential game.

The most common occupations in these villages are in agriculture, sericulture, and dairy production banerjee2013diffusion. In addition, these villages had almost no exposure to microfinance institutions and other types of credit before this program. We allow the parameters of our utility function to be different across villages, and estimate them for each village using Markov Chain Monte Carlo Maximum Likelihood snijders2002markov.\footnote{MCMC Maximum Likelihood evaluates the score function by MCMC at each Newton-Raphson step. The number of likelihood evaluations required is typically much smaller than $\mathcal{O}(N\kappa)$, the number of welfare evaluations needed for greedy optimization for treatment allocation.} We also note that each household is connected to approximately $10$ others on average across all of the $43$ villages. Comparing this with the total number of households in each village (there are between $107$ and $341$ households in each village), we find that the household network in each village is a sparse network. We, therefore, choose $A_N=1$ in our simulation and application. In addition, we choose $m(X_i,X_j) = \frac{1}{1+\vert X_i-X_j\vert}$, which is a monotonically decreasing function in the metric between $X_i$ and $X_j$.

Simulation Exercises

In this section, we evaluate the performance of our greedy algorithm in simulation exercises. We consider small networks of size $N=5,7,9,11,13$ or $15$ to compute the distribution of outcomes at every possible assignment vector, and use a brute force method to find an optimal treatment allocation.

We design the simulation setting to be relevant to empirical settings. For each choice of $N$, we randomly select $N$ households from Village 1 (as indexed in the dataset of banerjee2013diffusion) and treat them as the population of a small network, maintaining the covariates of the sampled households and setting the estimated structural parameters in Village 1 as the truth. In estimation of the structural parameters, we adopt the specification of the utility function (Eqs. (ref) and (ref)). The parameter estimates in Village 1 satisfies Dobrushin's condition. To match the network structure with the empirical application, we estimate a binary regression of network formations, $G_{ij}=\mathbbm{1}\{\beta_0+\beta_1\vert X_i-X_j \vert+\epsilon_{ij}\geq 0\},$ $\epsilon_{ij} \sim_{iid} Logit$, using the whole observations from Village 1. We then generate $100$ networks of size $N$ (keeping the sampled households fixed) from the estimated network formation model. For each of these networks, we compute an optimal treatment allocation with our method subject to the capacity constraint of $\kappa = \lceil0.3N\rceil$, and simulate the corresponding equilibrium welfare. We then report its average over these $100$ networks to assess the performance of our method. We then repeat the same simulation exercise for Village 4 (as indexed in the dataset of banerjee2013diffusion). The reason that we chose Village 4 is because the structural parameter estimates of Village 4 does not satisfy Dobrushin’s condition. So this case in comparison to Village 1 offers an illustration of how our proposed method performs when Dobrushin's condition fails.

First, we consider all possible treatment allocations subject to the capacity constraint and perform brute force search to find an optimal assignment. For instance, when $N=15$, the number of feasible assignment vectors is $32,768$. We compute the joint distribution of outcomes at each possible treatment allocation by applying the joint probability mass function of the Gibbs distribution (Eq.(ref)). Second, to assess the welfare loss from implementing the variational approximation, we evaluate the regret of a treatment assignment rule that is obtained by maximizing the variationally approximated welfare over every feasible treatment allocation meeting the capacity constraint (without greedy optimization). We label this method of obtaining the optimal treatment assignment as brute force with variational approximation (BFVA). Third, we perform random allocation that assigns treatment to a fraction $\kappa$ of units independently of personal characteristics and network structure. Fourth, we compute the Bonacich centralities\footnote{Following ballester2006s, Bonacich centrality is defined as follows: consider a network \(g\) with adjacency \(n\)-square matrix \(G\) and a scalar \(a\) such that $M(g,a) = \bigl[\mathbf{I} - aG\bigr]^{-1}$ is well‐defined and nonnegative, where $\mathbf{I}$ denotes the $N$-square identity matrix. The vector of Bonacich centralities of parameter \(a\) in \(g\) is $ b(g,a) = \bigl[\mathbf{I} - aG\bigr]^{-1}\,\mathbf{1}. $ Given that $a$ is a nuisance parameter, we set $a=0.1$, following galeotti2020targeting.} for each network, and assign treatment to units in the order of decreasing centrality until the capacity constraint binds. We labeled this method of obtaining the optimal treatment assignment as Centrality.

Figure (ref) shows the simulated average performances of the three aforementioned methods and the greedy targeting rule in terms of in-sample average welfare, with details summarized in Table (ref) in the Appendix. On the left-hand side of Figure (ref), we compute the regret for each method scaled by the average welfare level of the global optimal allocation. The right-hand side of Figure (ref) shows the results obtained using the parameters estimated from Village 4, which allow us to evaluate performance when Assumption (ref) is violated.

Figure (ref) shows that our greedy algorithm performs as well as the brute-force method in a small-network setting, indicating strong performance of our approach. Moreover, our greedy algorithm can achieve the same performance as BFVA, which means that using our greedy algorithm has a negligible effect upon regret. We also observe that targeting based on Bonacich centrality performs similarly to random allocation.

From the right-hand side of Figure (ref), we observe that our method continues to perform as well as the optimal allocation. The regret associated with centrality and random allocation methods increases when Assumption (ref) is violated.

Empirical Application

Our target in this application is to maximize the participation rate of microfinance (4 years after program assignment) given a capacity constraint on treatment (i.e., Eq.(ref)); we set our capacity constraint equal to the number of households that BSS contacted in the original study. For each iteration of the procedure, we set the number of draws in the Gibbs sampling procedure equal to $200N^2$.

Table (ref) shows the average probability of taking up microfinance observed in each village (column Sample Avg.) and the prediction of village-level take-up probability obtained from our MCMC-MLE estimates (column Welfare under Original). We refer to the former as the Sample Average and the latter as the Welfare under Original Allocation. We provide standard errors for the Sample Average, which we calculate using network HAC estimation (leung2019inference; and kojevnikov2021limit). We compute Welfare under Original Allocation by substituting the estimated parameters and the original treatment allocation (used by BSS) into our model. To further evaluate the performance of our proposed method, we randomly draw 100 treatment allocations that satisfy the capacity constraint in each village, and calculate the probability of purchasing microfinance for each allocation. We refer to the average probability over these draws as the Welfare under Random Allocation. In addition, we compute welfare based on treatment assignments determined by Bonacich centrality for each network, which we denote as the Welfare under Centrality. We then implement our proposed method with the estimated parameters to find the optimal treatment allocation rule. We refer to the share of households adopting microfinance according to the optimal treatment allocation and our model as the Welfare under Greedy Allocation. Table (ref) records these statistics for the $43$ villages in the dataset, with the final column comparing the Welfare under our Greedy Allocation with the Welfare under Original Allocation. It also contains bootstrap standard errors for welfare based on 100 bootstrap samples for each village. The bootstrap samples are obtained by drawing outcomes from the MCMC stationary distribution simulated under the structural parameters estimated with the original sample. To obtain the standard errors for the Welfare under Greedy Allocation, for each bootstrap sample, we estimate the structural parameters and simulate welfare under a greedy optimal allocation.\footnote{If an optimal welfare is differentiable in the structural parameters and the greedy optimal allocation under the true structural parameter value is unique, we expect the bootstrap delta method applies to yield asymptotically valid standard errors.}

First, we note that the estimated average share of households who adopt microfinance under the MCMC-MLE estimates fits the data well for all $43$ villages. Second, we find that the centrality-based allocation delivers a level of welfare comparable to both the original treatment allocation and the random allocation. This result suggests that the centrality-based approach may fail to capture the spillover effects arising from strategic interactions. It also implies that the leaders that BSS selected were not particularly effective in encouraging take-up by other households. Third, we find that our proposed method compares favourably to the method that is implemented in banerjee2013diffusion, yielding a treatment allocation that attains a higher welfare level. As shown in Table (ref), the welfare gain is positive for all $43$ villages (exceeding $100\%$ in some villages). This indicates that if the specification of the sequential network game is correct in the context of the current application, individualized treatment allocation that takes into account network spillovers can generate large welfare gains. Existing empirical work around social networks has not quantified the welfare gain from individualized treatment allocation under spillovers due to a lack of feasible procedures to obtain an optimal individualized assignment policy. In contrast, we uncover evidence of the significant welfare gains that can be realized by exploiting network spillovers.

To highlight the computational advantage of our proposed method, we compare the computational time required for the variational approximation with the MCMC approach for computing the equilibrium welfare. To compute an approximation of the welfare value for a treatment allocation over a village of $175$ villagers, the variational approximation takes $0.04$ seconds, whereas MCMC requires $15$ seconds. This difference translates into a total time gap of approximately $20$ hours when the welfare criterion is evaluated $N \cdot \kappa \approx 4{,}500$ times with $\kappa = \lceil 0.3N \rceil$.

akbarpour2025just shows that the optimal treatment allocation rule under a capacity constraint may lose any advantage over random allocation if the policymaker slightly relaxed capacity constraint by providing treatment to a few additional households. The objective in that paper, however, is to maximize information diffusion in the context of a large network asymptotic. Therefore, adding a few more seeds at random increases the probability that at least one of them will be close to the well-connected center nodes to making targeting relatively unimportant. This is distinct from our target, where we focus on the proportion of households that purchase microfinance in equilibrium.\footnote{In addition, beaman2021can points out that the previous results only hold under three conditions: agents must adopt a new behavior after a single exposure to someone else who has adopted in the network; the time period for adoption is sufficiently long; and social interaction within the network is frequent. If any of the three criteria fail, then targeting may be necessary to prevent information frictions from curbing widespread technological diffusion.} Compared with maximizing information diffusion, being connected to a central node may even reduce the probability of adopting microfinance, since central units typically do not adopt microfinance given there is a substitution effect between local borrowing and microfinance.

Conclusion

In this work, we have introduced a novel method to obtain individualized treatment allocation rules that maximize the equilibrium welfare in sequential network games. To handle the analytical and computational challenges of analyzing the stationary distribution of outcomes, we use variational approximation and maximize the approximated welfare criterion using a greedy maximization algorithm over treatment allocations. We bound the welfare regret, taking into account the approximation errors of the variational approximation and of the greedy maximization.

There are several questions remained to be studied. First, we assume that the network structure does not change in response to the treatment allocation. One could apply the framework of badev2021nash to incorporate joint determination of network formation and individual choices into policy targeting, but we leave the details for future research. Second, we may want to perform inference for the welfare at the obtained assignment rule, taking into account the uncertainty of parameter estimates and a potential winner's bias andrews2020inference. Third, we have used a naive mean field method in this work. As is mentioned in wainwright2008graphical, using a structural mean field method can improve the performance of an approximation and can lead to better welfare performance. Fourth, we assume that the network structure in our data is perfectly measured, which may not hold in practice. This issue has been examined in lewbel2025estimating.

Additional Table

Lemma and Proposition

Preliminary Lemma

In this section, we collect various lemmas that we use to prove our main results. We first denote the matrix norms induced by vector norms as $\Vert A\Vert_{a,b}\coloneqq \sup\{\Vert Ax\Vert_{b}:\Vert x\Vert_a\leq 1\}$. Let $p$ be a generic measure with support $\mathcal{Y}^N$, and denote the conditional distribution of $Y_i$ given $Y_{-i}$ as $p_i(Y_i\vert Y_{-i})\coloneqq \frac{p(Y)}{\sum_{Y_{i}\in\mathcal{Y}}p(Y_i,Y_{-i})}$ given the choices of the other units $Y_{-i}$. A matrix $A=(a_{ij})_{i,j\le N}$ is a coupling matrix if it satisfies $a_{ii}=0$ for all $i$ and for $i\neq j$ \[ \bigl\|p_i(\cdot \mid Y_{-i}) \;-\; p_i(\cdot \mid Y_{-i}')\bigr\|_{\mathrm{TV}} \;\le\; a_{ij}, \] whenever $Y,Y'\in \mathcal{Y}^N$ differ only at the $j$-th coordinate.

Proof of Proposition (ref)

Theorem

Proof of Theorem (ref)

We first state Theorem (ref) that we use to prove Theorem (ref).

Proof of Theorem (ref)