Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
126,929 characters · 21 sections · 133 citation commands
Policy Targeting under Network Interference
{\it Keywords:} Causal Inference, Welfare Maximization, Spillovers, Social Interactions. \\ {\it JEL Codes:} C10, C14, C31, C54.
\onehalfspacing
Consider a policymaker who must use a quasi-experiment, such as an existing experiment or observational study, to design a decision rule (policy) that assigns treatments based on observable characteristics. The main challenge is treating an individual may generate spillovers on her friends or neighbors. Spillovers may, in turn, affect the design of the optimal policy. This paper studies the problem of allocating treatments in the presence of spillover effects to maximize welfare, using information from a quasi-experiment. Applications include cash-transfer programs, education programs, and information campaigns, among others egger2019general, opper2016does, bond201261.
A (large) population of $n$ individuals is connected in a single network. Treatments generate spillovers to neighbors in the network (i.e., network interference). Researchers randomly sample $n_e \ll n$ units in a (quasi)experiment and randomize treatments among sampled individuals and their neighbors (the remaining units are not necessarily in the experiment). They then collect sampled individuals' covariates, treatment assignments, outcomes, neighbors' covariates, and assignments. The population network is not necessarily observed. The goal is to estimate a treatment rule to deploy on the entire population. Consider the example of targeting information to increase insurance take-up in a region subject to environmental disasters cai2015social. Using variation from experiment participants sampled from a random subset of villages in this region, we estimate whom to target in the entire region.
The first challenge is that the population network may be unobserved due to the cost of collecting network data on large populations. Researchers may only observe neighbors' information about the experiment participants. Collecting network information from the individuals in the entire population, such as a region or country, is often costly or infeasible breza2017using. Motivated by this, I develop a method that does not require we observe the population network. I allow for arbitrary constraints on the policy space, such as informational constraints. A second challenge is treatment effects heterogeneity. I leverage the assumption that spillovers occur through the number of treated neighbors, as is often documented in applications, and allow for treatment effects heterogeneity in arbitrary individual characteristics (e.g., covariates and number of neighbors).\footnote{Models consistent with this restriction are models of exogenous and anonymous spillover effects; see, e.g., manski2013identification. For instance, cai2015social leverage a two-stage experimental design to show “the network effect is driven by the diffusion of insurance knowledge" (i.e., treatment) “rather than purchase decisions" (i.e., outcome) cai2015social, consistent with the model proposed in this paper. Other examples of empirical applications using models consistent with our model include sinclair2012detecting, duflo2011peer, muralidharan2017general, where for the second reference, networks can be considered groups of classrooms with units within each classroom being fully connected. }
The proposed method, which I call Network Empirical Welfare Maximization (NEWM), estimates the welfare as a function of the policy using arbitrary estimators (e.g., based on machine learning). It then solves an exact optimization procedure over the policy space. I interpret policy targeting as a treatment choice problem manski2004, KitagawaTetenov_EMCA2018, athey2017efficient, here studied in the context of network interference. I evaluate the method's performance based on its maximum regret, that is, the difference between the largest achievable welfare and the welfare from deploying the estimated policy.
From a theoretical perspective, this paper makes three contributions: (i) it derives the first set of guarantees on the regret for treatment rules with spillovers; (ii) it introduces an estimation procedure with fast convergence rates of regret with machine-learning (non-parametric) estimators and networked units; and (iii) it shows that for a large class of policy functions, the optimization problem can be written as a mixed-integer linear program, solved using off-the-shelf optimization routines.
The analysis proceeds as follows. First, I discuss the identification of social welfare under interference. Identification relies on the unconfoundedness of treatment assignments and of the sampling indicators. I then study semi-parametric estimators for the welfare and analyze the performance of the estimated policy. I show that under regularity conditions, the regret of the estimated policy scales at the rate $1/\sqrt{n_e}$, whenever the maximum degree (i.e., the number of neighbors) is uniformly bounded de2018identifying. If the maximum degree grows with the population size, the rate depends on the degree, and converges to zero when the degree grows at an appropriate slower rate than $n$. Finally, I derive lower bounds that guarantee a maximin convergence rate of the regret with a bounded degree. Throughout the analysis, I do not impose assumptions on the (joint) distribution of characteristics used for targeting and on the network other than restrictions on the maximum degree.
A condition for these results to hold is that the optimization procedure achieves the in-sample optimum. I guarantee it by showing that we can cast the problem in a mixed-integer linear program.
The derivations present several challenges: (i) individuals depend on neighbors' assignments that I control through contraction inequalities; (ii) statistical dependence invalidates standard symmetrization arguments wainwright2019high; and (iii) in the presence of observational studies with networks, machine-learning estimators may present non-vanishing bias even when using existing methods athey2017efficient. For (iii), I introduce a novel cross-fitting algorithm for networked observations and characterize its properties.
I study the numerical properties of the method using data from cai2015social. I design a policy that informs farmers about insurance benefits to increase insurance take-up. The NEWM method leads to (out-of-sample) improvements in insurance take-up up to thirty percentage points compared to methods that ignore network effects KitagawaTetenov_EMCA2018, athey2017efficient. I obtain these improvements despite not using network information for the design of the policy. Finally, I present several extensions, including trimming when individuals present poor overlap due to a large maximum degree, different target, and sampled populations, and spillovers over non-compliance (in the Appendix).
This paper builds on the growing literature on statistical treatment choice KitagawaTetenov_EMCA2018, kitagawa2017equality, athey2017efficient, mbakop2016model, armstrong2015inference, bhattacharya2012inferring, hirano2009asymptotics, stoye2009minimax, stoye2012minimax, tetenov2012statistical, zhou2018offline, and classification elliott2013predicting, boucheron2005theory. Unlike previous references, I estimate the policy when treatments generate spillovers here. This paper is the first to study the properties of targeting on networks in the context of the empirical welfare maximization literature.
A conceptual difference from the $i.i.d.$ setting with single and multi-valued treatments as in KitagawaTetenov_EMCA2018, zhou2018offline is that here individuals depend on neighbors' assignments, whereas treatments are individual-specific. This structure permits the population network to be unobserved. In addition, I can bound the complexity of the function class using properties of the maximum degree. The second difference is that individuals exhibit dependence and arguments based on $i.i.d.$ sampling, such as symmetrization, fail here. Optimization differs because individuals depend on neighbors' treatments.
This paper connects the literature on treatment choice with the one on targeting and networks. I provide an overview below and an extensive discussion in Section (ref).
The influence-maximization literature mostly focuses on detecting the most influential “seeds" based on centrality measures. These measures are often motivated by a particular model. See bloch2017centrality for a review. Recent advances include jackson2018behavioral, akbarpour2018just, banerjee2017using, banerjee2014gossip, galeotti2017targeting in economics, and kempe2003maximizing, eckles2019seeding, among others in computer science. This paper differs in (i) its approach because I leverage experimental variation to construct policies that maximize the empirical welfare (instead of policies justified by game theoretic structures); (ii) setup because I allow for constraints on the policy class and heterogeneity in treatment effects. These differences leverage the assumption that spillovers propagate locally in the network, which differs from some of the models in the influence maximization literature. su2019modelling study first-best policies for linear models without policy constraints. I do not impose such structural assumptions. The presence of constraints (and infeasibility of the first-best policy) justifies the regret analysis in the current paper. laber2018optimal consider a Bayesian model whose estimation relies on Monte Carlo methods and the correct model specification.
This paper also connects to the literature on social interaction manski2013identification,manresa2013estimating, auerbach2019identification, and causal inference under interference or dependence liu2019doubly, li2019randomization, hudgens2008toward, goldsmith2013social, sobel2006randomized, savje2017average, aronow2017estimating, chiang2019multiway. The exogenous and anonymous interference condition is closely related to leung2019treatment. However, knowledge of treatment effects is insufficient to construct welfare-optimal treatment rules in the presence of either (or both) constraints on the policy functions or treatment effects heterogeneity. Additional references include bhattacharya2019demand and wager2019experimenting, who study pricing with social interactions through partial identification and sequential experiments, respectively. Here, instead, I study empirical welfare maximization for individualized treatment rules. li2019randomization, graham2010measuring, and bhattacharya2009inferring study optimal configurations of individuals into small groups, such as assigning students to classes, which differs from here where policies denote (constrained) treatment assignments. See kline2020econometric and graham2020econometric for further references.
Finally, more recent works that study targeting in new directions include kitagawa2020should in the context of a parametric model of disease diffusion, ananth in settings with an observed network of the target population, and viviano2020policy in the context of experimental design and sequential experiments.
The paper is organized as follows. Section (ref) presents the problem setup and main conditions. Estimation and theoretical analysis are contained in Section (ref). Section (ref) and online Appendix (ref) present extensions. Section (ref) contains an application. Section (ref) concludes. Appendix (ref) (at the end of the main text) presents a practical guide to implement the algorithm, online Appendix (ref) a numerical study and online Appendix (ref) theoretical derivations.
In this section, I introduce the notation and problem setup. I first introduce the outcome model in Section (ref). Section (ref) formalizes the sampling and design in the experiment. The policy targeting exercise is discussed in Section (ref), and restrictions on the network in Section (ref). Algorithm (ref) in Appendix (ref) presents a user-friendly description of the procedure.
Consider a population of $n$ individuals connected under an adjacency matrix $A$. Each individual is associated with an arbitrary vector of characteristics $ Z_i \in \mathcal{Z} $ and a binary indicator $D_i \in \{0,1\}$, with $D_i = 1$, indicating that individual $i$ was assigned the treatment in the experiment, and $D_i = 0$ if no treatment was assigned. Define $$ A \in \mathcal{A}_n \subseteq \{0,1\}^{n \times n}, \quad N_i = \Big \{j \in \{1, \cdots, n\} \setminus \{i\} : A_{i,j} = 1 \Big\}, \quad Z = (Z_i)_{i=1}^n, \quad D = (D_i)_{i=1}^n, $$ where $\mathcal{A}_n$ is the set of symmetric and unweighted adjacency matrices, $N_i$ denotes the friends of $i$, and $|N_i|$ the degree. Let $Y_i$ denote the $i$'s post-treatment outcome in the experiment. Here, $Z$ can be arbitrary and I impose no restriction on its (joint) distribution.
With interference, unit $i$'s outcome depends on its own and other units' treatment. In full generality, I can write $ Y_i = \tilde{r}_n(i, D, A, Z, \varepsilon_i) $ for some unobserved random variables $\varepsilon_i$ capturing uncertainty in potential outcomes, and unknown $\tilde{r}_n(\cdot)$.\footnote{We consider $\varepsilon_i$ as a random variable to capture uncertainty in the realization of the outcomes once the policy discussed in Section (ref) is implemented at scale. It is possible to extend our results if we condition on $\varepsilon_i$ as in leung2022causal (and therefore without imposing assumptions on $\varepsilon_i$ other than uniformly bounded outcomes as in leung2022causal) only in settings where the treatment probabilities are known (see Remark (ref)).}
Under Assumption (ref), outcomes depend on (i) the number of first-degree neighbors ($|N_i|$), (ii) the number of first-degree treated neighbors (or a function of this, $T_i$), and (iii) individual's treatment status ($D_i$), observables ($Z_i$), and unobservables ($\varepsilon_i$). Assumption (ref) states that interactions are anonymous manski2013identification, and spillovers occur within neighbors. Heterogeneity occurs through the dependence with $Z_i$ and $|N_i|$. The model relates to leung2019treatment, and athey2018exact provide methods to test anonymous and local interference.
Here, $r(\cdot)$ is unknown and $g_n(\cdot)$ is known and characterizes how individuals depend on neighbors' treatments -- that is, the exposure mapping aronow2017estimating; $g_n(0, \cdot) = 0$ is without loss of generality, because $r(\cdot)$ also depends on $(Z_i, |N_i|)$. The function $g_n$ depends on $n$ because its support $\mathcal{T}_n$ can vary with $n$. For example, $g_n$ can be equal to the number of treated neighbors $T_i = \sum_{k \in N_i} D_k$, and the degree can grow with $n$. This scenario is the most agnostic one because $r$ is unknown and therefore equivalent to $g_n(\cdot)$ being unknown. Alternatively, $g_n(\cdot)$ can be equal to a step function of the share of treated neighbors sinclair2012detecting. The size of $\mathcal{T}_n$ affects treatments' overlap discussed in Assumption (ref).
Condition (A) states that unobservables are identically distributed, conditional on the same individual covariates and number of friends, and conditionally independent of $A$ and other units' characteristics. Condition (A) implies network exogeneity, attained if, for example, two individuals form a link based on observable characteristics and exogenous unobservables. Condition (A) guarantees that the individual conditional mean function in Equation (ref) below is the same across units. Condition (B) states that unobservables are independent across individuals who do not share a common neighbor (see Example (ref)). Condition (C) is a bounded moment assumption.
Our method can accommodate scenarios where (A) and (B) fail. I will not assume Condition (A) in settings where the individual treatment probabilities are either known or estimated parametrically (in Lemma (ref), and Theorems (ref), (ref)). I relax (B) in Section (ref).
Next, I formalize the sampling mechanism and experiment.
In the spirit of abadie2020sampling, I define $R_i \in \{0,1\}$ a random variable indicating whether individual $i$'s post-treatment outcome is observed by the researchers. Researchers do not necessarily observe the adjacency matrix $A$. However, researchers observe $i$'s relevant characteristics and treatment as well as $i$'s neighbors' characteristics and treatments if $R_i = 1$ (i.e., researchers only observe the friends of the sampled individuals but not necessarily $A$). In addition, sampled units and their neighbors (but not necessarily the other units in the population) are assigned treatments in the experiment ($D_i = 1$) with positive probability.
I formalize these conditions below. Define $R_i^f = 1\Big\{\sum_{k \neq i} A_{i,k} R_k > 0\Big\}$ the indicator of whether individual $i$ has at least one neighbor who is sampled, and $n_e = \sum_{i=1}^n \mathbb{E}[R_i]$ the expected number of sampled individuals. I consider $n_e < n$, and assume that $n_e$ is proportional to $n$ for expositional convenience.\footnote{If $n_e = n^\rho, \rho < 1$ all our results hold if we replace the right-hand side in Assumption (ref) with $\mathcal{O}(n^{(1/2 - \xi)\rho})$.}
Condition (i) states that researchers observe the post-treatment outcomes of sampled units, the covariates and treatment of sampled units, and the covariates and treatments of the friends of the sampled units. I do not assume that $A$ (the connections of the entire target population) is observed, while I assume that relevant information about the friends of the sampled individuals ($R_i = 1$) is observed. Condition (i) also postulates that the indicators $R_i$ are exogenous with respect to the network $A$, characteristics $Z$ and unobservables $\varepsilon_i$.
Finally, Condition (i) states that the expected number of sampled individuals $n_e$ is proportional to $n$, which is assumed for expositional convenience. We can allow $R_i$ to depend on $Z_i$ (see Remark (ref)) and $n_e$ not to be proportional to $n$.
Condition (ii) states the treatment is randomized in the experiment on observables $Z_i$, which can be arbitrary and may also contain network information, and possibly also on the indicator $R_i$. If individuals are not sampled in the experiment ($R_i = 0$), $D_i$ can also depend on whether at least one friend is sampled (e.g., researchers collect neighbors' information and then randomize treatments across participants and their neighbors).
Condition (iii) imposes positive overlap for sampled units and their friends but not necessarily for the remaining units who are not sampled and are not friends of sampled units. For example, the treatment of those units who do not participate in the experiment and whose friends do not participate in the experiment can be equal to the baseline value $D_i = 0$ almost surely, whereas it is randomized with positive probability for the experiment participants and their friends. Here, $\delta_n$ denotes the overlap constant of the neighbors' treatments of the sampled individuals. It depends on $n$, because the support of the exposure mapping $T_i$ may vary with $n$. We defer to Section (ref) restrictions on $\delta_n$ and on the network.
Figure (ref) (left-hand-side panel) presents an illustration. In an experiment, Assumption (ref) entails: randomizing participants $R_i$; collecting the covariates $Z_i$ and their neighbors' covariates $Z_{N_i}$; randomizing treatments among participants and their friends (observed by the researchers); observing the post-treatment outcomes $Y_i$ of the sampled units ($R_i = 1$).
Under Assumptions (ref), and (ref) define
the conditional mean and propensity score for sampled units ($R_i = 1$), respectively, where we suppressed the dependence of $e$ with $n$ for expositional convenience. Note that Assumption (ref) (A) guarantees that $m(\cdot)$ does not depend on the index $i$. When the propensity score is known, Assumption (ref) (A) is not necessary for our results to hold, because we can use information about $e(\cdot)$ for identification and estimation.
Once the experiment is concluded, a policymaker will design a treatment mechanism with the goal of maximizing average social welfare in the entire population $i \in \{1, \cdots, n\}$, with adjacency matrix and covariates $(A, Z)$ as in Figure (ref). Partition $Z_i = \Big[X_i, \tilde{X}_i\Big]$, for two vectors $(X_i, \tilde{X}_i)$, $X_i \in \mathcal{X} \subseteq \mathcal{Z}$. The policymaker observes from the entire population $$ X = (X_i)_{i=1}^n, \quad X_i \in \mathcal{X}, $$ a subset of individuals' characteristics. Here, $X_i$ denotes individual information observed by a policymaker for all $n$ units in the population. Information $X_i$ can be arbitrary. Examples include census data or network statistics when observed by the policymaker.\footnote{Although we write $Z_i, |N_i|$ separately for expositional convenience, $Z_i$ (and $X_i$) can also contain the degree and other network statistics if observed by the researcher, given that we impose no assumption on $Z$.} Researchers observe an arbitrary function $b_n(X_1, \cdots, X_n)$ of $X$. For instance, $b_n(\cdot)$ can be a constant function if $X_i$ for all $n$ units is only observed by the policymaker but not by the researchers, as in KitagawaTetenov_EMCA2018, or can denote the empirical distribution of $X$ if also observed by the researchers. Researchers design a policy such that:
I therefore consider an individualized treatment assignment $ \pi : \mathcal{X} \mapsto \{0,1\}, \pi \in \Pi_n(b_n(X)) \subseteq \Pi, $ where $\Pi_n(b_n(X))$ denotes the set of constraints on $\pi$, a subset of a given function class $\Pi$. Here, the constraints may also depend on researchers' arbitrary information $b_n(X)$.\footnote{For example, $\Pi_n$ may require $\pi \in \Pi$, and the capacity constraint $\frac{1}{n} \sum_{i=1}^n \pi(X_i) \le K$ for a constant $K$. } The policy $\pi \in \Pi_n$ satisfies (1), (2), and (3). The policy can be implemented in an online fashion, and it does not require observing the population network. However, because I impose no restrictions on $X_i$, individual covariates can contain network statistics if available.
Finally, note that the individualized treatment rules differs from global treatment rules that depend on the population adjacency matrix $A$. Global treatment rules are more flexible, but require observing the network data of the entire target population and therefore are applicable in contexts complementary to ours. See Remark (ref) for a comprehensive discussion.
I define utilitarian welfare as the expected outcome once I assign treatments with policy $\pi(X_i)$ in the entire population of $n$ units. Under Assumption (ref), welfare is defined as
The definition of welfare implies no carryovers occur from the previous experimental intervention once we deploy policy $\pi$ on the population.\footnote{In practice, carryovers do not occur if either the policy $\pi$ is deployed sufficiently far in time from the experimental intervention or if the experiment run by researchers has a neglible effect on the entire population. See athey2018design for a discussion on the no carryovers assumption.} I collect the assumptions below.
I refer to $\Pi_n(b_n(X))$ as $\Pi_n$. Assumption (ref) formalizes the policy targeting exercise and imposes restrictions on the complexity of the function class $\Pi$ as in previous literature KitagawaTetenov_EMCA2018, zhou2018offline. Ideally, one would like to learn
However, $\pi_n^*$ depends on $m(\cdot)$ and $A$, both unobserved. I replace the oracle problem in Equation (ref) with its sample analog, and compare the estimated policy to $\pi_n^*$. I discuss identification below and defer estimation to the following section. Define (with $ T_i(\pi) $ in (ref))
Lemma (ref) shows that we can identify welfare using information from the propensity score under exogeneity of $R_i$. It does not impose conditions on $(A, Z)$ or $\varepsilon_i$ (Assumption (ref) is not required), other than independence with $(R_i, D_i)$ (Assumption (ref)).
Lemma (ref) identifies welfare effects on the entire population of $n$ individuals, conditional on $A$ (and therefore also unconditional on $A$), without requiring observing $A$. The key intuition is to leverage the randomization induced by the sampling indicators $R_i$ and use their independence with the adjacency matrix $A$ and unobservables $\varepsilon_i$. Incorporating sampling uncertainty for policy targeting (without imposing assumptions on the observables and unobservables) is a contribution of independent interest in the context of policy targeting.
I conclude the description of the setup with a set of assumptions on the network topology and overlap that control the degree of dependence. Define $\mathcal{N}_n = \max_{i \in \{1, \cdots, n\}} |N_i| + 2$.
Assumption (ref) bounds the ratio of the maximum degree and the overlap constant and trivially holds in networks with bounded degree described below.
Example (ref) holds for many economic models, for instance, the ones in de2018identifying. Economic applications with a bounded degree include the Add Health Study, and jackson2012social among others.\footnote{In the Add Health Study researchers elicited up to five names of friends of each sex. The number of reciprocated friends have median one and less than five percent of individuals have more than three of such links de2018identifying. In jackson2012social fewer than 1 per 1,000 respondents reached the caps of 5 or 8 nominations (Footnote 37, p. 1879).} Assumption (ref) allows for unbounded degree, in which case properties of the estimators in Section (ref) will depend on $\mathcal{N}_n$ and $\delta_n$.
Restrictions on the degree interact with the choice of the exposure mapping $g_n(\cdot)$ and the overlap constant $\delta_n$. I provide two examples below.
In summary, Assumption (ref) requires that the overlap constant $\delta_n \rightarrow 0$ at a slower rate than $1/\sqrt{n}$, that can hold under restrictions of either the exposure mapping or on the degree. Section (ref) presents theoretical results when Assumption (ref) fails -- that is, $\delta_n \rightarrow 0$ at a faster rate in $n$, using a trimming strategy.
I pause here to compare our framework and assumptions with existing models of spillovers.
The framework I present most closely connects to the literature on causal inference under interference, including, among others, hudgens2008toward, manski1993identification, aronow2017estimating and the model in leung2019treatment in particular. The model in this paper allows for arbitrary heterogeneity in the number of friends, $|N_i|$, observables $Z_i$, and the exposure mapping $T_i$ as a function of the number of treated friends. We can therefore achieve semi-parametric identification of policy effects in the spirit of the literature on (augmented) inverse probability weights tchetgen2012causal, aronow2017estimating.
I do not require restrictions on observables $Z_i$, which can be arbitrarily dependent, and on $A$, other than restrictions on the maximum degree. This approach is possible once I explicitly incorporate sampling uncertainty as in abadie2020sampling for policy learning. Similar restrictions on the degree are often imposed to obtain concentration of the estimated causal effects savje2017average. Here, the maximum degree restrictions together with the local interference assumption allow me also to control the complexity of the policy function class, characterized by the direct and spillover effects $\Big(\pi(X_i), \sum_{k \in N_i} \pi(X_k)\Big), \pi \in \Pi$.
I draw connections to the literature on information diffusion and optimal seeding. This literature mostly studies models where informed individuals transmit information to neighbors sequentially over multiple periods banerjee2013diffusion, banerjee2014gossip, akbarpour2018just, kempe2003maximizing. These references do not take into account heterogeneity as in this paper (e.g., through $Z_i$), and study centrality measures motivated by the diffusion model considered. This paper studies a static model with heterogeneity, with spillovers occurring through the number of treated friends.
In particular, as noted by banerjee2013diffusion, models of information diffusion focus on either what banerjee2013diffusion defines as “information effects" (people become aware of certain opportunities or technologies) or “endorsement effects" (people's behavior may affect others' behavior), but not necessarily both (similar to what manski1993identification defines exogenous and endogenous spillovers). Once we interpret the outcome $Y_i$ as technology adoption, this paper mostly focuses on information effects through the dependence of the outcome on neighbors' treatments (information). It can accommodate endorsement effects in those settings where the function $r(\cdot)$ captures endorsement effects in a reduced form.\footnote{An example is having two periods $t \in \{1, 2\}$, where the treatment consists of providing information at time $t = 1$ to some individuals. At $t = 1$, outcomes only depend on individual treatments $D_i$, whereas at $t = 2$ outcomes depend on the average number of friends who adopted the technology. Let $Y_{i,1} = D_i \tau + \varepsilon_{i,1}$ the outcome at time $t = 1$, and $Y_{i,2} = f(D_i, Y_{i,1}, \sum_{k \in N_i} Y_{k,1}, |N_i|, \varepsilon_{i,2})$, for some function $f(\cdot)$ and i.i.d. $\varepsilon_{i,1}, \varepsilon_{i,2}$. This model satisfy our assumptions for $Y_{i,2}$, with $\varepsilon_i = (\sum_{k \in N_i} \varepsilon_{k, 1}, \varepsilon_{i,1}, \varepsilon_{i,2})$ in Assumption (ref).}
Finally, a further distinction from the literature on seeding kempe2003maximizing, kitagawa2020should, galeotti2017targeting is that the current paper focuses on constrained policies, motivated by the cost of collecting network data, instead of first-best (unconstrained) policies which would require information on the population network.
Next, I introduce our procedure and its properties. I estimate a policy with guarantees valid for finite (possibly large) $n$ and characterize convergence rates as $n,n_e \rightarrow \infty$. Convergence rates are with respect to a sequence of data-generating processes indexed by $n$, each with a single network $A \in \mathcal{A}_n$, where I explicitly condition on $A \in \mathcal{A}_n, Z \in \mathcal{Z}^n$ unless otherwise specified. Conditional statements that I provide below do not subsume that $(A, Z)$ are observed. Instead, they establish stronger guarantees than unconditional statements by leveraging the independence of the sampling $R_i$ with the network $A$ and the assumption that the sampled units are drawn from the (larger) target population (see Lemma (ref)).
Suppose first researchers know the propensity score. Consider the double robust estimator (AIPW):
where $ m_i^c(\pi) = m^c\Big(\pi(X_i), T_i(\pi), Z_i, |N_i|\Big). $ The function $m^c$ denotes an arbitrary regression adjustment, possibly different from the population conditional mean function. Note that $m^c$ can be arbitrary. Therefore, it does not require that the conditional mean functions are identical across units (Assumption (ref) (A)). The estimated welfare inherits double-robust properties in the spirit of robins1994estimation, and tchetgen2012causal, aronow2017estimating, liu2019doubly with spillovers. For known propensity scores and any $m^c$, the estimator is unbiased for $W_{A, Z}(\pi)$ (see Appendix (ref)).
Assumption (ref) states that the regression adjustment is (i) uniformly bounded and (ii) independent of experiment participants. An example is $m_i^c = 0$, or $m_i^c$ estimated on an independent population. The use of $m_i^c(\cdot)$ in this section is not necessary for our results to hold. However, even with a known propensity score, using a regression adjustment can improve the stability of the estimator when poor overlap occurs. Sections (ref) and (ref) provide details where $m_i^c$ is estimated in-sample. With known propensity score and a parametric regression adjustment (ii) is not necessary, as shown in Section (ref). Let $$ \hat{\pi}_{m^c, e} \in \mathrm{arg}\max_{\pi \in \Pi_n} W_n(\pi, m^c, e). $$
Theorem (ref) provides a non-asymptotic upper bound on the regret, and it is the first result of this type under network interference.
The regret bound depends on the network topology through the maximum degree $\mathcal{N}_n$, the overlap constant $\delta_n$, and the (expected) sample size $n_e$. The degree affects the regret bound through two channels: (i) dependence between outcomes conditional on the network and covariates and (ii) the complexity of the function class obtained by the composition of direct and spillover effects. For (i), I leverage Assumptions (ref), (ref) (i, ii), and (ref) (B), to show each individual observation is dependent with at most $2 \mathcal{N}_n^2$ many other units. For (ii), I leverage instead Assumptions (ref) and (ref), to bound (ii) as a function of the VC dimension of $\Pi$ and $\mathcal{N}_n$. The bound also depends on $\delta_n$, which can vary with $n$. Intuitively, for larger networks (and larger degrees), the probability that individuals exhibit strict overlap may get smaller, depending on the exposure mapping considered. The bound is independent of $\alpha$ in Equation (ref). Theorem (ref) does not assume Assumption (ref) (A).
The bound shrinks to zero as $n_e$ increases, only if the maximum degree and the overlap constant grows at an appropriate slower rate than the sample size. We formalize this below.
The corollary shows that the regret converges to zero at a rate that depends on the convergence rate of the maximum degree and the number of experiment participants. For bounded degree, the regret scales at rate $1/\sqrt{n_e}$.
In the following theorem, I provide a lower bound for any data-dependent policy. Consistently with the previous theorems, I provide the lower bound conditional on $(A,Z)$.
Theorem (ref) provides a worst-case lower bound to any data-dependent policy, holding uniformly for any $n_e \ge 16 \mathrm{VC}(\Pi)$. Similar to lower bounds in the literature KitagawaTetenov_EMCA2018, the bound is maximin over the data-generating process, including any adjacency matrix $A$ satisfying Assumption (ref). However, different from KitagawaTetenov_EMCA2018, Theorem (ref) establishes the minimax convergence rate of $\hat{\pi}_{m^c, e}$ for the rescaled regret
after we divide by the factor $(\mathcal{N}_n^{3/2} \log(\mathcal{N}_n))/\delta_n$ appearing in Theorem (ref). The rescaling factor differs from lower bounds on the (non-rescaled) regret in the literature, and it is motivated by the dependence of $\mathcal{N}_n$ with the adjacency matrix and $\delta_n$ with the data-generating process. We discuss implications for the regret without rescaling below.
Corollary (ref) follows from the fact that $\delta_n/\mathcal{N}_n^{3/2} \log^{1/2}(\mathcal{N}_n) \le 1/\log^{1/2}(2)$. It states that the lower bound for the rescaled regret implies a lower bound for the regret. Therefore, Theorem (ref) establishes a minimax rate of convergence of $\hat{\pi}$ for the regret without rescaling under the additional assumption that $\mathcal{N}_n < c_0$ is uniformly bounded for a constant $c_0 < \infty$.
In summary, the bound in Theorem (ref) converges to zero as $n, n_e \rightarrow \infty$, in settings with a sufficiently small degree (see Corollary (ref)). The bound in Theorem (ref) does not converge to zero if the degree $\mathcal{N}_n$ grows at an arbitrary rate with $n$. Therefore our bounds are informative (converge to zero), only in settings with a sufficiently sparse graph. These settings include bounded degree as a special case, but also allows for unbounded degree with rate satisfying Assumption (ref). For example, with an exposure mapping such that $\delta_n \in (\delta, 1 - \delta)$ for a constant $\delta$ independent of $n$ (for instance, the exposure mapping is as in Example (ref) with $\lambda_n$ independent of $n$), the bound converge to zero only if $\mathcal{N}_n^{3} \log(\mathcal{N}_n)/n \rightarrow 0$. In addition, the bound in Theorem (ref) also provides a minimax rate of convergence of the regret (without rescaling) in settings where the degree is uniformly bounded (but not necessarily otherwise).
Next, I derive regret guarantees when estimating the conditional mean $m(\cdot)$ and/or propensity score $e(\cdot)$, as defined in Equation (ref) under Assumptions (ref), and (ref). Define $\hat{m}$, and $\hat{e}$ the estimated conditional mean and propensity score as in Algorithm (ref) (Appendix (ref)), $W_n(\pi, \hat{m}, \hat{e})$ as the welfare with the estimated nuisance functions as in Equation (ref), and
I propose a modification of the cross-fitting algorithm -- see chernozhukov2018double, and athey2017efficient in particular -- here studied in the context of interference. I describe the algorithm in Algorithm (ref) and provide a sketch in Algorithm (ref).
First, I find the smallest partition of sampled individuals such that two individuals assigned to the same group are neither friends nor share a common friend. This information is available under the sampling mechanism in Section (ref), because researchers observe the set of friends of each sampled individual. The solution to this problem is obtained by solving a sequence of mixed-integer linear programs. Each program fixes the number of groups (starting from one). For a given number of groups, it checks whether a feasible partition exists. If no feasible partition exists, it increases by one the number of groups and iterates.
Once I obtain such groups, I estimate the conditional mean function using standard cross-fitting within each group of individuals as in athey2017efficient. Specifically, I partition each group $g$ into $K$ equally sized folds; for individual $i$ in group $g$, fold $k$, I estimate her conditional mean function using information from all units in each fold in group $g$ except fold $k$. I repeat the same algorithm for the propensity score, where I first estimate the individual treatment probability and then aggregate such probabilities as in Remark (ref). Algorithm (ref) presents the details and Algorithm (ref) a summary.
As in athey2017efficient, the regret bound is increasing in the number of folds, while the estimation error of the nuisance functions is decreasing in the number of folds (see Appendix (ref)). Therefore, we must choose a sufficiently large $K$ to control the estimation error of the nuisance functions. However, the choice of $K$ must also guarantee that each fold contains a non-negligible proportion of observations. In practice, I recommend $K$ between five and ten.
To my knowledge, Algorithm (ref) is novel to the literature on interference. Its main innovation with respect to existing cross-fitting methods is the partitioning approach (Part 1 in Algorithm (ref)), here required due to interference. For settings where the network presents approximately independent components (e.g., regions), I also present a computational relaxation in Algorithm (ref). Algorithm (ref) constructs subgraphs of the network recursively to minimize the number of individuals with shared friends between different subgraphs. It estimates nuisance functions for unit $i$ using information from units in the subgraphs different from the one of unit $i$. With multiple disconnected regions, Algorithm (ref) estimates the nuisance functions using information from all regions except the one containing $i$. See Appendix (ref) for details.
To study properties of the algorithm, I assume that the estimated nuisance functions satisfy the same bounded and overlap conditions as their population counterparts athey2017efficient.
The rate of convergence here also depends on the product of the mean-squared error of the estimated conditional mean function and propensity score, averaged over the population covariates and number of neighbors:
where $\hat{m}^{(i)}, \hat{e}^{(i)}$ are the estimated functions for unit $i$, as defined in Algorithms (ref), (ref).
Theorem (ref) states that the regret bound depends on two components. The first component depends on the convergence rate of the maximum degree, overlap constant, and experiment size, similar to what was discussed in the presence of a known propensity score (e.g., Corollary (ref)). For a bounded degree as in Example (ref), $\xi = 1/2$, and $\xi < 1/2$ otherwise. The second component depends on the estimation error of the nuisance functions, and in particular, it depends on the product of their convergence rates, in the same spirit of standard conditions in the $i.i.d.$ setting farrell2015robust.
Next, I discuss the optimization procedure. For simplicity, consider the most agnostic case where $T_i = \sum_{k \in N_i} D_k$ denotes the sum of treated neighbors. Similar reasoning applies to $T_i$ being a known function of the sum of treated neighbors. Define the estimated effect of assigning to unit $i$ treatment $d$, after treating $t$ neighbors:
where I omit the dependence of $q_i(\cdot)$ with $m^c$ and $e$ for the sake of brevity. Second, let $ B_i(\pi, h) = 1\Big\{\sum_{k \in N_i} \pi(X_k) = h \Big\} $ be the indicator of whether $h$ neighbors of individual $i$ have been treated under policy $\pi$. We have the following:
Namely, each element in the sum is weighted by the indicator $B_i(\pi,h)$, and only one of these indicators is equal to one. I can then define variables $p_i, p_i = \pi(X_i), \pi \in \Pi_n$ that denote the treatment assignment of each unit $i$ either sampled $(R_i = 1)$ or friend of a sampled unit $(R_i^f = 1)$. For example, for $ \pi(X_i) = 1\{X_i^\top \beta \ge 0\}, \beta \in \mathcal{B}, $ florios2008exact, $$
$$ where $p_i$ is equal to one if $X_i^\top \beta$ is positive, and zero otherwise. The key intuition is to introduce additional variables to write $B_i(\pi, h)$ using mixed-integer linear constraints. Define $$ t_{i,h,1} = 1\left\{\sum_{k \in N_i} p_k \ge h\right\}, \quad t_{i,h,2} = 1\left\{\sum_{k \in N_i} p_k \le h\right\}, \quad h \in \{0, \cdots,|N_i|\}. $$ It follows that $t_{i,h,1} + t_{i,h,2} - 1 = B_i(\pi, h)$, and that such variables admit a mixed-integer linear program characterization. Formally, the optimization program is
under the following constraints:
The first constraint can be replaced by methods discussed in previous literature, such as maximum scores florios2008exact. By contrast, the additional constraints are due to interference. In practice, including additional (superfluous) constraints stabilizes the optimization problem. These are $\sum_h (t_{i,h,1} + t_{i,h,2} - 1) = 1$ for each $i$ and $\sum_i \sum_h u_{i,h} = \sum_i p_i$. Whenever units have no neighbors, the objective function is proportional to the one discussed in KitagawaTetenov_EMCA2018 under no interference. Therefore, the formulation generalizes the MILP formulation to the case of interference.
The proof of Theorem (ref) follows directly from the argument in the current section.
This section includes a sketch of the proof of Theorem (ref), whereas Appendix (ref) presents formal definitions and derivations. Readers not interested in the proof of Theorem (ref) can skip to Section (ref) (or (ref)). For brevity, in the argument below, I further assume $Y_i \in [-\Gamma', \Gamma']$ for a finite constant $\Gamma' < \infty$; that is, the outcome is uniformly bounded. Appendix (ref) presents derivations for unbounded outcomes. Because $\Pi_n \subseteq \Pi$, it follows that
our focus will be bounding the right-hand side of Equation (ref). Define $$
$$ where the dependence with $e, m^c$ is suppressed for convenience. Define $\mathcal{Q}_n(\pi, A, Z)$ as the \textit{joint} distribution, of $Q_i$, namely $\Big(Q_i(\pi, A, Z)\Big)_{i=1}^n \Big| A, Z \sim \mathcal{Q}_n(\pi, A, Z)$, for given $\pi, A, Z$.
Define $(\sigma_i)_{i=1}^n$ $i.i.d.$ Rademacher random variables independent of observables and unobservables ($P(\sigma_i = 1) = P(\sigma_i = -1) = 1/2$) and $\mathbb{E}_\sigma[\cdot]$ denotes the expectation only with respect to $(\sigma_i)_{i=1}^n$, conditional on observables and unobservables. By Lemma (ref) $\mathbb{E}[W_n(\pi)| A,Z] = W_{A, Z}(\pi)$ for all $\pi \in \Pi$.
\paragraph{Symmetrization with network data} Next, I extend the symmetrization argument vershynin2018high to the context of this paper. Define \\ $\Big(Q_i'(\pi, A, Z)\Big)_{i=1}^n \Big| A, Z \sim \mathcal{Q}_n(\pi, A, Z)$, an independent copy of $\Big(Q_i(\pi, A, Z)\Big)_{i=1}^n$, conditional on $(A, Z)$. It follows
Ideally, using standard symmetrization arguments, I would like to bound the right-hand side in Equation (ref). Unfortunately, this is not possible because of dependence. I instead partition observations into groups of conditionally independent random variables. I then obtain bounds that depend on the number of such groups. Let $A^2$ be the adjacency matrix obtained by connecting neighbors and two-degree neighbors under $A$. Let $\chi_n(A^2)$ be the smallest number of groups such that each group does not contain two units that either are neighbors or share a common neighbor under $A$, and $\mathcal{C}_n^2 = \{\mathcal{C}_n^2(g)\}_{g=1}^{\chi_n(A^2)}, \mathcal{C}_n^2(g) \subseteq \{1, \cdots, n\}$, the smallest set of such groups. Then
Note that $Q_i$ equals zero if $R_i = 0$. Therefore, under Assumption (ref) (ii), it follows that $Q_i$ can be written as a function of $\Big[R_i\Big(\varepsilon_i, R_i, \varepsilon_{D_i}, R_i^f, R_{j \in N_i}, R_{j \in N_i}^f, \varepsilon_{D_{j \in N_i}}, Z_i, |N_i|, Z_{k \in N_i}\Big)\Big]$, where $R_i^f = 1\{\sum_k A_{i,k} R_k > 0\}$. For each $j \in N_i$, $R_{j}^f$ equals one almost surely conditional on $R_i = 1$. $R_i^f$ is instead a deterministic function of $R_{j \in N_i}$. As a result, because $Q_i = 0$ if $R_i = 0$ almost surely, one can write $Q_i$ only as a function of $\Big[R_i\Big(\varepsilon_i, R_i, \varepsilon_{D_i}, R_{j \in N_i}, \varepsilon_{D_{j \in N_i}}, Z_i, |N_i|, Z_{k \in N_i}\Big)\Big]$, its dependence with $R_{j \in N_i}^f$ can be dropped.
Under the distributional assumptions of each of these components, it follows that $Q_i$ are jointly independent if they are not neighbors and do not share a common neighbor conditional on $A, Z$.\footnote{In particular, we leverage here Assumption (ref) (interference is local); Assumption (ref) (ii) (treatments are conditionally independent); Assumption (ref) (B) (unobservables are conditionally independent if two individuals do not share a common neighbor). I relax Assumption (ref) (B) in Section (ref).} Because $Q_i, Q_i' | A, Z$ have the same marginal distribution by construction, $$
$$
\paragraph{Bound on the function class complexity} I control $(III)$ with Lemma (ref). The idea of the lemma is the following. First, note that here $Q_i(\pi, \cdot)$ depends on $\pi$ through $\Big(\pi(X_i), \sum_{k \in N_i} \pi(X_k)\Big)$. I show that $Q_i(\pi, A, Z)$ is Lipschitz in $\Big(\sum_{k \in N_i} \pi(X_k)\Big)$ with the Lipschitz contant proportional to $\frac{\Gamma'}{\gamma \delta_n}$. I then leverage extensions of the Ledoux-Talagrand contraction inequality ledoux2011probability to show
for a universal constant $\bar{C} < \infty$. Using Theorem 5.22 in wainwright2019high, I can bound the right-hand side in Equation (ref), by an integral of the covering number of a function class obtained from $ \Big(\sum_{k \in N_i} \pi(x_k)\Big) \pi(x_i), \pi \in \Pi$ -- which we can bound by a function of the maximum degree and the VC dimension of $\Pi$ (Lemma (ref)) -- and $\frac{\sqrt{\sum_{i=1}^n R_i 1\{i \in \mathcal{C}_n^2(g)\}}}{n_e}$.
\paragraph{Conclusions} Collecting terms, for a universal constant $\bar{C} < \infty$, I show $$
$$ The first term $\sqrt{\chi_n(A^2)}$ captures the dependence structure. By \cite{brooks1941colouring}'s theorem, $\chi_n(A^2) \le 2 \mathcal{N}_n^2$ (see Lemma \ref{lem:boundnumber}). The second term captures Lipschitz-continuity of the objective function and depends on the overlap $1/\delta_n$. The third term captures the complexity of the function class of interest, increasing in the maximum degree. The last term captures concentration in the sample size. Using Jensen's inequality, $\mathbb{E}\Big[\frac{\sqrt{\sum_{i=1}^n R_i}}{n_e}\Big] \le 1/n_e^{1/2}$. In Theorem \ref{thm:thmmain}, $\Gamma$ replaces $\Gamma'$ under bounded moments, instead of bounded outcomes.
I discuss here trimming with poor overlap, higher-order dependence, different target and sample units, and non-reversible treatments. Appendix (ref) contains additional extensions.
In this subsection, I provide regret bounds whenever a few units may present a large degree. I consider the setting where $T_i = \sum_{k \in N_i} D_k$. To guarantee overlap, I introduce the following trimming estimator:
with $e_i(\pi), m_i^c(\pi), I_i(\pi)$ as in Equation (ref). Here, $\log_\gamma(\kappa_n)$ defines the trimming constant, as the logarithm in scale $\gamma$ of a user-specific $\kappa_n$ (with $\gamma$ in Assumption (ref)).
The trimming estimator builds on the following idea: it excludes the direct effect on the largely connected nodes (with more than $\log_\gamma(\kappa_n)$ neighbors) but keeps information from the spillovers that such nodes generate. This is because nodes with most connections are those for which overlap restrictions are more likely to fail. Define $$ \hat{\pi}_{\kappa_n}^{tr} \in \mathrm{arg} \max_{\pi \in \Pi_n} W_n^{tr}(\pi, m^c, e; \kappa_n), \quad P_n\Big(|N_i| \ge \log_\gamma(\kappa_n)\Big) = \frac{1}{n} \sum_{i=1}^n 1\Big\{|N_i| \ge \log_\gamma(\kappa_n)\Big\}. $$
Theorem (ref) shows we can improve the regret bound for a suitable choice of $\kappa_n$ under restrictions on the degree distribution. For instance, suppose $\sqrt{n}$-many individuals have a degree that can grow in $n$, whereas all other units have a degree bounded by at most $\log_\gamma(\kappa)$, for a constant $\kappa$ independent of $n$. In this case, $P_n(|N_i| \ge \log_\gamma(\kappa)) = \mathcal{O}(\sqrt{\frac{\alpha}{n_e}})$, and the regret is of order $\mathcal{O}\Big(\frac{\mathcal{N}_n^{3/2}}{\kappa} \sqrt{\frac{\log(\mathcal{N}_n) \mathrm{VC}(\Pi)}{n_e}}\Big)$, independent of $\delta_n$. Theorem (ref) illustrates how information can be leveraged from the degree distribution to improve convergence rates.
Next, I characterize regret bounds in settings where individuals can depend on friends up to the degree of order $M$, where $M$ is a finite number and unknown. To simplify exposition, I assume the outcome is uniformly bounded.
Under Assumption (ref), unobservables can depend on individuals of at most degree $M$. Suppose $M$ is unknown and researchers do not have information from higher-order neighbors. Define $m^c: \{0,1\} \times \mathbb{Z} \times \mathcal{Z} \times \mathbb{Z} \mapsto [-\Gamma', \Gamma']$ for some finite $\Gamma' < \infty$, $e^c(\cdot; |N_i|): \mathcal{Z}^{|N_i|} \times \{0,1\}^{|N_i|} \times \mathcal{Z} \mapsto (\gamma \delta_n, 1 - \gamma \delta_n)$, the pseudo-true conditional mean function and propensity score, and $\hat{m}, \hat{e}$ their corresponding estimators constructed arbitrarly (e.g., pooling information from all sampled units). Let
denote the mean-squared errors of the estimators obtained from all sampled units, averaged over the population covariates and number of neighbors. Different from Theorem (ref), we do not need to condition on $R_i = 1$ in Equation (ref) because no cross-fitting is used, and the estimated nuisance function is independent of $i$'s index.
Theorem (ref) provides a uniform bound on the regret, and it is double robust to correct specification of the conditional mean and the propensity score. The theorem's result depends on the convergence rate of $\hat{e}$ and $\hat{m}$ to their $pseudo$-true value. For parametric estimators of the conditional mean and the propensity score and bounded degree, the regret bounds scale at rate $1/\sqrt{n_e}$, divided by the overlap parameter. For general machine-learning estimators, the rate can be slower than the parametric one, reflecting the “cost” of the lack of knowledge of the degree of dependence $M$. Here, $\mathcal{N}_n^{M/2 - 1}$ captures higher-order dependence. Theorem (ref) does not require that Assumption (ref) (A) holds in settings with a correctly specified propensity score, assuming $\hat{m}^c$ converges to some pseudo-true value $m^c$.
This subsection compares regret guarantees when units are either drawn from the (larger) target population as described in Section (ref), or units are drawn from a different population from the target population. Following KitagawaTetenov_EMCA2018, and to simplify exposition in this subsection, we consider a policy function class $\Pi_n = \Pi$ where $\Pi$ is not data dependent.\footnote{We assume that $\Pi_n = \Pi$ not to define the joint distribution of $(X, A', Z')$ in the definition below. } Consider a population with $n$ individuals, connected under adjacency matrix $A'$ and with covariates matrix $Z'$. For given $(A', Z')$, welfare is defined as
Consider two notions of regret, the conditional and expected regret, defined respectively as
The conditional regret is a function of the target population adjacency matrix and covariates $Z'$, whereas the expected regret takes expectation over $(A', Z')$. The expected regret is (implicitly) a function of the joint distribution of $(A', Z', A, Z)$, since it integrates over the distribution of $(A', Z')$ and $\hat{\pi}$ estimated on the sampled units.
When the target population differs from the population from which we sample experiment participants, we can only hope to control the expected, but not the conditional regret. When instead the target population is the one from which we sample the experiment participants, we can control both notions of regret as shown in the following lemma.
Lemma (ref) shows that the regret guarantees in Section (ref) are valid bounds on the expected (and conditional) regret. The proof of Lemma (ref) follows directly from Jensen's inequality and the law of iterated expectations. The main assumption of Lemma (ref) is that the sampled units are drawn from the (larger) target population, which is the main case of interest in this paper. This is a common feature in applications where researchers sample (small groups of) individuals at random from a large region or country cai2015social, egger2019general, and are interested in scaling the policy up in such a region or country.
Suppose, however, we are interested in implementing the policy on a population different from the one from which we have drawn our sample (e.g., in a different country). In the following theorem, we study guarantees of the proposed procedure for this setting.
The proof is in Appendix (ref). Theorem (ref) provides a bound on the expected (instead of conditional) regret, allowing the sampled units to be drawn from a population different from the target population. The bound depends on two components. The first mimics the component in Theorem (ref) and depends on the expected maximum degree and the expected size of the sampled population $n_e$. The second component instead captures the discrepancy between the population from which the sample is drawn $(A, Z)$ and the target population.
Suppose that $(A, Z), (A', Z')$ have the same distribution. It follows
which is independent of the sample size $n_e$. Equation (ref) depends on how fast the conditional mean functions of all units $n$ concentrate around their expectation uniformly over $\Pi$. Equation (ref) captures the expected “cost" of targeting treatments on a population different from the one from which the sample was drawn.
I now illustrate the proposed method using data originating from cai2015social. The authors study the effect of an information session on farmers' weather insurance adoption. Individuals are grouped into 185 addresses (villages) grouped into approximately 50 larger areas. According to the authors, “All rice-producing households were invited to one of the sessions, and almost 90% of them attended. Consequently, this provided us (the authors) with a census of the population of these 185 villages. In total, 5,335 households were surveyed" cai2015social. Before conducting the experiment, researchers collected network data by asking each individual to indicate at most five friends (who can be in the same or different village). On average, $50\%$ of the connections of sampled units have a different village. More than $90\%$ of the connections are within the same area.
In this application, I use information collected from those units for which information about their post-treatment outcome and their friend's identity is available; in total, 4511, a subset of the population. The experiment consists of two rounds of information sessions three days apart, each round containing two types of information sessions (simple and intensive). Households are randomized to each round and within each round to each type of information session. By using time variation over the two rounds, cai2015social show the existence of significant neighbors' spillover effects of an intensive information session on second-round participants' outcomes and no endogenous spillover effects, consistently with the model presented in this paper. I defer a discussion on how the model and assumptions of this paper connect to cai2015social to Section (ref).
In the experiment, “the effect of social networks on insurance take-up is identified by looking at whether second round participants are more likely to buy insurance if they have more friends who were invited to first round intensive sessions" cai2015social. Specifically, each round consists of two sessions held simultaneously. In the first round, households are assigned to either a 20-minute session during which researchers offer details about the insurance contract only (control arm, “simple" information session) or a 45-minute session that also provides details about the expected benefits of insurance (treatment arm, “intensive" information session). In the second round, farmers are assigned similarly to either intensive or simple information sessions. Treatment denotes whether individuals were assigned to an intensive information session (either in the first or second round), whereas, by design, spillovers occurs from the first to second round, as described in cai2015social.\footnote{For estimation, I follow cai2015social and consider the general network matrix where spillovers only occur from individuals participating in the first information session to individuals in the second session. When evaluating the out-of-sample performance of the policy, I use the original “general network" as an adjacency matrix because out-of-sample evaluations may not have the sequential structure of the experiment (i.e., some individuals may be treated and asked to make purchase decisions some time after treatment occurs, possibly generating spillovers also on the treated units participating in the same information session).} Researchers also considered additional arms where they provided information about purchase decisions of other participants (“More info" in Figure (ref)). Here, I follow the main analysis in cai2015social (Table 2), and focus on providing information on insurance benefits only.
I follow cai2015social in the model specification. I estimate a model using all first-round participants and those second-round participants either in the control arm or in the main (intensive) treatment arm.\footnote{Namely, I follow Column (2)-(5) in Table 2 in cai2015social. As discussed in cai2015social, I can drop observations in the “More info" treatment arms for estimating the conditional mean function because individuals in the second-round of information sessions do not generate spillover effects by design. } I estimate $\hat{m}$ using the linear probability model for the outcome as in cai2015social (Table 2, Col (4)), controlling for area fixed effects, a large set of covariates, the average number of treated neighbors, individual treatment, and the interaction between individual and neighbors' treatments. The model in cai2015social assumes homogenous treatment effects across covariates and villages. Here, I also allow for some heterogeneity in covariates and control for interaction terms of the rice area, a coefficient capturing risk aversion and education with individual and neighbors' treatments. Following cai2015social, I consider the “general network" as the main network, that is, the raw network data obtained from surveys where an individual generates spillover effects on $i$ if she was indicated by $i$ as a friend. I then construct welfare using a doubly-robust estimator, with ten-fold cross-fitting as in Algorithm (ref). The conditional mean is estimated via lasso with a small penalty ($e^{-12}$) to increase the stability of the estimator. The individual propensity score is estimated as in Remark (ref) via a penalized logistic regression with a similar small penalty and $5\%$ trimming.
I “simulate" the following environment: researchers collect information from villages in the first fifteen areas. They estimate the policy to treat individuals in the remaining villages. In the remaining villages, I assume the policymaker does not have access to the network information but only observes the farmer's education, risk aversion, and rice area. I then compute welfare effects out-of-sample on the villages outside the training set (first 15 areas). I repeat the same process via three-fold cross-fitting: I use the second fifteen areas as a training set and the remaining areas as a test set; similarly, I use the last group of areas as a training set and the first thirty areas as a test set. Finally, I compute the average out-of-sample improvements over the three out-of-sample evaluations. The out-of-sample evaluation uses the double-robust score, estimated out-of-sample. This exercise mimics settings where participants are sampled from a random subset of villages, and the treatment assigned to the experiment participants cannot be changed after the experiment (see Remark (ref)). In this exercise, I sample areas instead of villages to guarantee that the welfare estimates are independent of the training set, a desirable property for out-of-sample comparisons.
I contrast to the empirical welfare-maximization method that ignores welfare effects in athey2017efficient, KitagawaTetenov_EMCA2018 and uses the same policy and models of the proposed procedure for both the propensity score and conditional mean function (including that the conditional mean function controls for spillovers).
As a first exercise, I consider simple policies that use information from transformations of two of the three covariates: education, rice area, and a coefficient capturing risk aversion. I compute simple classification trees obtained for all possible two-out-of-three combinations of such variables. The tree finds one optimal split over the first (continuous) variable. The split for the second variable is constrained to be at the population median value. This policy is simple to compute and communicate because it assigns treatments based on a few possible sub-groups. I study out-of-sample improvements while varying the treatment cost as $1\%, 3\%, 5\%$ of the insurance take-up benefit. These costs are comparable to the direct treatment effect that we would estimate once observations from all villages as in Table 2, Col 2 in cai2015social are pooled (approximately equal to $3\%$). Table (ref) provides welfare comparisons. We observe welfare improvements up to approximately thirty percentage points and positive effects uniformly across the specifications. These economically significant improvements are obtained despite the network not being observable in the target sample.
As a second exercise, I consider a more complex policy consisting of a maximum score that controls for education, rice area and risk aversion as follows:
The parameters are estimated using the mixed-integer linear program in Section (ref). Table (ref) reports the average out-of-sample welfare improvement estimated via three-fold cross-fitting. It shows out-of-sample welfare improvements up to nine percentage points. This result illustrates the benefits of the procedure for more complex policy functions as well.
The cross-fitting procedure returns three policies estimated on independent samples. To investigate the properties of the estimated policy, Table (ref) reports the coefficients of the estimated policy (NEWM) leading to the largest out-of-sample welfare. The policy treats individuals who are more risk-averse, less educated, and with a smaller rice area. I contrast this policy with the one that ignores network effects (EWM). The two policies are substantially different when treating individuals with larger rice areas and risk aversion. This difference highlights the importance of taking into account spillover effects for policy targeting because different subgroups should be treated differently with spillover effects.
This section concludes with a review of the assumptions required by the proposed procedure and their applicability in the context of the chosen application. Assumption (ref) states that interference occurs through the neighbors' treatment assignments. In the context of our application, treatments denote (intensive) information sessions. This paper assumes potential outcomes are (possibly heterogeneous) functions of the number of informed neighbors. As a result, the model is best suited when information effects, as opposed to endorsement effects (i.e., effects driven by neighbors' purchase decisions), occur. This restriction is consistent with findings in cai2015social, who, by leveraging the sequential structure of the experiment, illustrate information effects and lack of endorsement effects. Quoting cai2015social's abstract: “By varying the information available about peers' decisions and randomizing default options, we show that the network effect is driven by the diffusion of insurance knowledge rather than the purchase decisions." Insurance knowledge denotes the treatments, and purchase decisions are the outcomes of interest, consistent with our model.
A second restriction this paper imposes is that the maximum degree is sufficiently smaller than the sample size (Assumption (ref)). This restriction avoids overfitting and controls the complexity of the function class of interest. Following the specification in cai2015social, here individuals generate spillovers on those people indicated as friends, at most five of them by the design of the survey in cai2015social. Therefore, we interpret our analysis as imposing a restriction on the exposure mapping $g_n(\cdot)$: only the five “closest" friends (i.e., friends indicated in the survey) generate spillover effects, whereas if there are other friends not indicated in the survey, these generate no or negligible spillovers. This assumption is mantained in cai2015social, who state: “The drawback of this specification is that the network characterization may be incomplete. This concern is mitigated by the experience of the pilot test in two villages, where most farmers named four or five friends (82% five, 14% four, and 4% others) when the number was not limited." However, it is important to acknowledge that this is an assumption, and future research should explore the sensitivity of the estimated policy to misspecification of the exposure mapping savje2023causal.
The model specification of the conditional mean function in cai2015social imposes a lack of heterogeneity in unobserved network statistics. However, because we augment the estimated conditional mean with the doubly robust score, the estimators also allow for arbitrary network heterogeneity, even if such heterogeneity is not captured in the estimated conditional mean function. The reader may refer to Lemma (ref) and Theorem (ref) for details.
Finally, the sampling in cai2015social guarantees that the welfare estimated using information from participants is an unbiased estimator of welfare once the policy is deployed at scale in rural China. The main reason is that cai2015social independently sample 185 small villages in rural China, and, among such, they randomize treatments at the individual level cai2015social. This sampling induces local dependence within small villages, which is possible to accommodate in our framework (see Remark (ref)).
This paper introduced a method for estimating treatment rules under network interference. It considers constrained environments, and accommodates policy functions that do not necessarily depend on network information. The proposed methodology is valid for a large class of networks and does not impose restrictions on covariates. I cast the optimization problem into a mixed-integer linear program and derive guarantees on the policy regret.
The proposed method assumes anonymous and exogenous interactions. Future research can address the case of endogenous interactions by explicitly modeling the endogenous component, or considering weak dependence structures as in leung2022causal.
This paper estimates welfare-maximizing policies when the network information on the target sample is not observed by directly maximizing the empirical welfare. Extending our method by incorporating partial information on the population network is an interesting future direction. Combining the high-dimensional estimator of the network as in alidaee2020recovering with the empirical welfare-maximization procedure is a possible approach.
Finally, the literature on influence maximization has often relied on structural models, whereas the literature on treatment choice has focused on semiparametric estimation. This paper opens new questions about the trade-off between structural assumptions and model-robust estimation of policy functions. Exploring this trade-off remains an open question.