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.
77,355 characters · 21 sections · 62 citation commands
Experimental Design under Network Interference
{\it Keywords:} Experimental Design, Spillovers, Two-wave experimentation, Causal Inference. \\
\onehalfspacing
This paper studies the design of experiments for inference on treatment effects under network interference. Network interference induces (i) spillovers across units and (ii) statistical dependence. Our goal is to obtain precise estimates of common measures of treatment effects, such as direct, spillover, and overall effects.
We consider a setting in which individuals are connected in a single network and interact locally (i.e., with neighbors).\footnote{This assumption is known as local interference manski2013identification and can be tested, for instance, using athey2018exact. It is often assumed in practice egger2019general,dupas2014short,miguel2004worms,bhattacharya2013estimating,duflo2011peer and studied in theoretical analyses forastiere2016identification,leung2019treatment,sinclair2012detecting.} Unlike typical clustered or saturation-design settings baird2018optimal, independent clusters are not necessarily available. Instead, researchers observe a single network; they run a pilot (first-wave experiment) to estimate outcome variances and covariances and then optimally select participants and treatments in the main (second-wave) experiment.\footnote{Pilot studies are common practice; see, e.g., karlan2018failing,karlan2008credit,dellavigna2018predicting.} Relevant applications include online and field experiments in which interference naturally occurs karrer2021network,muralidharan2017general.
The experiment, which we call “Experiment under Local Interference” (ELI), is designed to recover one or more estimands, including (i) the overall effect, (ii) the direct effect, and (iii) spillover effects. For example, in a cash transfer program barrera2011improving, one may be interested in effects on recipients (direct effects), on non-recipients living near recipients (spillovers), and on their sum (overall effects). For each estimand, we consider a single user-specified estimator linear in observed outcomes; the choice of estimator may arise from a researcher’s spillover model muralidharan2017general,kreindler2023optimal,egger2019general.
We rely on two conditions common in economic applications: (i) interference and dependence are local within the network; and (ii) effects may be heterogeneous in observed and low-dimensional network summary statistics.\footnote{Examples consistent with these conditions include models of spillovers in public programs muralidharan2017general, cash transfer programs egger2019general, health interventions dupas2014short, and educational programs duflo2011peer.}
We propose the following protocol: (1) we select a small subsample and conduct a pilot study; (2) using pilot information, we then choose participants and treatment assignments in the main experiment; finally, (3) we collect outcomes for participating units. Under this protocol, we develop a statistical framework for the design and inference of a two-wave experiment (pilot and main) under network interference.
As a first step, we show that the main experiment is unconfounded if pilot units and their neighbors are excluded from the main experiment; otherwise, this does not need to hold. This restriction creates a design trade-off: a larger pilot yields more precise variance estimates (useful for the second wave) but also imposes stricter constraints on the main experiment. As a result, we should select a pilot that is sufficiently “well separated’’ from (i.e., shares few neighbors with) the rest of the network. We embed this problem in a min-cut optimization that can be solved using off-the-shelf algorithms. We then select participants and treatment assignments in the main experiment to minimize the estimated variance of the target estimator(s).
We derive theoretical guarantees that inform the selection of the pilot. In particular, we establish the rate at which the variance of the two-wave design approaches that of an “oracle’’ design (regret); the oracle selects participants and assignments to minimize the true variance without a pilot and without additional constraints on the main experiment. The regret converges to zero at a rate governed by the inverse of the pilot size and by the ratio of the pilot to the main-experiment size. This, in turn, yields a regret-minimizing pilot size as a function of the main-experiment size and provides intuitive rules of thumb for choosing the pilot. A key step in the proof is to derive lower bounds for the oracle objective under stricter constraints on the experimenter’s decision space.
The optimization problem naturally induces nontrivial dependence among treatment assignments. Motivated by this, we derive asymptotic properties of the estimator under the proposed design, conditioning on the realized assignments. This, in turn, motivates our approach of minimizing the variance of the estimator to achieve precise model-based inference. In a series of extensions, we broaden the framework to (i) incorporate randomization to enable design-based inference and (ii) accommodate partially observed networks.
We conclude with simulation results. The proposed method significantly outperforms state-of-the-art competitors for estimating overall, spillover, and direct effects, especially in the presence of heteroskedasticity and nonzero covariances.
This paper connects to a recent literature in statistics and econometrics that studies experimental design under interference without using pilot information for inference on treatment effects. We show that incorporating a pilot can substantially improve precision. Relevant references include clustered experiments eckles2017design, taylor2018randomized, ugander2013graph and saturation designs baird2018optimal, basse2016analyzing, pouget2018dealing, which typically assume clustered observations. Additional related work includes basse2018model, who assume Gaussian outcomes and no spillover effects; wager2019experimenting, who study sequential randomization for optimal pricing under global interference (without focusing on inference for treatment effects); and kang2016peer, who analyze encouragement designs (without variance-optimal design). basse2018limitations discuss limits of design-based causal inference under interference, and jagadeesan2017designs, sussman2017elements design experiments for direct effects only, whereas we consider a broader class of estimands, including overall and spillover effects. viviano2020policy studies policy inference and welfare under unobserved networks and clusters. To our knowledge, none of these papers study variance-optimal two-wave designs.
We also relate to a large literature on experimental design in the i.i.d.\ batch setting, including one-stage procedures harshaw2019balancing, kasy2016experimenters, kallus2018optimal, barrios2014optimal and two-stage procedures bai2019optimality, tabord2018stratification. However, these works do not address network interference. More broadly, we connect to the literature on treatment effects with interference aronow2017estimating, hudgens2008toward, forastiere2016identification, manski2013identification, leung2019treatment, vazquez2017identification, athey2018exact, goldsmith2013social, savje2017average, ogburn2017causal, kitagawa2020should, viviano2019policy, which focuses on identification and inference rather than variance-optimal experiments.
In this section, we discuss the setup, model, and estimands.
We first introduce necessary notation. We consider $N$ units connected by a binary, symmetric adjacency matrix $\mathbf{A}$, with $\mathbf{A}_{i,j} \in \{0,1\}$. We denote $\mathcal{N}_i = \{j: \mathbf{A}_{i,j} = 1\}$ by the set of neighbors of unit $i$. The adjacency matrix is observed by the researcher. The researcher conducts two experiments: a pilot and the main experiment. For each unit $i \in \{1, \dots, N\}$, we denote \[ R_i = 1\Big\{i \text{ is in the main experiment}\Big\}, \quad P_i = 1\Big\{i \text{ is in the pilot experiment}\Big\}, \] as the participation indicators in the main and pilot experiments, respectively. We let $\sum_{i=1}^N R_i \le \bar{n}$ and $\sum_{i=1}^N P_i \le \bar{m}$ for some pre-specified $\bar{n}$ and $\bar{m}$, which encode constraints on the number of participants in the main experiment and the pilot. For expositional convenience, we assume that $\bar{n}$ is proportional to $N$, i.e., $\bar{n} \propto N$.\footnote{This condition can be relaxed, e.g., by assuming that $\bar{n} \propto N^{c}$ for some constant $c < 1$. In this case, our guarantees continue to hold provided that the conditions on the maximum degree in Assumption (ref) below hold with $\bar{n}$ in lieu of $N$.} We define $n := \sum_{i=1}^N R_i$ as the number of individuals in the main experiment.
Each unit $i$ is associated with an outcome, pre-treatment observables, and a binary assignment, defined as $ (Y_i, T_i, D_i),$ respectively. Here, $T_i$ may depend on $\mathbf{A}$ and covariates (e.g., $T_i = |\mathcal{N}_i|$). Importantly, we assume that $T_i \in \mathcal{T}$, where $\mathcal{T}$ is a discrete set. The discrete support of $T_i$ will play a prominent role when we consider difference-in-means estimators in Example (ref) below.
We define $R_{\mathcal{N}_i} = \big(R_j\big)_{j \in \mathcal{N}_i}$ and $D_{\mathcal{N}_i} = \big(D_j\big)_{j \in \mathcal{N}_i}$ as the vectors of selection indicators and treatments of the neighbors of individual $i$, and \[
\] as the vector of selection indicators and the vector of treatment assignments for participants and their neighbors, respectively. Similarly, $\mathbf{P} = (P_1, \cdots, P_N)$, $\mathbf{T} = (T_1, \cdots, T_N)$, $\mathbf{D} = (D_1, \cdots, D_N)$, and $\mathbf{1} = (1, \cdots, 1) \in \mathbb{R}^N$. Throughout our discussion, we fix $\mathbf{A}$ and $\mathbf{T}$ (i.e., $\mathbf{A}$ and $\mathbf{T}$ are non-random), unless otherwise specified. We postulate nonreversible treatments; i.e., for pilot units with $D_i = 1$, the treatment status cannot be changed.
We let $Y_i(\mathbf{d})$ denote the potential outcome as a function of the treatment assignments $\mathbf{d} \in \{0,1\}^N$, with $Y_i = Y_i(\mathbf{D})$.
Assumption (ref) states that each individual’s outcome depends only on their neighbors’ treatment assignments through a known function $g_i$. Here, $g_i$ is the exposure mapping aronow2017estimating and can be an arbitrary function (with discrete support) of $\mathbf{A}$, $\mathbf{T}$, and the neighbors’ treatments. In addition, once we condition on the exposure mapping, the network affects the outcome variable through arbitrary observables $T_i$. Finally, since $\varepsilon_i(\mathbf{d})$ is constant in $\mathbf{d}$, we write the unobservable simply as $\varepsilon_i$, omitting its argument.
Our framework encompasses several examples of interest, including exposure mappings that depend on the number or share of treated neighbors, whether at least one neighbor is treated, or interactions between the number of treated neighbors and observable characteristics of the neighbors. Assumption (ref) is consistent with local interference assumptions often documented in practice cai2015social or studied in theoretical analyses leung2019treatment. Local interference is testable athey2018exact. Throughout the rest of our discussion, we denote
the expectation of the potential outcome evaluated at individual treatment $d$, exposure $s$, and individual-level covariate $l$.
We allow $(T_i, D_i)$ to exhibit arbitrary dependence. Instead, we impose restrictions on the dependence structure of the unobservables $\varepsilon_i$.
The first condition in Assumption (ref) states that unobservables of non-adjacent units are independent, while $\varepsilon_i$ and $\varepsilon_{\mathcal{N}_i}$ may be statistically dependent. The second condition states that pairs of neighbors share the same joint distribution whenever their $(T_i, T_j)$ match. One-degree dependence is imposed for expository convenience and can be relaxed to higher-order dependence up to degree $M$, as discussed below.
Without further restrictions on the network topology, dependence may be arbitrary, making inference difficult. In this paper, we consider sparse networks in which the maximum degree grows sufficiently slowly relative to $N$.
Assumption (ref) is common in the dependency-graph literature (e.g., ross2011fundamentals) and imposes restrictions on the network topology. It holds for economic models with bounded degree de2018identifying. Economic applications where Assumption (ref) holds include the Add Health Study jackson2012social and, in development settings, cai2015social, among others.\footnote{See, e.g., footnote 7 in de2018identifying and footnote 37, p. 1879, in jackson2012social.} Assumption (ref) fails in the presence of a few units (hubs) with very large degree, such as in a star network. Dense networks, although interesting, are outside the scope of this paper.
Our main goal is to conduct precise inference on user-specific linear estimator of the form
where $w_{\mathbf{A},\mathbf{T}}(\cdot)$ are user-specified (known) function of the main-experiment treatment assignments and the participant indicators $\mathbf{R}$. Examples include simple difference-in-means estimators, stratified weighted differences (e.g., tabord2018stratification), and linear-regression estimators. Linearity in $Y_i$ rules out nonlinear outcome estimators such as feasible two-stage generalized least squares.
The ultimate goal is to conduct inference on the estimand
We write $\tau := \tau_{\mathbf{A},\mathbf{T}}(\mathbf{R},\mathbf{D}^R)$ when clear from context, leaving implicit its dependence on $\mathbf{R}$ and $\mathbf{D}^R$. Following abadie2017sampling, we refer to $\tau$ as a model-based estimand since it is a function of $(\mathbf{R},\mathbf{D}^R,\mathbf{A},\mathbf{T})$ and its causal interpretation relies on the researcher’s maintained model that motivates the chosen estimator $\widehat{\Gamma}$.
The above examples underscore that $\tau$ admits a causal interpretation under the model posited by the researcher. Such models are common in experimental economics; see, e.g., muralidharan2017general,kreindler2023optimal,egger2019general. Therefore, whenever $\hat{\Gamma}$ is unbiased for $\tau$ conditional on $(\mathbf{R},\mathbf{D}^R)$, a natural objective is to minimize its conditional variance. Valid confidence intervals for $\tau$ can then use the the conditional variance (see Theorem (ref) and abadie2017sampling).
Minimizing the conditional variance has a long tradition in experimental design, dating back to information-theoretic optimality for i.i.d.\ data and linear models john1975d. Specifically, define
the smallest conditional variance of $\hat{\Gamma}$ (implicitly a function of $\mathbf{A},\mathbf{T}$) with $\bar n$ participants in the main experiment.
We seek an experiment with the following properties: select a pilot and main-experiment participants $(\mathbf{P},\mathbf{R})$, together with a distribution of treatments $\mathbf{D}$, such that
while imposing that no more than $\bar n$ units are in the main experiment and no more than $\bar m$ units are in the pilot study. Here, $\zeta\ge 0$ is a user-chosen tuning parameter governing allowable optimization slack (we will take $\zeta=0$ unless otherwise specified).
There are two main considerations. First, researchers may not know the variance of the estimator and will need a pilot to estimate it, raising the question of how to choose the pilot while guaranteeing unbiasedness. Second, the design that minimizes the conditional variance does not necessarily randomize treatments, since its goal is precise inference on a model-based estimand. It is therefore natural to ask whether one can introduce randomization to enable design-based inference on hypotheses of independent interest (e.g., on sharp null hypotheses). For expositional convenience, we focus first on settings where the experiment may not necessarily allow for design-based inference. Section (ref) and Appendix (ref) extend our framework to allow for randomization and design-based inference by letting $\zeta > 0$.
Finally, Section (ref) extends the framework to multiple estimands by minimizing the worst-case variance across their corresponding estimators.
This section presents the experimental protocol. We begin with a brief overview and then formalize the pilot (Algorithm (ref)) and the main experiment (Algorithm (ref)). We defer a complete discussion of the practical choice of tuning parameters to Section (ref), which provides an explicit guide for practitioners.
The algorithm proceeds as follows:
We now provide details on each of these steps.
The first step is selecting the pilot study. If pilot outcomes inform the main-experiment design, then selecting any pilot unit or any neighbor of a pilot unit for the main experiment makes $\mathbf R$ and $\mathbf D^R$ statistically dependent on those units’ unobservables. This violates unconfoundedness and the first condition in (ref).
Figure (ref) illustrates the issue. In the figure, the pilot set includes nodes N4, N5, and N6. Because their outcomes inform the main-experiment design, treatments depend on the unobservables of these pilot units. Since pilot units are statistically dependent on their neighbors (e.g., N7), selecting N7 would make selection depend on both treatments and unobservables in the main experiment, thereby confounding the design. First, define
the set of pilot units and their neighbors. The experiment is unconfounded if it satisfies the following restrictions.
The proof is in Appendix (ref). Proposition (ref) provides sufficient conditions for unbiasedness conditional on $\mathbf R$ and the treatment assignments.
The first condition states that unobservables for units outside $\mathcal J$ (i.e., all units except the pilot units and their neighbors) are independent of assignment and selection, conditional on $(\mathbf A,\mathbf T,\mathbf P)$. The second condition requires that pilot selection depend only on $(\mathbf A,\mathbf T)$. The third condition excludes the pilot units and their neighbors from the main experiment.
Proposition (ref) yields two insights: (a) pilot participants can be selected using only network information (and types); (b) the larger the set $\mathcal J$ (pilot units plus their neighbors), the stricter the exclusion constraint on the second wave.
Accordingly, Algorithm (ref) chooses pilot units to minimize $|\mathcal J|$. It also requires that some neighbor pairs are within the pilot to identify and estimate covariances; treatments in the pilot are then randomized. The optimization problem in (ref) is min-cut optimization program: it finds a set of units that are well separated from the remainder, subject to constraints on the number of pilot units and on the number of within-pilot neighbor pairs.
The corollary illustrates that the proposed algorithm yields unbiased estimators of treatment effects.
Finally, the main statistical goal of the pilot is to learn the variance and covariance functions: $ \mathrm{Var}\Big(Y_i\Big|A, D_i, T_i, D_{\mathcal{N}_i}, \mathbf{P}\Big), \quad \mathrm{Cov}\Big(Y_i, Y_j\Big|A, D_i, D_j, D_{\mathcal{N}_i}, D_{\mathcal{N}_j}, T_i, T_j, \mathbf{P}\Big). $
The following lemma guarantees identification.
The proof is in Appendix (ref). Building on the lemma above, estimation of $\sigma^2$ and $\eta$ can be carried out by a variety of methods; the rate of convergence affects the precision of the estimator in the main experiment. We denote by \[ \big(\widehat\sigma_p^{2},\, \widehat\eta_p\big) \] the variance and covariance functions estimated from the pilot study. Section (ref) and Algorithm (ref) provide concrete estimation examples and practical recommendations for implementing Algorithm (ref), including the choice of $\delta, \widehat\sigma_p^{2},\, \widehat\eta_p$.
We now discuss the main experiment (Algorithm (ref)). Throughout, we omit the explicit dependence of the weights on $(\mathbf A,\mathbf T)$ and write $w(i;\mathbf R,\mathbf D^R)$ for brevity.
Given the pilot selection $\mathbf P$, the main experiment design minimizes a plug-in estimate of the variance. Formally, define
The first term captures heteroskedastic variances; the second captures covariances between neighbors, both estimated from the pilot.\footnote{In the presence of higher-order interference, we also add additional components which depend on higher-degree neighbors. See Appendix (ref). }
The optimization problem is in Equation (ref). The minimization is with respect to the participation indicators and the treatment assignments. The optimization problem selects a number of participants in the interval $n \in \{\underline{n}, \underline{n}+ 1, \cdots, \bar{n}\}$, with $\underline{n} < \bar{n}$, denoting a lower bound on the number of participants. The upper bound $\bar{n}$ typically arises due to cost constraints for the researcher. The lower bound $\underline{n}$ guarantees that sufficiently many units are selected in the main experiment useful in our theoretical derivation. In particular, our theoretical guarantees (Section (ref)) will impose that $\underline{n}/\bar{n} \in (0,1)$, requiring researchers some slackness factors in the smallest and largest sample size (we recommend $\underline{n} \ge 2 \bar{n}/3$). In practice, such lower bound is non-binding when the estimator's standard error is decreasing in the same size, although it can improve optimization error in few instances. Additional constraints on $R_i$ or $D_i$, although omitted for brevity, may be included without affecting our theoretical guarantees.\footnote{For example, only some units can participate in the experiments, corresponding to constraints on $R_i = 0$ for some of the units. An alternative constraint is to impose $D_i \times R_i \ge D_i$. This constraint imposes that those units which are not selected as participants have treatment assignments equal to zero.}
The constraint in Equation (ref) illustrates the trade-off in the selection of the pilot study: the larger the pilot study, the more precise the estimator of the variance. However, the larger the pilot study, the larger the set $\mathcal{J}$ and therefore, the more stringent the constraint imposed in the above optimization procedure.
Finally, Algorithm (ref) returns a variance estimator for inference on the main effect $\tau$. Consistency of the variance estimator $\widehat{V}$ in Equation (ref) requires consistent estimation of $m(d,s,l)$ using data from the main experiment (at a possibly slow rate). As formalized in Theorem (ref) below, $\hat m$ may be a parametric (as in Example (ref)) or nonparametric estimator (e.g., leung2019treatment) depending on the researcher's modeling assumption. Precise conditions are collected in Assumption (ref).
Next, we study how the variance of the estimator obtained from the two-wave experiment in Section (ref) compares with the variance of the oracle study. Specifically, we study \[ \mathbb{V}\!\Big(\widehat{\Gamma}\ \big|\ \mathbf{R}, \mathbf{D}^R, \mathbf{A}, \mathbf{T}\Big) \;-\; \mathbb{V}_{\bar{n}}^\star, \] where $(\mathbf{R},\mathbf{D}^R)$ solve the two-wave design problem in (ref). We refer to $\mathbb{V}_{\bar{n}}^\star$ as the variance attainable by an oracle experimentalist who optimally selects participants and assigns treatments with ex-ante perfect knowledge of the population variance and covariance functions (without a pilot). The oracle selects exactly $\bar{n}$ individuals for the experiment, corresponding to the upper bound in our feasible design.\footnote{We use this restriction in our theoretical results; it can be relaxed to an oracle that selects any number of participants between $\underline{n}+|\mathcal{J}|$ and $\bar{n}$. In the asymptotic regime where the pilot size grows more slowly than the main-experiment size, we have $|\mathcal{J}|/\underline{n} \lesssim \mathcal{N}_{\max}\,\bar{m}/\underline{n} = o(1)$ for $\underline{n}$ large relative to the maximum degree $\mathcal{N}_{\max}$ and the pilot size $\bar{m}$.}
Before stating our first theorem, we impose the following conditions.
Assumption (ref) quantifies the pilot-based convergence of the variance and covariance functions. For parametric estimators, the rate is typically $\bar{m}^{-1/2}$. This assumption is not required for inference in the main experiment, but it is invoked to study regret properties: if the pilot estimates poorly approximate the variance and covariance functions, the design may be less precise.
Assumption (ref) imposes bounded outcomes.\footnote{One can weaken it to sub-Gaussian tails at the cost of heavier notation.} The final assumption is a stability condition on the weights.
Assumption (ref)(i) states that, holding the inclusion of unit $i$ and its neighbors fixed, the weight for unit $i$ cannot change by more than a constant multiple of the relative change in sample size across two designs; this is a mild stability requirement. Part (ii) requires that the resulting design produce bounded weights. This is typically satisfied by the algorithm, since unbounded weights would make the variance objective equal to infinity and can also be enforced directly as an additional constraint in Algorithm (ref).
\paragraph{Example (ref) cont'd} Consider the weights in Example (ref). Then Assumption (ref) holds if the weights are bounded by a universal constant, i.e., \[ \sum_{l} v(l)\, \min \left\{ \frac{\sum_{j} I_j(d,s,l)}{n},\ \frac{\sum_{j} I_j(d',s',l)}{n} \right\} \;>\; 1/\bar{C}, \] with $I_j(\cdot)$ as defined in Example (ref), for some finite $\bar{C}>0$. Therefore, Assumption (ref) holds for the difference-in-means estimator under a uniform boundedness restriction on the weights, which can be imposed by design in Algorithm (ref). \qed
The proof is in Appendix (ref). Theorem (ref) characterizes the difference between the variance of the experiment with a pilot and the variance of the oracle experiment with known variance and covariance functions. The result highlights a trade-off: (i) a larger pilot reduces estimation error, and (ii) a larger pilot also tightens the design constraints, potentially increasing regret relative to the oracle. A key challenge in the proof is comparing the constrained design with its oracle counterpart, which assigns treatments without restrictions induced by the pilot study.
An important assumption is that the network is sufficiently sparse. For instance, we require the minimum experiment size $\underline{n}$ to exceed (by a proportional factor) the product of the maximum degree and the pilot size. This condition is satisfied in large samples when $\mathcal{N}_{\max}$ is small relative to $N$ (and hence to $\underline{n}$), i.e., under Assumption (ref). It fails in dense networks such as a star, where $\mathcal{N}_{\max}=N$.
To our knowledge, this is the first result that formally characterizes the pilot size relative to the main experiment.
We conclude with asymptotic inference for the target estimand.
Condition (i) rules out degeneracy of the variance. Condition (ii) requires that the conditional-mean estimator $\hat{m}$ used in the variance formula be consistent at a rate as slow as $o_p(n^{-1/4})$. The condition can be met by semiparametric estimators that converge more slowly than $n^{-1/2}$.
The proof is in Appendix (ref). Theorem (ref) establishes asymptotic normality for a broad class of linear estimators. Notably, inference does not require rate conditions for the pilot estimators of the variance and covariance functions. Asymptotic properties of estimators for network data have been studied in various contexts ogburn2017causal, chin2018central, savje2017average. Here, we derive asymptotics conditionally on the entire assignment mechanism.
In this section, we sketch main extensions and defer formal details to Appendix (ref).
Appendix Algorithm (ref) modifies Algorithm (ref) to allow for randomization. Specifically, first, we compute the optimal selection of participants and assignments in the main experiment using pilot information as before. Second, we re-randomize treatments: for each experimental participant $i$ with $R_i=1$, we independently randomize the treatment assignment to be equal to the optimal assignment with probability $1-\iota$, and accept the proposed new assignment only if its plug-in variance does not exceed the plug-in variance at the optimum by more than a small slack $\zeta/\bar n$. If the proposal fails this variance cap, we re-randomize until it passes.
Algorithm (ref) is designed so that, in addition to the model-based inference of Theorem (ref) (which remains valid), one may perform design-based inference on hypotheses of independent interest. This is possible using e.g., procedures in puelz2022graph by simulating from the same randomization scheme in Step 2 of Algorithm (ref), after conditioning on the optimal solutions in Equation (ref).
The parameters $\iota$ and $\zeta$ trade off additional randomization against precision for model-based inference: larger $\iota$ increases randomization away from the optimizer; larger $\zeta$ admits more variance inflation. We formalize this intuition in Appendix Theorem (ref) where we show that the regret bound on the conditional variance now holds as in our main Theorem (ref) up to the slack parameter $\zeta$.
As a second extension, we extend the results to settings with a finite set of estimands, each paired with a (linear) estimator. Let $\mathcal W=\{w^1,\ldots,w^E\}$ with $E<\infty$. As in (ref), and omitting the explicit $(\mathbf A,\mathbf T)$ dependence of the weights for brevity, consider
with corresponding model-based estimand $ \tau(w) \;=\; \frac{1}{n}\sum_{i=1}^N R_i\, w\!\big(i;\mathbf R,\mathbf D^R\big)\, m\!\big(D_i,\, g_i(D_{\mathcal{N}_i}),\, T_i\big), $ which is implicitly a function of $(\mathbf A,\mathbf T,\mathbf R,\mathbf D^R)$. Returning to Example (ref), one might be interested separately in direct and spillover effects; then $(w^1,w^2)$ pick out two coordinates of the least-squares weight vector. In principle, it is possible that multiple weights $w$ may correspond to the same estimand $\tau(w)$ under certain modeling assumptions. We abstract from this complication and, motivated by empirical practice, we consider a scenario where, for each estimand, researchers consider a single estimator. In addition, we let $E$ to be finite.
The core idea is to conduct the experiment as in Algorithm (ref), by minimizing the worst-case conditional variance of each of the estimators. Inference and regret bounds follow verbatim as in Section (ref) and formalized in Appendix Theorem (ref).
In this section we first discuss the choice of the tuning parameters and estimators in the experiments. We then provide a set of numerical studies.
Algorithms (ref) and (ref) require (i) tuning choices and (ii) pilot-based estimators of the outcome variance and covariances. Below we give practical defaults.
Lastly, we present our numerical studies. In simulations, we assume $T_i = |\mathcal{N}_i|$ and $g_i\!\big(D_{\mathcal{N}_i}\big) = \sum_{k \in \mathcal{N}_i} D_k$. Define $S_i := \sum_{k \in \mathcal{N}_i} D_k$ and $G_i := S_i/|\mathcal{N}_i|$.
\paragraph{Simulation model.} We specify the conditional variance and covariance functions
where $s$ denotes the number of treated neighbors and $l$ denotes the number of neighbors. The covariance assumes a constant correlation $\alpha$ as in baird2018optimal. We set $\alpha=0.1$ and $\mu=0.5$, and consider $(\beta_1,\beta_2)\in\{(0,0),(0.5,0.5),(0.5,1)\}$, which we label, respectively, “homoskedastic,” “small heteroskedasticity,” and “large heteroskedasticity.” Results for more parameters are reported in Appendix (ref).
Following eckles2017design, we consider outcome models of the form
We use $(\gamma_1,\gamma_2)=(0.5,1)$. These coefficients affect the mean but not the conditional variance of the estimators given $(\mathbf R,\mathbf D^R)$ and thus do not influence variance comparisons across designs.
\paragraph{Network design.} Our main simulations use the village friendship networks of cai2015social. We build two undirected adjacency matrices: (i) a “weak” network with an edge if either member names the other as a friend, and (ii) a “strong” network with an edge only if both name each other. The weak network is denser, while the strong network is sparser. This allows us to study how network density affects the performance of the algorithm. We consider as our population the first five villages, corresponding to $N=832$ nodes in total, and impose that no more than half of the individuals are in the main experiment ($\bar n=416$), with no binding constraints on $\underline{n}$.
We also consider simulated graphs with $N=800$ nodes and a maximum number of participants $\bar n=400$. In particular, we study two models: (i) Erd\H{o}s–R\'enyi (ER): $A_{ij}\stackrel{\text{iid}}{\sim}\mathrm{Bernoulli}(p)$ for $i<j$, symmetrized with zero diagonal, using $p=2/N$; (ii) Barab\'asi–Albert (BA): start from an Erd\H{o}s–R\'enyi graph on $N_0=N/5$ nodes with $p=2/N$. Then, for $t=N_0+1,\ldots,N$, add one node and attach it to $m=2$ existing nodes with probability proportional to their degrees.
We implement Algorithms (ref) and (ref) using the defaults in Section (ref). We solve the MIQP in (ref) exactly with $\bar m=70$ and $\delta=30$. We estimate the conditional mean as \[ \small \hat m_p(d,s,l) \;=\; \hat \gamma_0 + \hat \gamma_1 d + \hat \gamma_2 \,\frac{s}{\max\{l,1\}}, \] where $(\hat{\gamma}_0,\hat{\gamma}_1,\hat{\gamma}_2)$ are the OLS coefficients from regressing $Y_i$ on $\big[1,\ D_i,\ G_i\big]$ using the pilot data $\{(Y_i,D_i,T_i,D_{\mathcal{N}_i}): P_i=1\}$. We then form residuals $ \hat\varepsilon_i \;:=\; Y_i - \hat m_p(D_i, S_i, T_i), S_i=\textstyle\sum_{k\in\mathcal N_i} D_k. $ For the variance, we fit the nonnegative least-squares model in Algorithm (ref) with $ W_i \;=\; \big[\,1,\ D_i,\ G_i\,\big], $ which is a correctly specified model for the variance. As a more flexible alternative, we also consider a fourth-degree polynomial in $(D_i,G_i)$, described below.
For the covariance, we impose a constant correlation $\alpha\in[0,0.3]$ and estimate it by regressing $\hat\varepsilon_i \hat\varepsilon_j$ on $\widehat\sigma_p(T_i,D_i,G_i)\,\widehat\sigma_p(T_j,D_j,G_j)$ over pilot units $(i,j)$ with $j\in\mathcal{N}_i$, as in Algorithm (ref). This constraint reflects prior (approximate) knowledge of small, positive correlations between neighbors.
Given $(\widehat\sigma_p^2,\widehat\eta_p)$, we solve the design problem (ref) over $(\mathbf R,\mathbf D^R)$ using a nonlinear mixed-integer solver (Ant Colony Optimization; dorigo2005ant), with a time limit of 9{,}000 seconds.
\paragraph{Variants of our method.} In addition to our main procedure, we consider three variants. The first variant (ELI with Randomization) follows Algorithm (ref): we independently flip each optimal assignment with probability $\iota\in\{0.05,0.10\}$ for $R_i=1$; for simplicity, we perform a single randomization draw (no re-randomization). The second variant (ELI-Unobs) is described in Appendix (ref) and allows for partial network information: it selects a pilot of 70 units from the sixth village only and assumes the pre-experiment network is observed for the first 200 units in the main village. For missing edges, we use a simple Erd\H{o}s–R\'enyi imputation: draw $p\sim\mathrm{Uniform}(0,1)$ once per replication and, conditional on $p$, draw missing $A_{ij}$ i.i.d.\ $\mathrm{Bernoulli}(p)$. We alternate (a) Monte Carlo evaluation of $\widehat V_{\widehat\sigma_p,\widehat\eta_p}$ over imputed edges and (b) the design optimization over $(\mathbf R,\mathbf D^R)$. Full details are in Appendix (ref). The third variant is the same but instead of using a linear model for the variance (with positivity constraints) it uses a more flexible model with a polynomial transformation of $(D_i,G_i)$ of degree four and the same positivity constraint (defined as ELI flexible).
We benchmark our procedure against a set of alternatives with either $n=400$ or $n_+=470$ (the latter equals $400$ plus the $70$ units used in our pilot). Competitors under the augmented budget are labeled with a “$+$” suffix. We consider:
Table (ref) summarizes our main results on the real-world network by reporting the sampling variance of the estimator(s) across columns indexed by $(\beta_1,\beta_2)$. The left panel uses the network with strong ties; the right panel uses weak ties. The top panel targets only the global (overall) treatment effect, whereas the bottom panel estimates both the direct and the spillover effects (two estimands/two estimators, as in Appendix (ref)). Across all specifications, our proposed method (ELI) uniformly attains the lowest variance relative to all competitors. The gains are larger when $(\beta_1,\beta_2)$ increase—that is, under stronger heteroskedasticity. Consistent with design-based identification, Figure (ref) in the Appendix shows bias is zero.
For observed networks, the two ELI variants—(i) adding randomization and (ii) using a more flexible estimator—perform similarly to the baseline ELI, suggesting these variants have comparable performance to ELI even under greater flexibility. With a partially observed network, the only valid benchmark we consider is random allocation; in this case, ELI again dominates uniformly.
Figure (ref) complements these findings. In the left panel (real-world networks), we plot the percentage reduction in sample size that would be required for the best-performing alternative to match the variance of our main ELI specification for the overall effect. For the “unobserved network’’ case, the comparison is between ELI with a partially observed network and random allocation only. The implied savings are up to 40 percentage points.
In the right panel (simulated networks), we plot the log-variance of ELI against the competitor with the lowest median variance, which randomizes using the same total number of units as ELI (participants plus pilot). Under heteroskedasticity, ELI uniformly outperforms, with larger advantages as heteroskedasticity intensifies. Under homoskedasticity ($( \beta_1,\beta_2 )=(0,0)$), ELI still dominates except in a single case where graph clustering with 70 additional participants slightly outperforms ELI.\footnote{Because the simulated-network analysis does not include a separate cluster as in the real-world setting, we do not report partially observed–network results for simulations.} Additional results are reported in Appendix (ref).
This paper introduced a method for designing experiments under network interference. We proposed a two-wave design that selects participation indicators and treatment assignments to minimize the variance of a pre-specified linear estimator, and we provided the first statistical framework for such two-wave experiments with interference, including regret guarantees.
Our main analysis considers settings in which the complete network is observed. In the Appendix and in simulations, we show how the framework extends to partially observed networks. Our numerical findings suggest that imputing missing edges can reduce the estimator's variance. A comprehensive theoretical analysis of partially observed networks, including model selection for the imputation step, remains an important direction for future work.
We focused on local interference. Future research should study designs under more general interaction structures in which interference propagates across larger portions of the network. Understanding how network topology and alternative exposure mappings affect the performance of the proposed design mechanisms is another open question.