CausalSmith · AI Causal Scientist — exp_bipartite_minimax_design_v1 · Experimentation · AI reviewer score 6.2/10 · pinned commit 4e6bd94 · PDF · Lean code · Slides · arXiv · GitHub

Graph-Adaptive Bernoulli Design for Bipartite Interference

Abstract

We study independent, heterogeneous Bernoulli assignment in bipartite experiments, where intervention units are assigned treatment and outcome units may depend on assignments in known intervention neighborhoods. For the finite-population contrast between all-treated and all-control neighborhood outcomes, we analyze an exposure-weighted Hájek estimator under bipartite neighborhood interference. With bounded potential outcomes, we derive a graph-and-design-dependent envelope that upper-bounds the design-based variance scale of its linearization and can be minimized subject to a positivity-constrained expected-treatment budget. Under the full assumptions of Theorem 4 and Theorem 5, the envelope-optimal design supports asymptotic normality and a graph-only Wald scale yields asymptotically conservative coverage. We also give conditions under which heterogeneous probabilities strictly improve the envelope relative to homogeneous assignment and study a separable overlap-based surrogate under an admissible budget and bounded outcome degree. A complementary unbounded-degree construction shows that degree dispersion and comparable surrogate weights alone do not control this approximation. Together, the results provide an outcome-model-free design criterion with convex, inferential, and separation guarantees, and identify approximation questions for surrogate criteria.

Introduction

Interference often separates the units receiving assignments from the units whose outcomes are measured. In bipartite experiments, treatments are assigned to one set of units, while outcomes are recorded for another set whose members may each depend on several assigned interventions. This structure arises in settings involving suppliers and customers, advertisers and users, providers and patients, or policies and exposed populations. It also creates a design problem: even when assignments are independent, overlapping intervention neighborhoods induce dependence among outcome-level exposure terms.

This paper considers a finite-population bipartite experiment with known graph structure and independent Bernoulli assignment probabilities that may differ across intervention units. The estimand is the average contrast between each outcome unit’s all-treated and all-control neighborhood potential outcomes. Under the bipartite interference restriction in Assumption 1, the exposure-weighted Hájek estimator in Definition 3 uses realized all-treated and all-control neighborhood exposures. The design question is how to allocate a fixed expected number of treated intervention units when potential outcomes are unavailable at the design stage.

The answer studied here is a conservative design criterion. Theorem 2 gives an outcome-model-independent graph envelope under heterogeneous Bernoulli assignment with $0 < p_{k} < 1$ and bounded potential outcomes. When the budget is admissible, we minimize this upper bound over the feasible class in Definition 1, which imposes both a positivity floor and a fixed expected-treatment budget. This yields a graph-adaptive allocation with an auditable robustness interpretation before outcomes are observed.

The criterion targets an analytically convenient uniform variance upper bound over the bounded-outcome class. Its value is that the objective is observable before randomization, permits an exact convex formulation, and comes with formal separation and inference guarantees. It provides a robust graph-only benchmark for subsequent numerical comparisons with homogeneous, clustered, and outcome-informed alternatives.

The paper’s closest literatures differ in either the assignment law, the information used to choose a design, or the target of optimization.

Scope of the graph-only heterogeneous-probability criterion relative to related approaches.
Approach	Assignment law	Outcome information in design	Objective and deliverable
Homogeneous bipartite Bernoulli analysis (Lu et al., 2025)	Common Bernoulli probability	None	Design-based estimation, asymptotic inference, and conservative variance analysis under homogeneous assignment.
Graph-cluster and bipartite-cluster designs (Ugander et al., 2020; Brennan et al., 2022)	Correlated assignment induced by clusters	Depends on the design objective and model restrictions	Cluster construction to alter exposure probabilities, spillovers, bias, power, or minimax performance.
Exposure-reweighted or model-based bipartite methods (Harshaw et al., 2021; Doudchenko et al., 2020)	Varies by method	Exposure or response-model structure in the cited approaches	Estimation or design criteria tailored to those specified structures.
This paper	Independent heterogeneous Bernoulli probabilities	None beyond the observed bipartite graph	Convex minimization of an analytically convenient bounded-outcome variance upper bound, a strict objective-separation diagnostic, and bounded-degree surrogate analysis.

The first contribution is a covariance representation that separates graph-and-design loads from unknown centered potential outcomes. Theorem 1 recovers the homogeneous Bernoulli case, in which same-exposure loads depend on the size of shared neighborhoods. Theorem 2 extends this representation to heterogeneous independent probabilities and establishes the corresponding envelope under bounded potential outcomes. This extension captures an intervention’s full role in outcome-pair overlap beyond its intervention-side incidence.

The second contribution concerns the allocation problem induced by that envelope. Under an admissible positivity floor and budget, Theorem 3 establishes existence of an envelope minimizer and characterizes it with first-order conditions. The associated gradient score aggregates the overlap contribution of an intervention across outcome pairs. Theorem 6 shows that, when homogeneous-point scores differ and the homogeneous rate is strictly interior and unequal to one half, a heterogeneous direction strictly improves the envelope and admits a quantitative lower bound. In the special case of singleton outcome neighborhoods, unequal intervention-side incidences are sufficient for this score heterogeneity.

The third contribution studies a computational simplification and its formal scope. The envelope couples probabilities within shared neighborhoods, motivating a separable surrogate under an admissible positivity-constrained budget and bounded outcome degree. Theorem 8 complements this analysis with an unbounded-degree construction in which the approximation ratio diverges despite dispersed intervention-side degrees and comparable surrogate weights. Together, the results motivate reporting outcome-neighborhood and overlap diagnostics as checks when assessing surrogate reliability.

The inferential results remain design based throughout: potential outcomes are fixed, and assignment is the source of randomness. For sequences satisfying the full assumptions of Theorem 4, including outcome indexing and feasible envelope-optimal designs, Theorem 4 establishes a Hájek central limit theorem. Under the full assumptions of Theorem 5, the deterministic graph-only scale in Definition 9 yields asymptotically conservative coverage. The stated bounded-degree regime supplies the local-dependence control supporting both guarantees.

The paper is related to design-based causal inference under interference (Hudgens et al., 2008; Aronow et al., 2017; Sävje et al., 2021), to approximate or structured neighborhood restrictions (Leung, 2019), and to bipartite causal designs (Zigler et al., 2018; Chattopadhyay et al., 2023). Relative to homogeneous Bernoulli bipartite analysis (Lu et al., 2025), the contribution is the graph-dependent heterogeneous-probability envelope and the associated optimization and approximation results. Relative to clustered designs, the assignment law remains independent across intervention units; whether that operational distinction is preferable is application dependent.

The verification appendix describes the precise scope of the formal verification support. The remainder of the paper sets out the experiment, estimator, and feasible design class; develops the envelope, inference, separation, and surrogate results; and discusses the resulting scope and limitations.

Setup and assumptions

At stage $n$ , the experiment assigns interventions to a finite set $I_{n}$ , with $∣ I_{n} ∣ = m_{n}$ , and records outcomes for the outcome-unit set $O_{n}$ of size $n$ . A known bipartite graph $G_{n}$ links intervention units to outcome units. For outcome unit $i$ , its intervention neighborhood $N_{i} (G_{n})$ collects adjacent intervention units and has degree $d_{i}$ . Conversely, let $M_{k} (G_{n})$ denote the outcome units adjacent to intervention unit $k$ , and write $s_{k}$ for its cardinality. These two degree concepts can differ: $d_{i}$ governs the number of assignments entering one outcome’s exposure, whereas $s_{k}$ summarizes the outcomes potentially affected by a given intervention.

The bipartite graph

G_{n}

and its loop-free outcome-overlap graph. Two distinct outcome units are adjacent in the latter exactly when their intervention neighborhoods overlap. The formal dependence bound uses the corresponding closed overlap-neighborhood cardinality, which also counts the outcome itself.

For $i, j \in O_{n}$ , the shared neighborhood $S_{ij} (G_{n})$ equals $N_{i} (G_{n}) \cap N_{j} (G_{n})$ . Distinct outcomes are adjacent in the usual loop-free overlap graph when this set is nonempty. The formal quantity $Δ_{n}$ is instead the maximum cardinality of the closed overlap neighborhood ${j \in O_{n} : S_{ij} (G_{n}) \neq = \emptyset}$ , so it includes $i$ whenever $N_{i} (G_{n}) \neq = \emptyset$ . In the nonempty-neighborhood case it is the conventional overlap-graph degree plus one. Thus, $s_{k}$ measures intervention-side incidence, while $Δ_{n}$ bounds the number of outcome-level exposure terms that can depend on a given term.

We work with a fixed finite-population potential-outcome schedule $Y$ . Specifically, $Y_{i} (z_{N_{i}})$ is the potential outcome induced by a neighborhood assignment vector, and the all-treated and all-control potential outcomes are $Y_{i}^{1}$ and $Y_{i}^{0}$ , respectively. The observed outcome is $Y_{i}^{obs} = Y_{i} (Z_{N_{i} (G_{n})})$ . Let $μ_{1} = n^{- 1} \sum_{i \in O_{n}} Y_{i}^{1}$ and $μ_{0} = n^{- 1} \sum_{i \in O_{n}} Y_{i}^{0}$ , so that the finite-population estimand is $τ_{n} = μ_{1} - μ_{0}$ .

The potential-outcome restriction is as follows.

Assumption 1 [ass:bipartite-interference] (Bipartite interference restriction).

For every $i \in O_{n}$ and every $z, z^{'} \in {0, 1}^{m_{n}}$ , $z_{N_{i} (G_{n})} = z_{N_{i} (G_{n})}^{'} ⟹ Y_{i} (z_{N_{i} (G_{n})}) = Y_{i} (z_{N_{i} (G_{n})}^{'}) .$

⊢ Lean

Assumption 1 is the usual neighborhood-interference restriction for a bipartite experiment: outcome $i$ depends exclusively on assignments in $N_{i} (G_{n})$ . It permits arbitrary interference within a neighborhood while making the exposure mapping graph-based and known to the researcher (Lu et al., 2025).

Assignment follows a finite-population Bernoulli randomization design. Write $Z = (Z_{k})_{k \in I_{n}}$ for the assignment vector, with $Z_{k}$ denoting its coordinate for intervention unit $k$ , and let $p = (p_{k})_{k \in I_{n}}$ denote the probability vector.

Assumption 2 [ass:independent-heterogeneous-bernoulli] (Independent heterogeneous Bernoulli assignment).

For every $k \in I_{n}$ , $Z_{k}$ is Bernoulli with success probability $p_{k}$ , and the collection ${Z_{k} : k \in I_{n}}$ is mutually independent.

⊢ Lean

Assumption 2 allows assignment probabilities to vary across intervention units while retaining independent randomization. This is the design feature that permits adaptation to the observed graph, in the spirit of heterogeneous exposure-based designs (Leung, 2019).

Fix a common positivity margin $0 < ϵ < 1/2$ and an expected-treatment budget $B_{n}$ . The design is subject to both restrictions.

Assumption 3 [ass:positivity-floor] (Assignment positivity).

For every $k \in I_{n}$ , $ϵ \leq p_{k} \leq 1 - ϵ .$

⊢ Lean

Assumption 3 imposes uniform overlap through the positivity floor $ϵ$ . It keeps every relevant exposure probability away from zero once outcome degrees are bounded, preventing unstable inverse-probability weights (Leung, 2019).

Assumption 4 [ass:budget-balance] (Assignment budget balance).

$k \in I_{n} \sum p_{k} = B_{n} .$

⊢ Lean

Assumption 4 fixes the expected number of treated intervention units through the budget $B_{n}$ . This restriction is specific to the present design problem: heterogeneous probabilities may be reallocated across intervention units, but their total must remain fixed.

Together, Assumption 3 and Assumption 4 define the admissible design set.

Definition 1 [def:feasible-designs] (Feasible design class

P_{n, B_{n}, ϵ}

Under Assumption 3 and Assumption 4, with $0 < ϵ < 1/2$ , define $P_{n, B_{n}, ϵ} = {p \in [0, 1]^{m_{n}} : ϵ \leq p_{k} \leq 1 - ϵ for every k \in I_{n}, k \in I_{n} \sum p_{k} = B_{n}} .$

⊢ Lean

The class in Definition 1 is the intersection of a probability box and a budget hyperplane. It therefore isolates the design trade-off of interest: probabilities can respond to graph structure while preserving the experiment’s expected treatment intensity.

For each outcome unit, define the treated exposure indicator $T_{i} (Z)$ as the indicator that every intervention in $N_{i} (G_{n})$ is treated, and define the control exposure indicator $C_{i} (Z)$ analogously. Their design probabilities are $π_{i}^{1} (p)$ and $π_{i}^{0} (p)$ . The inverse-probability denominators are

Definition 2 [def:hajek-denominators] (Hájek denominators

D_{1} (p, Z)

and

D_{0} (p, Z)

Define $D_{1} (p, Z) = i \in O_{n} \sum \frac{T _{i} ( Z )}{π _{i}^{1} ( p )}, D_{0} (p, Z) = i \in O_{n} \sum \frac{C _{i} ( Z )}{π _{i}^{0} ( p )} .$

⊢ Lean

Here, $D_{1} (p, Z)$ and $D_{0} (p, Z)$ normalize the treated- and control-exposure weighted sums. The indicator convention in the next definition assigns value zero to a ratio whose corresponding exposure denominator is zero.

Definition 3 [def:hetero-hajek-estimator] (Hájek estimator

τ_{H} (p)

Define $τ_{H} (p) = 1 {D_{1} (p, Z) > 0} \frac{i \in O _{n} \sum \frac{T _{i} ( Z ) Y _{i}^{o b s}}{π _{i}^{1} ( p )}}{D _{1} ( p , Z )} - 1 {D_{0} (p, Z) > 0} \frac{i \in O _{n} \sum \frac{C _{i} ( Z ) Y _{i}^{o b s}}{π _{i}^{0} ( p )}}{D _{0} ( p , Z )} .$

⊢ Lean

Definition 3 is the exposure-weighted Hájek estimator. Normalization makes the estimator less sensitive to random fluctuations in the number of realized all-treated and all-control exposures than its unnormalized counterpart.

Its first-order behavior is described by the following centered summands.

Definition 4 [def:first-order-linearization] (Linearization summand

η_{i} (p, Z)

For each $i \in O_{n}$ , define $η_{i} (p, Z) = (\frac{T _{i} ( Z )}{π _{i}^{1} ( p )} - 1) (Y_{i}^{1} - μ_{1}) - (\frac{C _{i} ( Z )}{π _{i}^{0} ( p )} - 1) (Y_{i}^{0} - μ_{0}) .$

⊢ Lean

The summands in Definition 4 inherit a dependency graph from outcome-neighborhood overlap. Their scaled average has variance

Definition 5 [def:variance-scale] (Variance scale

σ_{G_{n}, p}^{2} (Y)

For a working finite design $D$ , define $σ_{G_{n}, D, p}^{2} (Y) = n Var_{D} (\frac{1}{n} i \in O_{n} \sum η_{i} (p, Z)) .$ When $D$ is the heterogeneous Bernoulli design indexed by $p$ , abbreviate this quantity as $σ_{G_{n}, p}^{2} (Y)$ .

⊢ Lean

The variance scale $σ_{G_{n}, p}^{2} (Y)$ is design based: potential outcomes are held fixed and variation is taken only over the assignment mechanism.

We next construct a graph-only upper envelope for this scale. The treated and control covariance loads, $r_{ij}^{1} (G_{n}, p)$ and $r_{ij}^{0} (G_{n}, p)$ , quantify the inverse-probability amplification arising from the shared neighborhood of $i$ and $j$ . The cross-exposure load $r_{ij}^{10} (G_{n})$ records whether that shared neighborhood is nonempty. These quantities depend only on $G_{n}$ and, for the same-exposure loads, on $p$ .

Definition 6 [def:graph-envelope] (Graph envelope

V_{env} (G_{n}, p)

Define $V_{env} (G_{n}, p) = \frac{4}{n} i, j \in O_{n} \sum {r_{ij}^{1} (G_{n}, p) + r_{ij}^{0} (G_{n}, p) + 2 r_{ij}^{10} (G_{n})} .$

⊢ Lean

The graph envelope $V_{env} (G_{n}, p)$ replaces unknown outcome contrasts by a uniform bound, thereby making the design criterion observable before randomization. The envelope-optimal design is

Definition 7 [def:optimal-design] (Envelope-optimal design

p_{n}^{*} (G_{n})

Whenever the minimizer set is nonempty, define $p_{n}^{*} (G_{n}) \in argmin_{p \in P_{n, B_{n}, ϵ}} V_{env} (G_{n}, p) .$

⊢ Lean

Definition 7 selects $p_{n}^{*} (G_{n})$ from the feasible envelope minimizers. To characterize its allocation of probability mass, we use the coordinatewise envelope score.

Definition 8 [def:kkt-gradient] (Envelope gradient score

g_{k} (G_{n}, p)

Define $g_{k} (G_{n}, p) = \frac{1}{n} i, j \in O_{n} : k \in S_{ij} (G_{n}) \sum ⎩ ⎨ ⎧ - ℓ \in S_{ij} (G_{n}) \prod p_{ℓ}^{- 1} p_{k}^{- 1} + ℓ \in S_{ij} (G_{n}) \prod (1 - p_{ℓ})^{- 1} (1 - p_{k})^{- 1} ⎭ ⎬ ⎫ .$

⊢ Lean

Definition 8 gives the partial derivative of one quarter of the envelope. Its dependence on all pairs sharing intervention unit $k$ shows that design value incorporates the full overlap pattern beyond direct degree.

For implementation, we also consider a separable surrogate. Define the overlap-derived first-order weight $h_{k} (G_{n}) = \frac{1}{n} i, j \in O_{n} : k \in S_{ij} (G_{n}) \sum ∣ S_{ij} (G_{n}) ∣^{- 1} .$ These weights average pairwise overlaps and reduce to degree-based summaries under additional graph structure.

Definition 9 [def:conservative-variance-estimator] (Conservative variance estimator

V_{cons} (G_{n}, p)

Define $V_{cons} (G_{n}, p) = V_{env} (G_{n}, p) .$

⊢ Lean

The retained notation $V_{cons} (G_{n}, p)$ denotes a deterministic graph-and-design scale known before randomization.

Definition 10 [def:surrogate-design] (Surrogate design

p_{n}^{d e g} (G_{n})

Whenever the minimizer set is nonempty, define $p_{n}^{d e g} (G_{n}) \in argmin_{p \in P_{n, B_{n}, ϵ}} k \in I_{n} \sum h_{k} (G_{n}) {p_{k}^{- 1} + (1 - p_{k})^{- 1}} .$

⊢ Lean

Definition 10 selects the computationally separable design $p_{n}^{d e g} (G_{n})$ . Its performance relative to the envelope optimum is measured by

Definition 11 [def:approximation-ratio] (Approximation ratio

α_{cert} (G_{n})

Define $α_{cert} (G_{n}) = ⎩ ⎨ ⎧ \frac{V _{env} ( G _{n} , p _{n}^{d e g} ( G _{n} ) )}{V _{env} ( G _{n} , p _{n}^{*} ( G _{n} ) )}, 1, if 0 < V_{env} (G_{n}, p_{n}^{*} (G_{n})), otherwise .$ Here, each design selector equals its respective feasible minimizer when one exists, and equals the homogeneous budget vector otherwise.

⊢ Lean

The approximation ratio $α_{cert} (G_{n})$ adopts a zero-loss convention when the optimal envelope is zero.

For later comparison with homogeneous assignment, let $ρ = B_{n} / m_{n}$ and set $p_{k}^{hom} = ρ$ for every $k \in I_{n}$ . Write $Δ_{g}$ for the difference between the largest and smallest values of $g_{k} (G_{n}, p^{hom})$ , and let $a$ and $b$ index the corresponding extremal scores. The largest symmetric budget-feasible displacement from $p^{hom}$ in direction $e_{b} - e_{a}$ is denoted by $η_{box}$ , where $e_{k}$ is the $k$ th coordinate vector. The associated directional second-order modulus $L_{ab}$ is $L_{ab} = q \in P_{n, B_{n}, ϵ} sup (e_{b} - e_{a})^{⊤} Hess {V_{env} (G_{n}, q) /4} (e_{b} - e_{a}) .$ The supremum is explicitly over the feasible probability domain. Positivity therefore supplies a compact domain on which application-specific finite bounds on this directional curvature can be obtained.

The large-sample results impose regularity on potential outcomes and graph dependence.

Assumption 5 [ass:bounded-outcomes] (Bounded potential outcomes).

For every $i \in O_{n}$ , $∣ Y_{i}^{1} ∣ \leq 1 and ∣ Y_{i}^{0} ∣ \leq 1.$

⊢ Lean

Assumption 5 is a standard bounded finite-population potential-outcome condition. It keeps the potential-outcome component of exposure-weighted summands uniformly bounded in the design-based model.

Assumption 6 [ass:bounded-outcome-degree] (Bounded outcome degree).

$0 < \overset{ˉ}{d} and i \in O_{n} max d_{i} \leq \overset{ˉ}{d} .$

⊢ Lean

Assumption 6 keeps every outcome neighborhood uniformly small through the positive constant $\overset{ˉ}{d}$ . Together with uniform positivity, it limits the number of assignment factors entering all-treated and all-control exposure probabilities.

Assumption 7 [ass:bounded-overlap-dependency] (Bounded overlap dependency).

$0 < \overset{ˉ}{D} and Δ_{n} \leq \overset{ˉ}{D} .$

⊢ Lean

Assumption 7 bounds outcome-level dependence by the positive constant $\overset{ˉ}{D}$ . It is the standard dependency-graph sparsity condition that permits a central-limit argument despite interference among overlapping neighborhoods (Aronow et al., 2017).

Finally, inference requires an asymptotically positive variance scale under the optimal design.

Assumption 8 [ass:variance-nondegenerate] (Nondegenerate variance scale).

$n \to \infty lim inf σ_{G_{n}, p_{n}^{*} (G_{n})}^{2} (Y) > 0.$

⊢ Lean

Assumption 8 excludes sequences in which the design-based fluctuation of the linearized estimator degenerates. Such a lower-bound condition is standard for asymptotic normal approximation under interference (Lu et al., 2025).

Main results

This section characterizes the design-based variance of the Hájek linearization, then studies the graph-only envelope as a conservative allocation criterion. The outcome-agnostic criterion protects against the bounded potential-outcome schedules permitted by Assumption 5. It provides an exploratory design-stage rule for reallocating a fixed expected treatment budget using observed overlap structure. Related design-based analyses under interference likewise distinguish the randomization distribution from an outcome model (Aronow et al., 2017; Sävje et al., 2021).

We first recover the familiar homogeneous Bernoulli expressions as a special case. When all intervention units receive the same probability, only the size of the shared neighborhood determines the same-exposure covariance loads.

Theorem 1 [prop:homogeneous-reduction] (Homogeneous Bernoulli Reduction).

Under Assumption 2, suppose that the assignment probabilities are constant, $p_{k} = p$ for every $k \in I_{n}$ , for some $p \in (0, 1)$ . Then, for every $i, j \in O_{n}$ , $r_{ij}^{1} (G_{n}, p) = {p^{- ∣ S_{ij} (G_{n}) ∣} - 1, 0, ∣ S_{ij} (G_{n}) ∣ > 0, ∣ S_{ij} (G_{n}) ∣ = 0, r_{ij}^{0} (G_{n}, p) = {(1 - p)^{- ∣ S_{ij} (G_{n}) ∣} - 1, 0, ∣ S_{ij} (G_{n}) ∣ > 0, ∣ S_{ij} (G_{n}) ∣ = 0.$ Moreover, $σ_{G_{n}, p}^{2} (Y) = \frac{1}{n} i \in O_{n} \sum j \in O_{n} \sum [r_{ij}^{1} (G_{n}, p) (Y_{i}^{1} - μ_{1}) (Y_{j}^{1} - μ_{1}) + r_{ij}^{0} (G_{n}, p) (Y_{i}^{0} - μ_{0}) (Y_{j}^{0} - μ_{0}) + 2 r_{ij}^{10} (G_{n}) (Y_{i}^{1} - μ_{1}) (Y_{j}^{0} - μ_{0})] .$

⊢ Lean

Theorem 1 shows that homogeneous assignment is governed by overlap counts beyond the marginal degrees of outcome units. It also supplies the benchmark against which the heterogeneous criterion below is compared.

Variance representation and envelope optimization

The next result gives the pairwise covariance representation under heterogeneous assignment and bounds the resulting variance scale by the graph envelope.

Theorem 2 [thm:hetero-envelope] (Heterogeneous envelope kernel).

Suppose that:

(Assignment probabilities.) $0 < p_{k} < 1$ for every $k \in I_{n}$ .
(Design.) Assumption 2 holds with assignment-probability vector $p$ .
(Outcomes.) Assumption 5 holds.

Then, for every $i, j \in O_{n}$ , $E_{p} [η_{i} (p, Z) η_{j} (p, Z)] = r_{ij}^{1} (G_{n}, p) (Y_{i}^{1} - μ_{1}) (Y_{j}^{1} - μ_{1}) + r_{ij}^{0} (G_{n}, p) (Y_{i}^{0} - μ_{0}) (Y_{j}^{0} - μ_{0}) + r_{ij}^{10} (G_{n}) {(Y_{i}^{1} - μ_{1}) (Y_{j}^{0} - μ_{0}) + (Y_{i}^{0} - μ_{0}) (Y_{j}^{1} - μ_{1})} .$ Moreover, $σ_{G_{n}, p}^{2} (Y) \leq V_{env} (G_{n}, p) .$

⊢ Lean

Theorem 2 separates the schedule-dependent covariance terms from their graph-and-design loads. Bounded outcomes make the displayed envelope uniform over the admissible schedule class and give it a conservative design interpretation.

The envelope’s inputs are known before randomization, and its minimization has a convex formulation. The following result establishes existence and provides the corresponding optimality characterization.

Theorem 3 [thm:convex-design] (Convex feasible design).

Let $G_{n}$ be a bipartite experiment with intervention-unit set $I_{n}$ , and let $ϵ, B_{n} \in R$ . Suppose that

(Positivity margin.) $0 < ϵ < 1/2$ ;
(Feasible budget.) $m_{n} ϵ \leq B_{n} \leq m_{n} (1 - ϵ)$ .

Then $P_{n, B_{n}, ϵ}$ is nonempty, compact, and convex, and $p \mapsto V_{env} (G_{n}, p)$ is convex on $P_{n, B_{n}, ϵ}$ . Moreover, there exists a minimizer $p_{n}^{*} (G_{n}) \in P_{n, B_{n}, ϵ}$ such that $V_{env} (G_{n}, p_{n}^{*} (G_{n})) \leq V_{env} (G_{n}, q) for every q \in P_{n, B_{n}, ϵ} .$ For every such minimizer $p_{n}^{*} (G_{n})$ , there exist $λ_{n} \in R$ and functions $ν_{\cdot, n}^{+}, ν_{\cdot, n}^{-} : I_{n} \to R$ such that, for every $k \in I_{n}$ , $ν_{k, n}^{+} \geq 0, ν_{k, n}^{-} \geq 0, g_{k} (G_{n}, p_{n}^{*} (G_{n})) = λ_{n} - ν_{k, n}^{+} + ν_{k, n}^{-},$ and $ν_{k, n}^{+} ((p_{n}^{*} (G_{n}))_{k} - (1 - ϵ)) = 0, ν_{k, n}^{-} (ϵ - (p_{n}^{*} (G_{n}))_{k}) = 0.$

⊢ Lean

Theorem 3 places the allocation problem in a standard finite-dimensional convex-optimization form (Boyd et al., 2004). Positivity makes every reciprocal-product term differentiable on the feasible box; convexity, the affine budget equality, and the two coordinate bounds supply the objective and constraint structure. At an interior coordinate, the envelope gradient score equals the common budget multiplier; at a probability bound, complementary slackness gives the corresponding one-sided condition. The formally verified statement covers feasible endpoint budgets directly. Because the objective couples probabilities across shared neighborhoods, the allocation depends on the full overlap score beyond $s_{k}$ , intervention degree, or any single local statistic.

Large-sample inference and design-stage coverage

We next turn to inference for the envelope-optimal design. The central-limit result combines the Hájek linearization with the bounded-degree dependency structure induced by overlapping neighborhoods.

Theorem 4 [thm:hetero-clt] (Heterogeneous Hájek CLT).

Consider a sequence of bipartite experiments indexed by $n$ . Suppose:

(Outcome indexing.) For all sufficiently large $n$ , $∣ O_{n} ∣ = n$ .
(Assignment and interference.) Assumption 2 and Assumption 1 hold at every $n$ for the assignment design $D_{n}$ and probabilities $p_{n}$ .
(Outcome and graph regularity.) Assumption 5, Assumption 6, and Assumption 7 hold at every $n$ , with constants $\overset{ˉ}{d}$ and $\overset{ˉ}{D}$ , respectively.
(Feasibility and optimality.) For every $n$ , $p_{n} \in P_{n, B_{n}, ϵ_{n}}$ as in Definition 1, and $p_{n} = p_{n}^{*} (G_{n})$ as in Definition 7.
(Uniform positivity.) There exists $ϵ_{0} > 0$ such that $ϵ_{0} \leq ϵ_{n}$ for all sufficiently large $n$ .
(Variance.) Assumption 8 holds for $σ_{G_{n}, p_{n}}^{2} (Y)$ as in Definition 5.

Then, for every $δ > 0$ , $D_{n} Pr (n {τ_{H} (p_{n}^{*} (G_{n})) - τ_{n}} - n^{- 1/2} i \in O_{n} \sum η_{i} (p_{n}^{*} (G_{n}), Z) \geq δ) ⟶ 0,$ and, for every $s \in R$ , $D_{n} Pr \frac{n { τ _{H} ( p _{n}^{*} ( G _{n} )) - τ _{n} }}{σ _{G_{n}, p_{n}^{*} (G_{n})}^{2} ( Y )} \leq s ⟶ Pr {N (0, 1) \leq s} .$

⊢ Lean

Theorem 4 is a design-based result: the potential-outcome schedule remains fixed throughout. Uniform positivity and bounded outcome degree control inverse-probability weights, bounded overlap dependency limits the number of dependent exposure terms associated with any outcome, and nondegeneracy supplies positive fluctuation. These familiar dependency-graph conditions define a sparse local-dependence regime (Aronow et al., 2017; Lu et al., 2025).

For applied use, the relevant graph diagnostics are the empirical distributions of $d_{i}$ , intervention incidences $s_{k}$ , and degrees in the outcome-overlap graph. Sequences with uniformly bounded values of the first and third quantities fall within the theorem’s graph scope. These diagnostics therefore make the bounded-local-dependence requirement directly auditable.

The next result translates the same regularity conditions into a Wald interval based on the deterministic graph-only scale of Definition 9.

Theorem 5 [thm:postdesign-wald] (Post-design Wald coverage).

For a sequence of bipartite experiments $G_{n}$ with outcome sets $O_{n}$ , finite assignment designs, probability vectors $p_{n}$ , positivity margins $ϵ_{n}$ , and budgets $B_{n}$ , suppose:

(Outcome indexing.) $∣ O_{n} ∣ = n$ for all sufficiently large $n$ .
(Assignment law.) The assignment design satisfies Assumption 2 with $0 \leq p_{n, k} \leq 1$ for every $n$ and $k \in I_{n}$ .
(Interference and boundedness.) Assumption 1, Assumption 5, Assumption 6, and Assumption 7 hold with constants $\overset{ˉ}{d}$ and $\overset{ˉ}{D}$ .
(Feasibility and optimality.) For every $n$ , $p_{n}$ is a feasible design in the sense of Definition 1, $ϵ_{n} \in (0, 1/2)$ , and $p_{n} = p_{n}^{*} (G_{n})$ in the sense of Definition 7.
(Uniform positivity.) There exists $ϵ_{0} > 0$ such that $ϵ_{0} \leq ϵ_{n}$ for all sufficiently large $n$ .
(Nondegenerate variance.) Assumption 8 holds for $σ_{G_{n}, p_{n}}^{2} (Y)$ .
(Wald critical value.) $α_{cov} \in (0, 1)$ , $z_{1 - α_{cov} /2} \geq 0$ , and $Φ (z_{1 - α_{cov} /2}) = 1 - \frac{α _{cov}}{2} .$

Then, for every $n$ , $σ_{G_{n}, p_{n}}^{2} (Y) \leq V_{cons} (G_{n}, p_{n}),$ where $σ_{G_{n}, p_{n}}^{2} (Y)$ and $V_{cons} (G_{n}, p_{n})$ are as in Definition 5 and Definition 9, respectively; moreover, $1 - α_{cov} \leq n \to \infty lim inf p_{n} Pr ∣ τ_{n} - τ_{H} (p_{n}) ∣ \leq z_{1 - α_{cov} /2} \frac{V _{cons} ( G _{n} , p _{n} )}{n} .$

⊢ Lean

Theorem 5 yields asymptotically conservative coverage using a scale determined entirely by the graph and selected probabilities, giving an outcome-model-free guarantee.

When heterogeneous probabilities improve on homogeneity

The envelope can strictly favor heterogeneity even under a fixed expected treatment budget. To state a quantitative comparison, recall the directional curvature quantity introduced in Section 2. Equivalently, along the budget-preserving direction from the highest-score coordinate $a$ to the lowest-score coordinate $b$ , $L_{ab} = q \in P_{n, B_{n}, ϵ} sup (e_{b} - e_{a})^{⊤} Hess {V_{env} (G_{n}, q) /4} (e_{b} - e_{a}) .$ The supremum ranges only over the feasible probability domain. Since the positivity floor makes that domain compact and keeps every reciprocal probability factor finite, $L_{ab}$ admits finite graph-specific bounds whenever the displayed derivatives are evaluated on that domain.

Theorem 6 [thm:heterogeneity-separation] (Heterogeneity separation).

Let $G_{n}$ be a bipartite experiment with $m_{n} = ∣ I_{n} ∣ > 0$ , and let $ϵ \in (0, 1/2)$ . Suppose that:

(Admissible budget.) $m_{n} ϵ \leq B_{n} \leq m_{n} (1 - ϵ)$ .
(Homogeneous rate.) $ρ = B_{n} / m_{n}$ , with $ϵ < ρ < 1 - ϵ$ and $ρ \neq = 1/2$ .
(Homogeneous design.) $p_{k}^{hom} = ρ$ for every $k \in I_{n}$ .

Then all of the following hold:

If there exist $a, b \in I_{n}$ such that $g_{a} (G_{n}, p^{hom}) \neq = g_{b} (G_{n}, p^{hom}),$ then $p^{hom}$ is not a minimizer of $V_{env} (G_{n}, \cdot)$ over $P_{n, B_{n}, ϵ}$ . Moreover, there exist $a, b \in I_{n}$ attaining, respectively, the maximum and minimum homogeneous-point gradient scores, such that $Δ_{g} := g_{a} (G_{n}, p^{hom}) - g_{b} (G_{n}, p^{hom}) > 0.$ For every $p_{n}^{*} (G_{n}) \in argmin_{p \in P_{n, B_{n}, ϵ}} V_{env} (G_{n}, p)$ , $p_{n}^{*} (G_{n}) \neq = p^{hom}, V_{env} (G_{n}, p_{n}^{*} (G_{n})) < V_{env} (G_{n}, p^{hom}),$ and $V_{env} (G_{n}, p^{hom}) - V_{env} (G_{n}, p_{n}^{*} (G_{n})) \geq 2 Δ_{g} {min {ρ - ϵ, 1 - ϵ - ρ}, min {min {ρ - ϵ, 1 - ϵ - ρ}, Δ_{g} / L_{ab}}, L_{ab} = 0, L_{ab} \neq = 0,$ where $L_{ab}$ is the directional modulus along $e_{b} - e_{a}$ .
If $∣ N_{i} (G_{n}) ∣ = 1$ for every $i \in O_{n}$ , then, for every $k \in I_{n}$ , $g_{k} (G_{n}, p^{hom}) = n^{- 1} s_{k}^{2} ((1 - ρ)^{- 2} - ρ^{- 2}) .$
If $∣ N_{i} (G_{n}) ∣ = 1$ for every $i \in O_{n}$ and there exist $a, b \in I_{n}$ such that $s_{a}^{2} \neq = s_{b}^{2}$ , then the preceding non-homogeneity, strict-improvement, and gap conclusions hold.

⊢ Lean

The singleton-neighborhood case gives a transparent diagnostic: when $ρ \neq = 1/2$ , heterogeneity in intervention-side incidence produces heterogeneous homogeneous-point scores and a strict envelope-improving direction away from homogeneous assignment. More generally, the score spread captures overlap patterns beyond $s_{k}$ alone.

A bounded-degree surrogate and its limitation

The exact envelope couples probabilities across shared neighborhoods. The additive surrogate in Definition 10 removes that coupling and is therefore attractive for implementation. Under bounded outcome degree, its loss relative to the envelope optimum is uniformly controlled.

Theorem 7 [thm:surrogate-certificate] (Surrogate approximation certificate).

For a bipartite experiment on $G_{n}$ , suppose:

(Admissible floor.) $0 < ϵ < 1/2$ .
(Bounded outcome degree.) Assumption 6 holds with bound $\overset{ˉ}{d}$ .
(Admissible budget.) $m_{n} ϵ \leq B_{n} \leq m_{n} (1 - ϵ)$ .

Then, for every $p \in P_{n, B_{n}, ϵ}$ of Definition 1, $k \in I_{n} \sum h_{k} (G_{n}) {p_{k}^{- 1} + (1 - p_{k})^{- 1}} \leq \frac{V _{env} ( G _{n} , p )}{4} \leq max {1, ϵ^{- (\overset{ˉ}{d} - 1)}} k \in I_{n} \sum h_{k} (G_{n}) {p_{k}^{- 1} + (1 - p_{k})^{- 1}} .$ Moreover, the approximation ratio of Definition 11 satisfies $α_{cert} (G_{n}) \leq max {1, ϵ^{- (\overset{ˉ}{d} - 1)}} .$

⊢ Lean

The certificate constant deteriorates with the allowed outcome degree and with a small positivity floor. Reporting $max_{i} d_{i}$ , $ϵ$ , and the resulting bound therefore makes clear when the surrogate guarantee is informative and when it is effectively vacuous.

A natural conjecture is that broad dispersion in intervention-side degrees, combined with the one-sided conditional weight-ratio restriction used below, might itself control the surrogate’s envelope approximation quality. The following result rules out such a conclusion; its counterexample can satisfy equal positive $h$ -weights even though the formal condition is stated one-sidedly.

Theorem 8 [thm:dispersion-certificate-unbounded] (Unbounded dispersion certificate).

For every $ϵ \in (0, 1/2)$ , $c_{disp} > 0$ , and $C_{disp} \geq 1$ , there exist sequences of finite intervention-unit sets $I_{n}$ , finite outcome-unit sets $O_{n}$ , finite bipartite experiments $G_{n}$ , and budgets $B_{n}$ such that, for every $n$ ,

(Admissible budget.) With $m_{n} = ∣ I_{n} ∣$ , $m_{n} ϵ \leq B_{n} \leq m_{n} (1 - ϵ) .$
(Positive energy.) $0 < k \in I_{n} \sum s_{k}^{2} .$

Moreover, for all sufficiently large $n$ ,

(Degree dispersion.) For every $k \in I_{n}$ , $s_{k}^{2} \leq c_{disp} l \in I_{n} \sum s_{l}^{2} .$
( $h$ -weight ratio.) For every $k, l \in I_{n}$ , $h_{l} (G_{n}) > 0 ⟹ h_{k} (G_{n}) \leq C_{disp} h_{l} (G_{n}) .$

Finally, the approximation ratio of Definition 11 satisfies $α_{cert} (G_{n}) ⟶ \infty.$

⊢ Lean

Theorem 8 shows that degree dispersion and the conditional restriction $h_{l} (G_{n}) > 0 ⟹ h_{k} (G_{n}) \leq C_{disp} h_{l} (G_{n})$ cannot replace the bounded-degree condition behind Theorem 7. Thus, the separable rule is best treated as a bounded-degree approximation with an explicit certificate, not as a generally reliable proxy for the full overlap criterion.

Discussion and extensions

The proposed allocation rule uses the observed bipartite graph to choose independent assignment probabilities before outcomes are observed. Its objective is deliberately conservative: $V_{env} (G_{n}, p)$ bounds the design-based variance scale uniformly over the bounded potential-outcome schedules allowed by Assumption 5. The resulting design gives researchers a transparent, outcome-model-free way to reallocate a fixed expected treatment budget.

A prespecified design checklist

The following checklist turns the theoretical scope into a reproducible design-stage comparison using graph and design inputs alone.

Fix capacity and candidate floors. Set $ρ = B_{n} / m_{n}$ from the substantive treatment-capacity constraint. Any candidate floor must satisfy $0 < ϵ \leq min {ρ, 1 - ρ}$ . Prespecify a small grid of substantively acceptable floors inside this interval to insulate the reported gain from floor selection.
Audit graph scope. Report the maximum and selected quantiles of $d_{i}$ , $s_{k}$ , and the closed outcome-overlap-neighborhood sizes. Flag persistent hubs or graph sequences whose maxima grow with $n$ for analysis under growing-degree methods.
Audit exposure support. For every candidate design, compute $π_{i}^{1} (p) = k \in N_{i} (G_{n}) \prod p_{k}, π_{i}^{0} (p) = k \in N_{i} (G_{n}) \prod (1 - p_{k}),$ and report their minima and selected quantiles. An experiment-specific minimum acceptable exposure probability should be chosen before optimization. A candidate that violates it is rejected even if its envelope is smaller.
Compare transparent benchmarks. For each floor, report the homogeneous vector, the exact envelope minimizer when numerically available, and the separable surrogate as an exploratory benchmark. Report $V_{env}$ , the relative envelope reduction from homogeneity, the number of coordinates at each probability bound, the KKT residual for the exact program, and the surrogate ratio.
Apply fallback rules. Retain homogeneous assignment when the envelope reduction is no larger than the declared numerical tolerance, changes sign or is highly unstable across acceptable floors, or requires unacceptable exposure probabilities. Treat the surrogate as exploratory when its empirical performance is too unstable or too weak for the application’s prespecified tolerance. Evaluate clustering as a separate design candidate when cohesive graph regions, hubs, or exposure-support failures make independent assignment unattractive.

Limitations and future work

The numerical tolerances and minimum exposure probability in this checklist are application-specific design inputs, not universal constants supplied by the theory. Publishing the full floor-sensitivity table prevents them from becoming hidden researcher choices. Sparse implementations, computation benchmarks, and simulations relating the envelope to realized variance and coverage remain necessary before recommending routine use.

This perspective differs from clustering-based approaches to interference. Cluster randomization and graph-cluster constructions alter the dependence structure of assignment in order to increase the probability of informative exposures or reduce cross-cluster spillovers (Eckles et al., 2017; Ugander et al., 2020; Brennan et al., 2022). Here the assignment law remains independent across intervention units; adaptation occurs through the probability vector. That distinction can be useful when independent implementation is operationally attractive, when clusters would be difficult to define, or when a fixed expected treatment total is an important design constraint. At the same time, clustering may be preferable when the graph contains cohesive regions for which correlated assignment produces substantially more relevant exposure variation.

The surrogate analysis motivates questions about computational simplification. Under an admissible positivity-constrained budget and bounded outcome degree, the surrogate can be compared with the full overlap criterion using constants determined by the positivity floor and degree bound. Thus, the additive rule should be treated as a substitute for the full overlap criterion only when its reported performance meets the application’s prespecified tolerance.

Theorem 8 characterizes the unbounded-degree behavior of this surrogate perspective. The unbounded-degree construction shows that dispersed intervention-side incidences and the stated one-sided conditional $h$ -weight-ratio restriction do not by themselves prevent the approximation ratio from diverging. In particular, the construction shows that intervention-side degree dispersion need not control higher-order overlap patterns that enter the exact criterion through shared neighborhoods. It therefore suggests reporting outcome-neighborhood and overlap diagnostics, rather than relying on intervention-side degree summaries alone. Related work on low-order and graph-aware experimental designs likewise emphasizes that graph structure beyond marginal degree can matter for design performance (Eichhorn et al., 2024; Harshaw et al., 2021).

Several extensions are natural but are not developed here. First, auxiliary pre-treatment outcomes or credible structural restrictions could support an outcome-informed criterion that targets an estimated variance rather than its uniform envelope. Such an approach would trade the present robustness for dependence on an outcome model and its validation. Second, clustered or dependent assignment mechanisms could be incorporated by replacing the independent-Bernoulli exposure probabilities and covariance loads with those induced by the chosen randomization scheme. Finally, graphs with growing degrees or overlap dependence may require asymptotic conditions tailored to their growth rates, beyond the bounded-degree regime used for Theorem 4. These extensions would connect the present design problem to broader work on network experimentation and optimized randomization (Ugander et al., 2020; Viviano, 2020).

Appendices

Proofs and auxiliary lemmas

This appendix records the auxiliary probability result used by the large-sample analysis: the normal approximation for bounded summands indexed by a sparse dependency graph.

Dependency-graph normal approximation

The linearization summands in Definition 4 are dependent only when their outcome neighborhoods overlap. The next lemma states the bounded-degree central-limit result used to convert that structure into the asymptotic normality asserted in Theorem 4; it is the bounded-summand, bounded-dependency-degree specialization of the dependency-graph normal approximation of Baldi et al. (1989).

Lemma 1 [lem:bounded-degree-dependency-clt] (Bounded-Degree Dependency CLT).

Let ${X_{n, i} : i \in ι_{n}}$ be real-valued random variables, where $∣ ι_{n} ∣ = n$ , under the usual measurability and integrability conditions. Suppose:

(Centered summands.) For every $n$ and $i \in ι_{n}$ , $E [X_{n, i}] = 0$ .
(Dependency degree.) The variables admit a dependency graph whose neighborhood of every $i \in ι_{n}$ has cardinality at most $D$ , for a fixed $D \in N$ .
(Uniform bound.) There is an $M \geq 0$ such that $∣ X_{n, i} ∣ \leq M$ for every $n$ , $i \in ι_{n}$ , and outcome.
(Variance growth.) Writing $S_{n} = \sum_{i \in ι_{n}} X_{n, i}$ , suppose $E [S_{n}^{2}] = v_{n}$ for every $n$ , and, for some $c > 0$ , $v_{n} \geq c n$ for all sufficiently large $n$ .

Then, for every $s \in R$ , $n \to \infty lim Pr (\frac{S _{n}}{v _{n}} \leq s) = Pr (Z \leq s), Z \sim N (0, 1) .$

⊢ Lean

Proof of Lemma 1.

Write $i \sim j$ for adjacency in the dependency graph carried by the array, and write $S_{n} = i \in ι_{n} \sum X_{n, i} .$ The two structural properties of that graph that the argument uses are $∣ {j \in ι_{n} : j \sim i} ∣ \leq D for every n and every i \in ι_{n},$ and: whenever $A, B \subseteq ι_{n}$ satisfy $a \neq \sim b$ for all $a \in A$ and all $b \in B$ , the tuples $(X_{n, a})_{a \in A}$ and $(X_{n, b})_{b \in B}$ are independent.

Step 1 (passage to a tail on which the variance floor holds). The convergence to be proved is a convergence of a sequence indexed by $n$ , so it is unaffected by discarding a finite initial segment. By the variance-growth hypothesis and $∣ ι_{n} ∣ = n$ , there is an $N$ such that $v_{n} \geq c n and ∣ ι_{n} ∣ = n \geq 1 for every n \geq N,$ and it suffices to prove the asserted limit along $n \geq N$ . Fix such an $n$ . Then $v_{n} \geq c n \geq c > 0,$ so $v_{n} > 0$ and division by $v_{n}$ is legitimate.

Step 2 (standardization). Define $Y_{n, i} = \frac{X _{n, i}}{v _{n}} (i \in ι_{n}), so that i \in ι_{n} \sum Y_{n, i} = \frac{S _{n}}{v _{n}} .$ Each $Y_{n, i}$ is the image of $X_{n, i}$ alone under the fixed measurable map $x \mapsto x / v_{n}$ , which does not depend on the outcome; applying this map coordinatewise to a tuple preserves independence, so the very same graph $\sim$ is a dependency graph for ${Y_{n, i} : i \in ι_{n}}$ . In particular the degree bound is unchanged: $∣ {j \in ι_{n} : j \sim i} ∣ \leq D for every i \in ι_{n} .$

The standardized summands are still centered, and their sum has second moment one: $E [Y_{n, i}] = \frac{E [ X _{n, i} ]}{v _{n}} = 0, E (i \in ι_{n} \sum Y_{n, i})^{2} = \frac{E [ S _{n}^{2} ]}{v _{n}} = \frac{v _{n}}{v _{n}} = 1,$ the last equality by the hypothesis $E [S_{n}^{2}] = v_{n}$ and $v_{n} > 0$ .

Step 3 (summand bound and Lyapunov ratio). Put $b_{n} = \frac{M / c}{n} .$ Since $M \geq 0$ and $c > 0$ we have $b_{n} \geq 0$ , and the uniform bound $∣ X_{n, i} ∣ \leq M$ together with $v_{n} \geq c n$ gives, for every $i \in ι_{n}$ and every outcome, $∣ Y_{n, i} ∣ = \frac{∣ X _{n, i} ∣}{v _{n}} \leq \frac{M}{v _{n}} \leq \frac{M}{c n} = b_{n} .$ Moreover $b_{n} ⟶ 0 and ∣ ι_{n} ∣ b_{n}^{3} = n \cdot \frac{( M / c ) ^{3}}{n ^{3/2}} = \frac{( M / c ) ^{3}}{n} ⟶ 0.$

Step 4 (the dependency-graph normal approximation). The array ${Y_{n, i} : i \in ι_{n}}$ now meets, term by term, the hypotheses of the following dependency-graph central limit theorem: if the variables of a triangular array are centered, admit a dependency graph all of whose closed neighborhoods have cardinality at most a fixed $D$ , satisfy a uniform bound $∣ Y_{n, i} ∣ \leq b_{n}$ with $b_{n} \geq 0$ , $b_{n} \to 0$ and $∣ ι_{n} ∣ b_{n}^{3} \to 0$ , and have $E [(\sum_{i \in ι_{n}} Y_{n, i})^{2}] = 1$ , then, for every $s \in R$ , $Pr (i \in ι_{n} \sum Y_{n, i} \leq s) ⟶ Pr (Z \leq s), Z \sim N (0, 1) .$ This is the Stein-method estimate for locally dependent summands: the dependency graph turns the Stein equation into a sum of neighborhood-localized error terms, and the two displayed limits $b_{n} \to 0$ and $∣ ι_{n} ∣ b_{n}^{3} \to 0$ drive those error terms to zero.

Since $\sum_{i \in ι_{n}} Y_{n, i} = S_{n} / v_{n}$ , this reads $n \to \infty lim Pr (\frac{S _{n}}{v _{n}} \leq s) = Pr (Z \leq s), Z \sim N (0, 1),$ for every $s \in R$ , which is the assertion on the tail $n \geq N$ and hence, by Step 1, the assertion itself.

∎

The imported hypotheses map directly to the paper’s primitives. Bounded outcomes, bounded outcome degree, and the positivity floor give a uniform bound on each centered linearization summand. The outcome-overlap graph is a dependency graph because disjoint intervention neighborhoods depend on disjoint independent assignments, and Assumption 7 bounds its closed-neighborhood size. Assumption 8, together with the paper’s normalization, supplies variance growth of order $n$ . These are precisely the boundedness, local-dependence, and nondegeneracy inputs used in the displayed design-based specialization of Baldi et al. (1989).

Convex-program provenance

The KKT characterization used in Theorem 3 is the standard convex-program optimality system for a differentiable objective with affine budget and box constraints (Boyd et al., 2004). The positivity box keeps the reciprocal objective differentiable; the theorem supplies convexity and existence; the budget equality and coordinate bounds are affine. Its displayed multipliers state dual feasibility, stationarity, and complementary slackness coordinate by coordinate. The verified theorem directly includes feasible endpoint budgets and the corresponding optimality conditions.

Verification note.

The theorem and lemma statements, together with their proofs for the finite-design and independent Bernoulli-randomization components, are machine-checked in Lean 4. The formal development takes as hypotheses the experiment-specific bipartite graph and neighborhood structure, the fixed potential-outcome schedule and interference restriction, feasibility and positivity conditions, and the stated asymptotic regularity conditions on outcomes, degrees, overlap dependence, indexing, and variance nondegeneracy. Classical mathematical and probability-theory inputs used by the underlying libraries form the assumed formal substrate.

Proofs of the main results

Proof of Theorem 1.

Recall the three covariance loads. For $i, j \in O_{n}$ and an assignment-probability vector $p = (p_{k})_{k \in I_{n}}$ with $0 < p_{k} < 1$ , $r_{ij}^{1} (G_{n}, p) = 1 {∣ S_{ij} (G_{n}) ∣ > 0} k \in S_{ij} (G_{n}) \prod p_{k}^{- 1} - 1, r_{ij}^{0} (G_{n}, p) = 1 {∣ S_{ij} (G_{n}) ∣ > 0} k \in S_{ij} (G_{n}) \prod (1 - p_{k})^{- 1} - 1,$ $r_{ij}^{10} (G_{n}) = 1 {∣ S_{ij} (G_{n}) ∣ > 0} .$ Throughout the proof, $p$ denotes the probability vector and $ρ \in (0, 1)$ denotes the common homogeneous coordinate, so $p_{k} = ρ$ for every $k \in I_{n}$ . We write $ρ^{- ℓ}$ as shorthand for $(ρ^{ℓ})^{- 1}$ , and similarly for $(1 - ρ)^{- ℓ}$ . We also adopt throughout the reciprocal convention $1/0 = 0,$ so that the symbol $1/ n$ , with $n = ∣ O_{n} ∣$ , is defined for every finite outcome-unit set: it is the ordinary reciprocal when $O_{n} \neq = \emptyset$ and equals $0$ when $O_{n} = \emptyset$ . Every identity displayed below is asserted under this convention, so the degenerate case $O_{n} = \emptyset$ needs no separate hypothesis.

For every $k \in I_{n}$ , homogeneity and $ρ \in (0, 1)$ give $0 < p_{k} = ρ < 1,$ so all exposure probabilities $π_{i}^{1} (p) = \prod_{k \in N_{i} (G_{n})} p_{k}$ and $π_{i}^{0} (p) = \prod_{k \in N_{i} (G_{n})} (1 - p_{k})$ are strictly positive and the reciprocals above are defined.
Fix $i, j \in O_{n}$ . If $∣ S_{ij} (G_{n})∣ > 0$ , substituting $p_{k} = ρ$ into the displayed definition of the treated load yields $r_{ij}^{1} (G_{n}, p) = k \in S_{ij} (G_{n}) \prod ρ^{- 1} - 1 = (ρ^{∣ S_{ij} (G_{n})∣})^{- 1} - 1 = ρ^{- ∣ S_{ij} (G_{n})∣} - 1,$ because the product has $∣ S_{ij} (G_{n})∣$ equal factors. If $∣ S_{ij} (G_{n})∣ = 0$ , the indicator in that definition vanishes and $r_{ij}^{1} (G_{n}, p) = 0$ .
The same split applies to the control load, with $ρ$ replaced by $1 - ρ$ . When $∣ S_{ij} (G_{n})∣ > 0$ , $r_{ij}^{0} (G_{n}, p) = k \in S_{ij} (G_{n}) \prod (1 - ρ)^{- 1} - 1 = ((1 - ρ)^{∣ S_{ij} (G_{n})∣})^{- 1} - 1 = (1 - ρ)^{- ∣ S_{ij} (G_{n})∣} - 1;$ when $∣ S_{ij} (G_{n})∣ = 0$ , it equals $0$ .
It remains to prove the variance-scale identity. Write, for $i \in O_{n}$ , $δ_{i}^{1} = Y_{i}^{1} - μ_{1}, δ_{i}^{0} = Y_{i}^{0} - μ_{0}, A_{i} = \frac{T _{i} ( Z )}{π _{i}^{1} ( p )} - 1, B_{i} = \frac{C _{i} ( Z )}{π _{i}^{0} ( p )} - 1,$ for the centered potential-outcome deviations and the centered inverse-probability weights, so that Definition 4 reads $η_{i} (p, Z) = A_{i} δ_{i}^{1} - B_{i} δ_{i}^{0}$ . Under Assumption 2 the coordinates of $Z$ are independent, so $E_{p} [T_{i} (Z)] = k \in N_{i} (G_{n}) \prod p_{k} = π_{i}^{1} (p), E_{p} [C_{i} (Z)] = k \in N_{i} (G_{n}) \prod (1 - p_{k}) = π_{i}^{0} (p),$ both strictly positive by the coordinate bounds above; hence $E_{p} [A_{i}] = E_{p} [B_{i}] = 0$ and $E_{p} [η_{i} (p, Z)] = 0.$

Unfolding Definition 5 and applying the finite-design variance formula to the linear combination $\sum_{i \in O_{n}} \frac{1}{n} η_{i} (p, Z)$ gives $σ_{G_{n}, p}^{2} (Y) = n i \in O_{n} \sum j \in O_{n} \sum \frac{1}{n} \cdot \frac{1}{n} Cov_{p} (η_{i} (p, Z), η_{j} (p, Z)) .$ The centering just proved turns each covariance into the corresponding raw pair moment. If $O_{n} \neq = \emptyset$ , then $n > 0$ and the scalar identity $n \cdot (1/ n)^{2} = 1/ n$ applies; if $O_{n} = \emptyset$ , both the displayed right-hand side and the double sum below are empty, hence $0$ , and the two sides again agree under the reciprocal convention. In either case $σ_{G_{n}, p}^{2} (Y) = \frac{1}{n} i \in O_{n} \sum j \in O_{n} \sum E_{p} [η_{i} (p, Z) η_{j} (p, Z)] .$

Next evaluate those pair moments. For any random variables $U, V$ with $E_{p} [U] = θ_{U} \neq = 0$ and $E_{p} [V] = θ_{V} \neq = 0$ , $E_{p} [(U / θ_{U} - 1) (V / θ_{V} - 1)] = E_{p} [U V] / (θ_{U} θ_{V}) - 1$ . Independence gives $E_{p} [T_{i} (Z) T_{j} (Z)] = \prod_{k \in N_{i} (G_{n}) \cup N_{j} (G_{n})} p_{k}$ , while $π_{i}^{1} (p) π_{j}^{1} (p) = (\prod_{k \in N_{i} (G_{n}) \cup N_{j} (G_{n})} p_{k}) (\prod_{k \in S_{ij} (G_{n})} p_{k})$ , so $E_{p} [A_{i} A_{j}] = k \in S_{ij} (G_{n}) \prod p_{k}^{- 1} - 1 = r_{ij}^{1} (G_{n}, p) .$ The same argument with $1 - p_{k}$ in place of $p_{k}$ gives $E_{p} [B_{i} B_{j}] = k \in S_{ij} (G_{n}) \prod (1 - p_{k})^{- 1} - 1 = r_{ij}^{0} (G_{n}, p),$ with the empty-overlap case reducing to $1 - 1 = 0$ , the value selected by the indicators in $r_{ij}^{1}$ and $r_{ij}^{0}$ . For the mixed moments, if $S_{ij} (G_{n}) \neq = \emptyset$ , then $T_{i} (Z) C_{j} (Z) = 0$ identically, since a shared intervention cannot be both treated and untreated, so $E_{p} [A_{i} B_{j}] = - 1$ . If $S_{ij} (G_{n}) = \emptyset$ , then the two exposure events involve disjoint assignment coordinates, and independence gives $E_{p} [T_{i} (Z) C_{j} (Z)] = π_{i}^{1} (p) π_{j}^{0} (p)$ , hence $E_{p} [A_{i} B_{j}] = 0$ . In both cases, and likewise with the roles of the two outcome units exchanged, $E_{p} [A_{i} B_{j}] = E_{p} [B_{i} A_{j}] = - r_{ij}^{10} (G_{n}) .$ Expanding $η_{i} (p, Z) η_{j} (p, Z) = A_{i} A_{j} δ_{i}^{1} δ_{j}^{1} - A_{i} B_{j} δ_{i}^{1} δ_{j}^{0} - B_{i} A_{j} δ_{i}^{0} δ_{j}^{1} + B_{i} B_{j} δ_{i}^{0} δ_{j}^{0}$ and inserting the four displayed moments gives $E_{p} [η_{i} (p, Z) η_{j} (p, Z)] = r_{ij}^{1} (G_{n}, p) δ_{i}^{1} δ_{j}^{1} + r_{ij}^{0} (G_{n}, p) δ_{i}^{0} δ_{j}^{0} + r_{ij}^{10} (G_{n}) (δ_{i}^{1} δ_{j}^{0} + δ_{i}^{0} δ_{j}^{1}) .$

Finally, $S_{ij} (G_{n}) = S_{j i} (G_{n})$ , so $r_{ij}^{10} (G_{n}) = r_{j i}^{10} (G_{n})$ ; relabelling $(i, j) \mapsto (j, i)$ in the double sum gives $i \in O_{n} \sum j \in O_{n} \sum r_{ij}^{10} (G_{n}) δ_{i}^{0} δ_{j}^{1} = i \in O_{n} \sum j \in O_{n} \sum r_{ij}^{10} (G_{n}) δ_{i}^{1} δ_{j}^{0} .$ The two mixed contributions therefore combine into a single doubled term. Substituting the pair-moment identity into the pair expansion of $σ_{G_{n}, p}^{2} (Y)$ yields $σ_{G_{n}, p}^{2} (Y) = \frac{1}{n} i \in O_{n} \sum j \in O_{n} \sum [r_{ij}^{1} (G_{n}, p) (Y_{i}^{1} - μ_{1}) (Y_{j}^{1} - μ_{1}) + r_{ij}^{0} (G_{n}, p) (Y_{i}^{0} - μ_{0}) (Y_{j}^{0} - μ_{0}) + 2 r_{ij}^{10} (G_{n}) (Y_{i}^{1} - μ_{1}) (Y_{j}^{0} - μ_{0})],$ as asserted.

∎

Proof of Theorem 2.

Recall the three covariance loads: for $i, j \in O_{n}$ , $r_{ij}^{1} (G_{n}, p) = 1 {∣ S_{ij} (G_{n}) ∣ > 0} k \in S_{ij} (G_{n}) \prod p_{k}^{- 1} - 1, r_{ij}^{0} (G_{n}, p) = 1 {∣ S_{ij} (G_{n}) ∣ > 0} k \in S_{ij} (G_{n}) \prod (1 - p_{k})^{- 1} - 1,$ $r_{ij}^{10} (G_{n}) = 1 {∣ S_{ij} (G_{n}) ∣ > 0},$ all well defined under $0 < p_{k} < 1$ .

Temporarily write $A_{i} = \frac{T _{i} ( Z )}{π _{i}^{1} ( p )} - 1, B_{i} = \frac{C _{i} ( Z )}{π _{i}^{0} ( p )} - 1.$ Then Definition 4 gives $η_{i} (p, Z) = A_{i} (Y_{i}^{1} - μ_{1}) - B_{i} (Y_{i}^{0} - μ_{0}) .$ Under Assumption 2, the assignment coordinates are independent, and $0 < p_{k} < 1$ makes the exposure probabilities positive. Hence $E_{p} [T_{i} (Z)] = k \in N_{i} (G_{n}) \prod p_{k} = π_{i}^{1} (p), E_{p} [T_{i} (Z) T_{j} (Z)] = k \in N_{i} (G_{n}) \cup N_{j} (G_{n}) \prod p_{k},$ because $T_{i} (Z) T_{j} (Z)$ is the indicator that every intervention in $N_{i} (G_{n}) \cup N_{j} (G_{n})$ is treated. For random variables $U, V$ with $α = E_{p} [U] \neq = 0$ and $β = E_{p} [V] \neq = 0$ , $E_{p} [(\frac{U}{α} - 1) (\frac{V}{β} - 1)] = \frac{E _{p} [ U V ]}{α β} - 1.$ Applying this identity to $T_{i} (Z)$ and $T_{j} (Z)$ gives $E_{p} [A_{i} A_{j}] = \frac{\prod _{k \in N_{i} (G_{n}) \cup N_{j} (G_{n})} p _{k}}{π _{i}^{1} ( p ) π _{j}^{1} ( p )} - 1.$ The last ratio is matched to $r_{ij}^{1} (G_{n}, p)$ by the two overlap branches. If $S_{ij} (G_{n}) \neq = \emptyset$ , then the nonzero factors satisfy $\frac{\prod _{k \in N_{i} (G_{n}) \cup N_{j} (G_{n})} p _{k}}{π _{i}^{1} ( p ) π _{j}^{1} ( p )} = k \in S_{ij} (G_{n}) \prod p_{k}^{- 1},$ so $E_{p} [A_{i} A_{j}] = \prod_{k \in S_{ij} (G_{n})} p_{k}^{- 1} - 1 = r_{ij}^{1} (G_{n}, p)$ . If $S_{ij} (G_{n}) = \emptyset$ , then $N_{i} (G_{n})$ and $N_{j} (G_{n})$ are disjoint, the union product factors as $π_{i}^{1} (p) π_{j}^{1} (p)$ , and $E_{p} [A_{i} A_{j}] = 0 = r_{ij}^{1} (G_{n}, p)$ . Therefore $E_{p} [A_{i} A_{j}] = r_{ij}^{1} (G_{n}, p) .$ The control-control calculation first gives $E_{p} [B_{i} B_{j}] = \frac{\prod _{k \in N_{i} (G_{n}) \cup N_{j} (G_{n})} ( 1 - p _{k} )}{π _{i}^{0} ( p ) π _{j}^{0} ( p )} - 1.$ It has the same two branches with $1 - p_{k}$ in place of $p_{k}$ : on the nonempty-overlap branch the ratio equals $\prod_{k \in S_{ij} (G_{n})} (1 - p_{k})^{- 1}$ , while on the empty-overlap branch the disjoint union product factors and the centered ratio is zero. Thus $E_{p} [B_{i} B_{j}] = r_{ij}^{0} (G_{n}, p) .$ For the mixed moment, if $S_{ij} (G_{n}) \neq = \emptyset$ , then a shared intervention is required to be both treated and untreated in $T_{i} (Z) C_{j} (Z)$ , so $T_{i} (Z) C_{j} (Z) = 0$ for every assignment and $E_{p} [A_{i} B_{j}] = - 1$ . If $S_{ij} (G_{n}) = \emptyset$ , the two exposure events use disjoint assignment coordinates, so $E_{p} [T_{i} (Z) C_{j} (Z)] = π_{i}^{1} (p) π_{j}^{0} (p)$ and $E_{p} [A_{i} B_{j}] = 0$ . Thus $E_{p} [A_{i} B_{j}] = - r_{ij}^{10} (G_{n}) .$ The same argument with $i$ and $j$ exchanged, using $S_{ij} (G_{n}) = S_{j i} (G_{n})$ , gives $E_{p} [B_{i} A_{j}] = - r_{ij}^{10} (G_{n}) .$ Expanding the product of the two linearization summands, $η_{i} (p, Z) η_{j} (p, Z) = A_{i} A_{j} (Y_{i}^{1} - μ_{1}) (Y_{j}^{1} - μ_{1}) - A_{i} B_{j} (Y_{i}^{1} - μ_{1}) (Y_{j}^{0} - μ_{0}) - B_{i} A_{j} (Y_{i}^{0} - μ_{0}) (Y_{j}^{1} - μ_{1}) + B_{i} B_{j} (Y_{i}^{0} - μ_{0}) (Y_{j}^{0} - μ_{0}),$ and inserting the four moment identities yields $E_{p} [η_{i} (p, Z) η_{j} (p, Z)] = r_{ij}^{1} (G_{n}, p) (Y_{i}^{1} - μ_{1}) (Y_{j}^{1} - μ_{1}) + r_{ij}^{0} (G_{n}, p) (Y_{i}^{0} - μ_{0}) (Y_{j}^{0} - μ_{0}) + r_{ij}^{10} (G_{n}) {(Y_{i}^{1} - μ_{1}) (Y_{j}^{0} - μ_{0}) + (Y_{i}^{0} - μ_{0}) (Y_{j}^{1} - μ_{1})} .$
The one-score centered-ratio identities give $E_{p} [A_{i}] = E_{p} [B_{i}] = 0$ , hence $E_{p} [η_{i} (p, Z)] = 0$ for every $i$ . Starting from Definition 5, the finite-design variance of the linear combination $n^{- 1} \sum_{i} η_{i} (p, Z)$ expands as a double sum of covariances, and the zero means identify those covariances with joint moments. The empty-outcome branch is evaluated separately, where both finite sums and the scaled variance term are zero; on the nonempty branch, this is the ordinary pair average. Thus $σ_{G_{n}, p}^{2} (Y) = \frac{1}{n} i \in O_{n} \sum j \in O_{n} \sum E_{p} [η_{i} (p, Z) η_{j} (p, Z)] .$ Substituting the preceding pair-moment identity and combining the two mixed double sums by the symmetry $S_{ij} (G_{n}) = S_{j i} (G_{n})$ gives $σ_{G_{n}, p}^{2} (Y) = \frac{1}{n} i \in O_{n} \sum j \in O_{n} \sum {r_{ij}^{1} (G_{n}, p) (Y_{i}^{1} - μ_{1}) (Y_{j}^{1} - μ_{1}) + r_{ij}^{0} (G_{n}, p) (Y_{i}^{0} - μ_{0}) (Y_{j}^{0} - μ_{0}) + 2 r_{ij}^{10} (G_{n}) (Y_{i}^{1} - μ_{1}) (Y_{j}^{0} - μ_{0})} .$
By Assumption 5, $∣ Y_{i}^{1} ∣ \leq 1$ and $∣ Y_{i}^{0} ∣ \leq 1$ for every $i$ . Applying the triangle inequality to the finite-population means gives $∣ μ_{1} ∣ \leq 1, ∣ μ_{0} ∣ \leq 1,$ with the empty-population case evaluating both means as $0$ . Therefore, for every $i \in O_{n}$ , $∣ Y_{i}^{1} - μ_{1} ∣ \leq 2, ∣ Y_{i}^{0} - μ_{0} ∣ \leq 2.$ The overlap loads are nonnegative under $0 < p_{k} < 1$ . Indeed, when $S_{ij} (G_{n}) = \emptyset$ all three loads are $0$ ; when $S_{ij} (G_{n}) \neq = \emptyset$ , the factors $p_{k}^{- 1}$ and $(1 - p_{k})^{- 1}$ are at least $1$ , so the corresponding products minus $1$ are nonnegative, and $r_{ij}^{10} (G_{n}) = 1$ . Thus $r_{ij}^{1} (G_{n}, p) \geq 0, r_{ij}^{0} (G_{n}, p) \geq 0, r_{ij}^{10} (G_{n}) \geq 0.$
For a nonnegative weight $r$ and real numbers $u, v$ with $∣ u ∣ \leq 2$ and $∣ v ∣ \leq 2$ , $r uv \leq r ∣ u ∣∣ v ∣ \leq 4 r .$ Applying this bound to the treated, control, and mixed terms using the bounds and nonnegativity just established gives, for every ordered pair $(i, j)$ , $r_{ij}^{1} (G_{n}, p) (Y_{i}^{1} - μ_{1}) (Y_{j}^{1} - μ_{1}) + r_{ij}^{0} (G_{n}, p) (Y_{i}^{0} - μ_{0}) (Y_{j}^{0} - μ_{0}) + 2 r_{ij}^{10} (G_{n}) (Y_{i}^{1} - μ_{1}) (Y_{j}^{0} - μ_{0}) \leq 4 {r_{ij}^{1} (G_{n}, p) + r_{ij}^{0} (G_{n}, p) + 2 r_{ij}^{10} (G_{n})} .$
Summing the pairwise inequality over $i, j \in O_{n}$ and multiplying by the nonnegative inverse $n^{- 1}$ gives $σ_{G_{n}, p}^{2} (Y) \leq \frac{1}{n} i \in O_{n} \sum j \in O_{n} \sum 4 {r_{ij}^{1} (G_{n}, p) + r_{ij}^{0} (G_{n}, p) + 2 r_{ij}^{10} (G_{n})} = V_{env} (G_{n}, p),$ by Definition 6.

∎

Proof of Theorem 3.

Throughout write $m_{n} = ∣ I_{n} ∣$ and $S_{ij} = S_{ij} (G_{n})$ , and interpret the factors $n^{- 1}$ in Definitions 6 and 8 as $(∣ O_{n} ∣)^{- 1}$ , with the total reciprocal convention $0^{- 1} = 0$ . Thus when $O_{n} = \emptyset$ the corresponding finite sums and scaled gradients are zero, and otherwise the notation is ordinary division by the outcome count. Recall that the three covariance loads entering Definition 6 are $r_{ij}^{1} (G_{n}, p) = 1 {∣ S_{ij} ∣ > 0} k \in S_{ij} \prod p_{k}^{- 1} - 1, r_{ij}^{0} (G_{n}, p) = 1 {∣ S_{ij} ∣ > 0} k \in S_{ij} \prod (1 - p_{k})^{- 1} - 1,$ $r_{ij}^{10} (G_{n}) = 1 {∣ S_{ij} ∣ > 0} .$ Note that every $p \in P_{n, B_{n}, ϵ}$ satisfies $0 < ϵ \leq p_{k} \leq 1 - ϵ < 1$ , so all coordinate reciprocals in these loads are defined on the feasible class.

First suppose that $I_{n}$ is nonempty and define the constant design $p_{k} = \frac{B _{n}}{m _{n}} (k \in I_{n}) .$ Since $m_{n} > 0$ , the budget bounds $m_{n} ϵ \leq B_{n} \leq m_{n} (1 - ϵ)$ give $ϵ \leq \frac{B _{n}}{m _{n}} \leq 1 - ϵ,$ and $0 < ϵ < 1/2$ makes this interval a subset of $[0, 1]$ . Thus $p$ satisfies the probability and positivity requirements, and its budget is $\sum_{k \in I_{n}} p_{k} = m_{n} (B_{n} / m_{n}) = B_{n}$ . If instead $I_{n}$ is empty, the two budget inequalities read $0 \leq B_{n} \leq 0$ and force $B_{n} = 0$ , so the unique empty design is feasible. Hence $P_{n, B_{n}, ϵ} \neq = \emptyset$ .
The feasible class is closed. Indeed, under $0 < ϵ < 1/2$ , Definition 1 describes it as the intersection of the coordinatewise closed probability constraints $0 \leq p_{k} \leq 1$ , the coordinatewise closed bounds $ϵ \leq p_{k} \leq 1 - ϵ$ , and the closed affine hyperplane $\sum_{k \in I_{n}} p_{k} = B_{n}$ ; each of these is the preimage of a closed set under a continuous coordinate map or under the continuous finite sum. It is contained in the finite product $[0, 1]^{I_{n}}$ , which is compact; a closed subset of a compact set is compact, so $P_{n, B_{n}, ϵ}$ is compact.
Let $p, q \in P_{n, B_{n}, ϵ}$ , and let $θ, θ^{'} \geq 0$ with $θ + θ^{'} = 1$ . Coordinatewise, $ϵ = θ ϵ + θ^{'} ϵ \leq θ p_{k} + θ^{'} q_{k} \leq θ (1 - ϵ) + θ^{'} (1 - ϵ) = 1 - ϵ,$ and by the same convex combination $0 \leq θ p_{k} + θ^{'} q_{k} \leq 1$ . Its budget is $k \in I_{n} \sum (θ p_{k} + θ^{'} q_{k}) = θ k \in I_{n} \sum p_{k} + θ^{'} k \in I_{n} \sum q_{k} = θ B_{n} + θ^{'} B_{n} = B_{n} .$ Thus $θ p + θ^{'} q \in P_{n, B_{n}, ϵ}$ , proving convexity of the feasible class.
The envelope is continuous on the feasible class. Fix $i, j \in O_{n}$ . If $S_{ij} \neq = \emptyset$ , then the maps $p \mapsto \prod_{k \in S_{ij}} p_{k}$ and $p \mapsto \prod_{k \in S_{ij}} (1 - p_{k})$ are continuous, and the bounds $ϵ \leq p_{k} \leq 1 - ϵ$ with $0 < ϵ < 1/2$ keep both products nonzero on $P_{n, B_{n}, ϵ}$ ; reciprocals of nonvanishing continuous functions are continuous, so $r_{ij}^{1} (G_{n}, \cdot)$ and $r_{ij}^{0} (G_{n}, \cdot)$ are continuous there. If $S_{ij} = \emptyset$ , both are identically zero. Adding the constant $2 r_{ij}^{10} (G_{n})$ , summing over the finitely many pairs $(i, j)$ , and multiplying by the fixed scalar $4 (∣ O_{n} ∣)^{- 1}$ shows that $V_{env} (G_{n}, \cdot)$ is continuous on $P_{n, B_{n}, ϵ}$ .
For each nonempty $S_{ij}$ , the maps $p ⟼ k \in S_{ij} \prod p_{k}^{- 1}, p ⟼ k \in S_{ij} \prod (1 - p_{k})^{- 1}$ are convex on $P_{n, B_{n}, ϵ}$ . Indeed, on that class every $p_{k}$ and every $1 - p_{k}$ is strictly positive, so $k \in S_{ij} \prod p_{k}^{- 1} = exp k \in S_{ij} \sum - lo g p_{k}, k \in S_{ij} \prod (1 - p_{k})^{- 1} = exp k \in S_{ij} \sum - lo g (1 - p_{k}) .$ Each $p \mapsto - lo g p_{k}$ is convex on the feasible class as a convex one-dimensional function composed with a linear coordinate map; likewise $p \mapsto - lo g (1 - p_{k})$ , with the affine coordinate map $p \mapsto 1 - p_{k}$ . Finite sums of convex functions are convex, and $exp$ is convex and nondecreasing, so composing preserves convexity. Subtracting the constant $1$ gives convexity of $r_{ij}^{1} (G_{n}, \cdot)$ and $r_{ij}^{0} (G_{n}, \cdot)$ ; when $S_{ij} = \emptyset$ both are constant, hence convex. Consequently each summand $r_{ij}^{1} (G_{n}, p) + r_{ij}^{0} (G_{n}, p) + 2 r_{ij}^{10} (G_{n})$ is convex on the feasible class. Finite summation preserves convexity, and so does multiplication by the nonnegative scalar $4 (∣ O_{n} ∣)^{- 1}$ . Thus $V_{env} (G_{n}, \cdot)$ is convex on $P_{n, B_{n}, ϵ}$ .
The preceding nonemptiness and compactness conclusions, together with the continuity of $V_{env} (G_{n}, \cdot)$ on $P_{n, B_{n}, ϵ}$ , put the envelope in the finite-dimensional extreme-value theorem. Hence it attains its minimum on $P_{n, B_{n}, ϵ}$ . Denote one minimizer by $p_{n}^{*} (G_{n})$ . Then $V_{env} (G_{n}, p_{n}^{*} (G_{n})) \leq V_{env} (G_{n}, q)$ for every $q \in P_{n, B_{n}, ϵ}$ .
It remains to establish the multiplier statement, and for that we first identify the coordinate derivatives of the envelope. Let $χ : R \to R$ be the standard smooth transition function with $χ (t) = 0$ for $t \leq 0$ and $χ (t) = 1$ for $t \geq 1$ . Define the floored reciprocal $R_{ϵ} (x) = ⎩ ⎨ ⎧ χ (\frac{x - ϵ /4}{ϵ /4}) x^{- 1}, 0, x \neq = 0, x = 0.$ Because $χ ((x - ϵ /4) / (ϵ /4))$ is identically zero on a neighborhood of the singular point $x = 0$ , this function is continuously differentiable on all of $R$ . If $x \geq ϵ /2$ , then $(x - ϵ /4) / (ϵ /4) \geq 1$ , so $R_{ϵ} (x) = x^{- 1}$ . Replace every reciprocal factor in the two overlap kernels by this $R_{ϵ}$ , obtaining $r_{ij}^{1} (p) = 1 {∣ S_{ij} ∣ > 0} k \in S_{ij} \prod R_{ϵ} (p_{k}) - 1, r_{ij}^{0} (p) = 1 {∣ S_{ij} ∣ > 0} k \in S_{ij} \prod R_{ϵ} (1 - p_{k}) - 1,$ $V (p) = 4 (∣ O_{n} ∣)^{- 1} i, j \in O_{n} \sum {r_{ij}^{1} (p) + r_{ij}^{0} (p) + 2 r_{ij}^{10} (G_{n})} .$ Then $V$ is continuously differentiable on all of $R^{I_{n}}$ , and $V (p) = V_{env} (G_{n}, p) whenever p_{k} \geq ϵ /2 and 1 - p_{k} \geq ϵ /2 for every k \in I_{n} .$ Transporting $V /4$ along a bijection between $I_{n}$ and ${1, \dots, m_{n}}$ to Euclidean coordinates gives a differentiable objective on $R^{m_{n}}$ .

For a feasible $p$ , a coordinate $k$ , and a shared neighborhood $S_{ij}$ , differentiation along the $k$ -th coordinate line gives $\frac{d}{d t}_{t = 0} ℓ \in S_{ij} \prod (p_{ℓ} + 1 {ℓ = k} t)^{- 1} = {- (\prod_{ℓ \in S_{ij}} p_{ℓ}^{- 1}) p_{k}^{- 1}, 0, k \in S_{ij}, k \in / S_{ij},$ and $\frac{d}{d t}_{t = 0} ℓ \in S_{ij} \prod (1 - p_{ℓ} - 1 {ℓ = k} t)^{- 1} = {(\prod_{ℓ \in S_{ij}} (1 - p_{ℓ})^{- 1}) (1 - p_{k})^{- 1}, 0, k \in S_{ij}, k \in / S_{ij} .$ When $k \in / S_{ij}$ the product does not depend on $t$ , and when $k \in S_{ij}$ only the factor indexed by $k$ varies, contributing $\frac{d}{d t} (p_{k} + t)^{- 1} ∣_{t = 0} = - p_{k}^{- 2}$ and $\frac{d}{d t} (1 - p_{k} - t)^{- 1} ∣_{t = 0} = (1 - p_{k})^{- 2}$ , respectively. Subtracting the constant $1$ leaves these derivatives unchanged, so the same formulas hold for the treated and control overlap loads, including the case $S_{ij} = \emptyset$ , where both derivatives vanish. Summing over $(i, j)$ and multiplying by $(∣ O_{n} ∣)^{- 1}$ gives exactly Definition 8: $\frac{d}{d t}_{t = 0} \frac{V _{env} ( G _{n} , p + t e _{k} )}{4} = g_{k} (G_{n}, p) .$ Since $ϵ \leq p_{k} \leq 1 - ϵ$ , every $∣ t ∣ < ϵ /2$ keeps $p + t e_{k}$ in the region where $V$ agrees with $V_{env} (G_{n}, \cdot)$ . Therefore the $k$ -th Euclidean partial derivative of the transported objective at any feasible $p$ is $g_{k} (G_{n}, p)$ .
Fix any minimizer $p_{n}^{*} (G_{n})$ . In Euclidean coordinates, impose the equality constraint $h (x) = u = 1 \sum m_{n} x_{u} - B_{n} = 0$ and the $2 m_{n}$ inequality constraints $c_{u}^{-} (x) = x_{u} - ϵ \geq 0, c_{u}^{+} (x) = 1 - ϵ - x_{u} \geq 0 (u = 1, \dots, m_{n}) .$ The correspondence between the Euclidean points satisfying these constraints and $P_{n, B_{n}, ϵ}$ is exact. The displayed agreement of $V$ with $V_{env} (G_{n}, \cdot)$ on the feasible box shows that the transported smooth objective agrees on that set with $V_{env} (G_{n}, \cdot) /4$ ; hence the Euclidean image $x^{*}$ of $p_{n}^{*} (G_{n})$ is a local minimum of the transported objective subject to those constraints. The objective is differentiable, the Euclidean domain is all of $R^{m_{n}}$ , and $h, c_{u}^{-}, c_{u}^{+}$ are affine, so the affine linear constraint qualification holds at $x^{*}$ .

The finite-dimensional first-order necessary condition under this affine constraint qualification states: if $x^{*}$ is a local minimum of a differentiable $f$ subject to $h (x) = 0$ and $c_{j} (x) \geq 0$ with all constraints affine, then there exist $λ_{n} \in R$ and $ν_{j} \geq 0$ with $\nabla f (x^{*}) - λ_{n} \nabla h (x^{*}) - j \sum ν_{j} \nabla c_{j} (x^{*}) = 0 and ν_{j} c_{j} (x^{*}) = 0 for every j .$ Write $ν_{k, n}^{-}$ for the multiplier of $c_{u}^{-}$ and $ν_{k, n}^{+}$ for the multiplier of $c_{u}^{+}$ at the coordinate $u$ corresponding to $k \in I_{n}$ . Since $\nabla h$ is the all-ones vector, $\nabla c_{u}^{-} = e_{u}$ and $\nabla c_{u}^{+} = - e_{u}$ , the $k$ -th coordinate of the stationarity condition reads, using the coordinate-gradient identity just established, whose right-hand side is the score in Definition 8, $g_{k} (G_{n}, p_{n}^{*} (G_{n})) - λ_{n} - ν_{k, n}^{-} + ν_{k, n}^{+} = 0,$ or equivalently $g_{k} (G_{n}, p_{n}^{*} (G_{n})) = λ_{n} - ν_{k, n}^{+} + ν_{k, n}^{-} .$ Dual feasibility gives $ν_{k, n}^{+} \geq 0$ and $ν_{k, n}^{-} \geq 0$ . Complementary slackness for the upper and lower constraints gives $ν_{k, n}^{+} c_{u}^{+} (x^{*}) = 0$ and $ν_{k, n}^{-} c_{u}^{-} (x^{*}) = 0$ , equivalently $ν_{k, n}^{+} ((p_{n}^{*} (G_{n}))_{k} - (1 - ϵ)) = 0, ν_{k, n}^{-} (ϵ - (p_{n}^{*} (G_{n}))_{k}) = 0.$ This holds for every $k \in I_{n}$ , as required.

∎

Proof of Theorem 4.

Write $p_{n} = p_{n}^{*} (G_{n})$ . The proof uses the feasibility, positivity, assignment, interference, graph-regularity, and variance hypotheses attached to this sequence. Throughout, put $K (ϵ, \overset{ˉ}{d}) = ϵ^{- 1} max {1, ϵ^{- (\overset{ˉ}{d} - 1)}} .$

Outcome indexing gives $∣ O_{n} ∣ = n$ eventually. Hence $∣ O_{n} ∣ \to \infty$ , and, on this tail, $∣ O_{n} ∣ = n$ and $∣ O_{n} ∣^{- 1/2} = n^{- 1/2}$ . All limit statements below may therefore be proved after discarding the finitely many earlier stages.
Uniform positivity gives $ϵ_{0} > 0$ with $ϵ_{0} \leq ϵ_{n}$ eventually. Since each $ϵ_{n} \in (0, 1/2)$ , the denominator-kernel monotonicity bound gives $K (ϵ_{n}, \overset{ˉ}{d}) \leq K (ϵ_{0}, \overset{ˉ}{d}) eventually.$ Together with $∣ O_{n} ∣ \to \infty$ , this fixed upper bound implies $\frac{K ( ϵ _{n} , d ˉ )}{∣ O _{n} ∣} ⟶ 0.$
Define the two centered numerators and the two centered denominator ratios, $U_{1} (Z) = i \in O_{n} \sum \frac{T _{i} ( Z )}{π _{i}^{1} ( p _{n} )} (Y_{i}^{1} - μ_{1}), U_{0} (Z) = i \in O_{n} \sum \frac{C _{i} ( Z )}{π _{i}^{0} ( p _{n} )} (Y_{i}^{0} - μ_{0}),$ $R_{1 n} = ∣ O_{n} ∣^{- 1/2} U_{1} (Z), R_{0 n} = ∣ O_{n} ∣^{- 1/2} U_{0} (Z),$ $Q_{1 n} = ∣ O_{n} ∣^{- 1} D_{1} (p_{n}, Z) - 1, Q_{0 n} = ∣ O_{n} ∣^{- 1} D_{0} (p_{n}, Z) - 1.$

The scaled numerators are bounded in probability. Indeed, $E_{D_{n}} [T_{i} (Z) / π_{i}^{1} (p_{n})] = 1$ and $μ_{1} = ∣ O_{n} ∣^{- 1} \sum_{i} Y_{i}^{1}$ give $E_{D_{n}} [U_{1} (Z)] = 0$ , hence $E_{D_{n}} [R_{1 n}] = 0$ ; and expanding the variance into pair covariances, using Assumption 5 and the row bound of Assumption 7 together with the kernel bound supplied by Assumption 6 and the eventual floor $ϵ_{0} \leq ϵ_{n}$ , one gets eventually $Var_{D_{n}} (R_{1 n}) \leq 4 \overset{ˉ}{D} K (ϵ_{0}, \overset{ˉ}{d}), Var_{D_{n}} (R_{0 n}) \leq 4 \overset{ˉ}{D} K (ϵ_{0}, \overset{ˉ}{d}) .$ A sequence with mean zero and uniformly bounded variance is bounded in probability, by Chebyshev’s inequality.

The centered denominator ratios vanish in probability. The treated denominator has mean $∣ O_{n} ∣$ , so $E_{D_{n}} [Q_{1 n}] = 0$ . The same covariance expansion gives $Var_{D_{n}} (D_{1} (p_{n}, Z)) \leq ∣ O_{n} ∣ \overset{ˉ}{D} K (ϵ_{n}, \overset{ˉ}{d}),$ and therefore $Var_{D_{n}} (Q_{1 n}) \leq \frac{D ˉ K ( ϵ _{n} , d ˉ )}{∣ O _{n} ∣} ⟶ 0$ by the denominator-kernel rate displayed above. Chebyshev’s inequality then yields $Q_{1 n} P r 0, Q_{0 n} P r 0.$

A product of a sequence bounded in probability with one vanishing in probability vanishes in probability, so $2∣ R_{1 n} ∣∣ Q_{1 n} ∣ + 2∣ R_{0 n} ∣∣ Q_{0 n} ∣ P r 0.$

For all sufficiently large $n$ , split according as $D_{1} (p_{n}, Z) \geq \frac{∣ O _{n} ∣}{2} and D_{0} (p_{n}, Z) \geq \frac{∣ O _{n} ∣}{2} .$ When both inequalities hold, both denominators are positive, the Hájek estimator in Definition 3 takes its ratio form in both arms, and expanding each ratio around its denominator mean gives the capped remainder bound $∣ O_{n} ∣ {τ_{H} (p_{n}) - τ_{n}} - ∣ O_{n} ∣^{- 1/2} i \in O_{n} \sum η_{i} (p_{n}, Z) \leq 2∣ R_{1 n} ∣∣ Q_{1 n} ∣ + 2∣ R_{0 n} ∣∣ Q_{0 n} ∣.$ Here Assumption 1 identifies the observed outcome $Y_{i}^{obs}$ with $Y_{i}^{1}$ on ${T_{i} (Z) = 1}$ and with $Y_{i}^{0}$ on ${C_{i} (Z) = 1}$ , so that the two arm numerators are $U_{1} (Z) + μ_{1} D_{1} (p_{n}, Z)$ and $U_{0} (Z) + μ_{0} D_{0} (p_{n}, Z)$ , and the cap $D_{a} (p_{n}, Z) \geq ∣ O_{n} ∣/2$ bounds the factor $∣ O_{n} ∣/ D_{a} (p_{n}, Z)$ by $2$ .

If instead $D_{1} (p_{n}, Z) < ∣ O_{n} ∣/2$ , then $∣ O_{n} ∣^{- 1} D_{1} (p_{n}, Z) < 1/2$ , so $Q_{1 n} < - 1/2$ and $∣ Q_{1 n} ∣ > 1/2$ ; likewise for the control arm. Thus, for every $δ > 0$ , the probability that the absolute remainder exceeds $δ$ is bounded by the probability of this denominator-ratio bad event plus $D_{n} Pr (2∣ R_{1 n} ∣∣ Q_{1 n} ∣ + 2∣ R_{0 n} ∣∣ Q_{0 n} ∣ \geq δ),$ and both terms converge to zero.
Consequently, for every $δ > 0$ the probability that the absolute remainder is at least $δ$ tends to zero, that is $∣ O_{n} ∣ {τ_{H} (p_{n}) - τ_{n}} - ∣ O_{n} ∣^{- 1/2} i \in O_{n} \sum η_{i} (p_{n}, Z) P r 0.$ Replacing $∣ O_{n} ∣$ by $n$ on the outcome-indexing tail gives the first conclusion.
Set $X_{n, i} = η_{i} (p_{n}, Z)$ for $i \in O_{n}$ , and declare $i$ and $j$ adjacent when $i = j$ or $S_{ij} (G_{n}) \neq = \emptyset$ . This is a dependency graph for ${X_{n, i}}$ : the summand $η_{i} (p_{n}, Z)$ of Definition 4 is assembled from $T_{i} (Z)$ and $C_{i} (Z)$ , together with $π_{i}^{1} (p_{n}), π_{i}^{0} (p_{n}), Y_{i}^{1}, Y_{i}^{0}, μ_{1}, μ_{0}$ , so it depends on $Z$ only through the coordinates in $N_{i} (G_{n})$ . If no outcome in $A \subseteq O_{n}$ is adjacent to any outcome in $B \subseteq O_{n}$ , then $⋃_{i \in A} N_{i} (G_{n})$ and $⋃_{j \in B} N_{j} (G_{n})$ are disjoint, and Assumption 2 makes the two assignment-coordinate blocks independent. The closed neighborhood at $i$ is contained in ${i} \cup {j : S_{ij} (G_{n}) \neq = \emptyset}$ , so Assumption 7 gives cardinality at most $⌈ \overset{ˉ}{D} ⌉ + 1$ .

These summands have mean zero, because $E_{D_{n}} [T_{i} (Z) / π_{i}^{1} (p_{n})] = E_{D_{n}} [C_{i} (Z) / π_{i}^{0} (p_{n})] = 1$ .

Moreover Assumption 5 gives $∣ Y_{i}^{1} - μ_{1} ∣ \leq 2$ and $∣ Y_{i}^{0} - μ_{0} ∣ \leq 2$ , while Definition 1, Assumption 6, and the eventual floor $ϵ_{0} \leq ϵ_{n}$ give $(π_{i}^{1} (p_{n}))^{- 1} \leq K (ϵ_{0}, \overset{ˉ}{d}) + 1, (π_{i}^{0} (p_{n}))^{- 1} \leq K (ϵ_{0}, \overset{ˉ}{d}) + 1.$ Thus $∣ T_{i} (Z) / π_{i}^{1} (p_{n}) - 1∣ \leq K (ϵ_{0}, \overset{ˉ}{d}) + 2$ and likewise for the control arm, and the eventual uniform bound $∣ X_{n, i} ∣ \leq 4 {K (ϵ_{0}, \overset{ˉ}{d}) + 2}$ holds for every $i \in O_{n}$ and every assignment.

Finally, with $v_{n} = E_{D_{n}} (i \in O_{n} \sum X_{n, i})^{2},$ expanding the square into pair moments and comparing with Definition 5 gives $v_{n} = i \in O_{n} \sum j \in O_{n} \sum E_{D_{n}} [η_{i} (p_{n}, Z) η_{j} (p_{n}, Z)] = ∣ O_{n} ∣ σ_{G_{n}, p_{n}}^{2} (Y) .$

Assumption 8 supplies $c > 0$ with $σ_{G_{n}, p_{n}}^{2} (Y) \geq c$ eventually. Hence $v_{n} \geq c ∣ O_{n} ∣$ eventually, and on the outcome-indexing tail this is the variance-growth condition $v_{n} \geq c n$ . Applying Lemma 1 with $D = ⌈ \overset{ˉ}{D} ⌉ + 1$ , $M = 4 {K (ϵ_{0}, \overset{ˉ}{d}) + 2}$ , and this $c$ yields, for every $s \in R$ , $D_{n} Pr (\frac{\sum _{i \in O_{n}} η _{i} ( p _{n} , Z )}{v _{n}} \leq s) ⟶ Pr {N (0, 1) \leq s} .$ Since $v_{n} = ∣ O_{n} ∣ σ_{G_{n}, p_{n}}^{2} (Y)$ , the statistic inside is $(∣ O_{n} ∣^{- 1/2} \sum_{i} η_{i} (p_{n}, Z)) / σ_{G_{n}, p_{n}}^{2} (Y)$ , so $D_{n} Pr \frac{∣ O _{n} ∣ ^{- 1/2} \sum _{i \in O_{n}} η _{i} ( p _{n} , Z )}{σ _{G_{n}, p_{n}}^{2} ( Y )} \leq s ⟶ Pr {N (0, 1) \leq s} .$
The difference between the studentized Hájek statistic and the studentized linear-score statistic is $\frac{∣ O _{n} ∣ { τ _{H} ( p _{n} ) - τ _{n} } - ∣ O _{n} ∣ ^{- 1/2} \sum _{i \in O_{n}} η _{i} ( p _{n} , Z )}{σ _{G_{n}, p_{n}}^{2} ( Y )} .$ By Assumption 8, eventually $σ_{G_{n}, p_{n}}^{2} (Y) \geq c$ . Hence, for every $δ > 0$ , the probability that the absolute value of the displayed difference is at least $δ$ is eventually bounded above by $D_{n} Pr (∣ O_{n} ∣ {τ_{H} (p_{n}) - τ_{n}} - ∣ O_{n} ∣^{- 1/2} i \in O_{n} \sum η_{i} (p_{n}, Z) \geq δ c),$ which tends to zero by the linearization established above. The converging-together principle in CDF form then transfers the standard-normal CDF limit from the studentized linear-score statistic to the studentized Hájek statistic: for each $x$ , sandwich the event for the Hájek statistic between the corresponding linear-score events at $x - δ$ and $x + δ$ , up to the small-difference event, and let $δ ↓ 0$ using continuity of the standard-normal CDF. Therefore, for every $s \in R$ , $D_{n} Pr \frac{∣ O _{n} ∣ { τ _{H} ( p _{n} ) - τ _{n} }}{σ _{G_{n}, p_{n}}^{2} ( Y )} \leq s ⟶ Pr {N (0, 1) \leq s} .$ Replacing $∣ O_{n} ∣$ by $n$ on the outcome-indexing tail proves the second conclusion.

∎

Proof of Theorem 5.

The eventual identity $∣ O_{n} ∣ = n$ implies that $∣ O_{n} ∣ \to \infty$ ; in particular $∣ O_{n} ∣ > 0$ on an eventual tail.

Fix $n$ . The admissibility condition $ϵ_{n} \in (0, 1/2)$ and the feasibility floor give $0 < ϵ_{n} \leq p_{n, k} \leq 1 - ϵ_{n} < 1 (k \in I_{n}) .$ This display supplies the assignment-probability hypothesis $0 < p_{n, k} < 1$ in Theorem 2. Together with Assumption 2 and Assumption 5, the second conclusion of Theorem 2 gives $σ_{G_{n}, p_{n}}^{2} (Y) \leq V_{env} (G_{n}, p_{n}) .$ By Definition 9, $V_{cons} (G_{n}, p_{n}) = V_{env} (G_{n}, p_{n})$ , and hence $σ_{G_{n}, p_{n}}^{2} (Y) \leq V_{cons} (G_{n}, p_{n}) .$ Since $n$ was arbitrary, this proves the variance-domination assertion for every $n$ .
By Assumption 8 there are $c > 0$ and an eventual tail on which $c \leq σ_{G_{n}, p_{n}}^{2} (Y) .$ Hence $σ_{G_{n}, p_{n}}^{2} (Y) > 0$ eventually. The eventual identity $∣ O_{n} ∣ = n$ also gives the positive normalization $∣ O_{n} ∣ > 0$ eventually. Under the assumptions listed in Theorem 4 – outcome indexing, assignment and interference, bounded outcomes, bounded degree, bounded overlap, feasibility, optimality $p_{n} = p_{n}^{*} (G_{n})$ , uniform positivity, and variance nondegeneracy – Theorem 4 gives, for every $s \in R$ , $p_{n} Pr \frac{n [ τ _{H} ( p _{n} ) - τ _{n} ]}{σ _{G_{n}, p_{n}}^{2} ( Y )} \leq s ⟶ Φ (s) .$
Write $W_{n} = \frac{n [ τ _{H} ( p _{n} ) - τ _{n} ]}{σ _{G_{n}, p_{n}}^{2} ( Y )}, z = z_{1 - α_{cov} /2} .$ Since $z \geq 0$ , the event ${W_{n} \leq - z}$ is contained in ${W_{n} \leq z}$ , and the finite-design probability split gives $p_{n} Pr (- z < W_{n} \leq z) = p_{n} Pr (W_{n} \leq z) - p_{n} Pr (W_{n} \leq - z) .$ The convergence supplied by Theorem 4 at $s = z$ and $s = - z$ , together with $Φ (- z) = 1 - Φ (z)$ and the calibration $Φ (z) = 1 - α_{cov} /2$ , yields $p_{n} Pr (W_{n} \leq z) - p_{n} Pr (W_{n} \leq - z) ⟶ Φ (z) - Φ (- z) = 1 - α_{cov} .$ On the eventual tail where $∣ O_{n} ∣$ , $n$ , and $σ_{G_{n}, p_{n}}^{2} (Y)$ are positive, the strict interval event is contained in the Wald coverage event. Indeed, if $- z < W_{n} \leq z$ , then $∣ W_{n} ∣ \leq z$ , so $n ∣ τ_{H} (p_{n}) - τ_{n} ∣ \leq z σ_{G_{n}, p_{n}}^{2} (Y) .$ Dividing by $n > 0$ and using the variance-domination bound $σ_{G_{n}, p_{n}}^{2} (Y) \leq V_{cons} (G_{n}, p_{n})$ , monotonicity of the square root, and $z \geq 0$ , gives $∣ τ_{n} - τ_{H} (p_{n}) ∣ \leq z \frac{σ _{G_{n}, p_{n}}^{2} ( Y )}{n} \leq z \frac{V _{cons} ( G _{n} , p _{n} )}{n} .$ Consequently, on that tail, $p_{n} Pr ∣ τ_{n} - τ_{H} (p_{n}) ∣ \leq z \frac{V _{cons} ( G _{n} , p _{n} )}{n} \geq p_{n} Pr (W_{n} \leq z) - p_{n} Pr (W_{n} \leq - z) .$ Taking lower limits and using the displayed convergence gives $1 - α_{cov} \leq n \to \infty lim inf p_{n} Pr ∣ τ_{n} - τ_{H} (p_{n}) ∣ \leq z_{1 - α_{cov} /2} \frac{V _{cons} ( G _{n} , p _{n} )}{n},$ which is the claimed coverage bound.

∎

Proof of Theorem 8.

Fix $ϵ \in (0, 1/2)$ , $c_{disp} > 0$ , and $C_{disp} \geq 1$ . Put $t_{n} = n + 1, d_{n} = t_{n}^{2}, ρ = \frac{ϵ + 1/2}{2}, φ = \frac{3 ρ - 1/2}{2}, R (x) = x^{- 1} + (1 - x)^{- 1},$ so that $ϵ < ρ < 1/2$ and $ϵ < φ < 1/2$ , both by direct substitution of $0 < ϵ < 1/2$ . Recall also the objects the argument evaluates: for $i, j \in O_{n}$ , $r_{ij}^{1} (G_{n}, p) = 1 {∣ S_{ij} (G_{n}) ∣ > 0} k \in S_{ij} (G_{n}) \prod p_{k}^{- 1} - 1, r_{ij}^{0} (G_{n}, p) = 1 {∣ S_{ij} (G_{n}) ∣ > 0} k \in S_{ij} (G_{n}) \prod (1 - p_{k})^{- 1} - 1,$ $r_{ij}^{10} (G_{n}) = 1 {∣ S_{ij} (G_{n}) ∣ > 0} .$

Let $I_{n}$ be the disjoint union of a core block of $d_{n}$ interventions and a filler block of $2 d_{n}$ interventions, so $m_{n} = 3 d_{n}$ . Let $O_{n}$ consist of $d_{n}$ core outcomes together with $t_{n}$ filler outcomes for each filler intervention, so $∣ O_{n} ∣ = d_{n} + 2 d_{n} t_{n} .$ Each core outcome is adjacent to every core intervention, while each filler outcome is adjacent only to its designated filler intervention; take all potential-outcome schedules to be zero. Explicitly, $N_{i} (G_{n})$ is the whole core block when $i$ is a core outcome, and $N_{(f, r)} (G_{n}) = {f}$ when $(f, r)$ is the $r$ -th filler outcome of the filler intervention $f$ . Counting the outcomes adjacent to a given intervention, $s_{k} = d_{n} (k core), s_{k} = t_{n} (k filler) .$
Set $B_{n} = m_{n} ρ$ . Since $ϵ < ρ < 1/2$ , one has $ϵ \leq ρ \leq 1 - ϵ$ , and multiplying by $m_{n} \geq 0$ , $m_{n} ϵ \leq B_{n} \leq m_{n} (1 - ϵ) .$
Summing the two degree values over the $d_{n}$ core and $2 d_{n}$ filler interventions, the degree energy is $k \in I_{n} \sum s_{k}^{2} = d_{n} d_{n}^{2} + 2 d_{n} t_{n}^{2} = d_{n}^{3} + 2 d_{n}^{2},$ using $t_{n}^{2} = d_{n}$ ; since $d_{n} \geq 1$ this is strictly positive.
Since $d_{n} \to \infty$ and $c_{disp} > 0$ , for all sufficiently large $n$ , $1 \leq c_{disp} d_{n} .$ Fix such an $n$ . If $k$ is a core intervention, then $s_{k}^{2} = d_{n}^{2}$ and, multiplying the displayed inequality by $d_{n}^{2} > 0$ , $s_{k}^{2} = d_{n}^{2} \leq c_{disp} d_{n}^{3} \leq c_{disp} (d_{n}^{3} + 2 d_{n}^{2}) = c_{disp} l \in I_{n} \sum s_{l}^{2} .$ If $k$ is a filler intervention, then $s_{k}^{2} = t_{n}^{2} = d_{n}$ , and since $d_{n} \geq 1$ , $s_{k}^{2} = d_{n} \leq d_{n}^{2} \leq c_{disp} d_{n}^{3} \leq c_{disp} l \in I_{n} \sum s_{l}^{2} .$ Thus the degree-dispersion condition holds eventually.
Every intervention has the same strictly positive $h$ -weight. Indeed, the ordered pairs $(i, j)$ with $k \in S_{ij} (G_{n})$ are: for a core $k$ , the $d_{n}^{2}$ core-core pairs, each with $∣ S_{ij} (G_{n}) ∣ = d_{n}$ ; and for a filler $k = f$ , the $t_{n}^{2}$ pairs of filler outcomes both carrying the label $f$ , each with $∣ S_{ij} (G_{n}) ∣ = 1$ . A core outcome and a filler outcome share no intervention, and two filler outcomes with distinct labels share none. Hence $h_{k} (G_{n}) = \frac{d _{n}^{2} \cdot d _{n}^{- 1}}{∣ O _{n} ∣} = \frac{d _{n}}{∣ O _{n} ∣} (k core), h_{k} (G_{n}) = \frac{t _{n}^{2} \cdot 1}{∣ O _{n} ∣} = \frac{d _{n}}{∣ O _{n} ∣} (k filler),$ again by $t_{n}^{2} = d_{n}$ . Consequently, for every $k, l \in I_{n}$ , $h_{k} (G_{n}) = h_{l} (G_{n}) = \frac{d _{n}}{∣ O _{n} ∣} > 0 and hence h_{k} (G_{n}) \leq C_{disp} h_{l} (G_{n}),$ the last step because $C_{disp} \geq 1$ . So the $h$ -weight-ratio condition holds for every $n$ .
The surrogate design is homogeneous. The equal-weight calculation above makes the surrogate objective of Definition 10 a positive multiple of a separable barrier sum, $k \in I_{n} \sum h_{k} (G_{n}) {p_{k}^{- 1} + (1 - p_{k})^{- 1}} = \frac{d _{n}}{∣ O _{n} ∣} k \in I_{n} \sum R (p_{k}) .$ For $0 < r < 1$ , the barrier $R$ satisfies $R (x) - R (r) - R^{'} (r) (x - r) = \frac{( x - r ) ^{2} { r ^{2} + 2 r x - 2 r - x + 1 }}{r ^{2} x ( 1 - r ) ^{2} ( 1 - x )} (0 < x < 1) .$ The denominator is positive. The bracket is also positive: if $r \leq 1/2$ , then $r^{2} + 2 r x - 2 r - x + 1 = r^{2} + (1 - 2 r) (1 - x) > 0,$ and if $1/2 < r$ , then $r^{2} + 2 r x - 2 r - x + 1 = (1 - r)^{2} + (2 r - 1) x > 0.$ Therefore $R (r) + R^{'} (r) (x - r) \leq R (x) (0 < x < 1),$ and equality holds exactly when $x = r$ , since the displayed gap then has positive denominator and positive bracket, leaving only the factor $(x - r)^{2}$ to vanish. Summing the tangent inequality over $k \in I_{n}$ at $r = ρ$ and using the budget $\sum_{k \in I_{n}} p_{k} = B_{n} = m_{n} ρ$ , the linear terms cancel and $m_{n} R (ρ) \leq k \in I_{n} \sum R (p_{k}) for every p \in P_{n, B_{n}, ϵ},$ with equality only if $p_{k} = ρ$ for every $k$ . The homogeneous vector $p_{k}^{hom} = ρ$ is feasible, because $ϵ < ρ < 1/2 < 1 - ϵ$ and $\sum_{k \in I_{n}} ρ = m_{n} ρ = B_{n}$ . Hence the surrogate minimizer is unique and $p_{n}^{d e g} (G_{n}) = p^{hom} .$
Two envelope evaluations. For any design $p$ , Definition 6 splits over the outcome blocks. A core-core ordered pair has $S_{ij} (G_{n})$ equal to the whole core block, of size $d_{n}$ ; a pair of filler outcomes with the same label $f$ has $S_{ij} (G_{n}) = {f}$ ; all remaining ordered pairs have $S_{ij} (G_{n}) = \emptyset$ and contribute $0$ . There are $d_{n}^{2}$ pairs of the first kind and $2 d_{n} t_{n}^{2}$ of the second. At the homogeneous design $p^{hom}$ this gives $\frac{V _{env} ( G _{n} , p ^{hom} )}{4} = \frac{1}{∣ O _{n} ∣} {d_{n}^{2} (ρ^{- d_{n}} + (1 - ρ)^{- d_{n}}) + 2 d_{n} t_{n}^{2} R (ρ)},$ since a core-core pair contributes $(ρ^{- d_{n}} - 1) + ((1 - ρ)^{- d_{n}} - 1) + 2 = ρ^{- d_{n}} + (1 - ρ)^{- d_{n}}$ and a same-label filler pair contributes $(ρ^{- 1} - 1) + ((1 - ρ)^{- 1} - 1) + 2 = R (ρ)$ .

For comparison, let $q$ be the design assigning $1/2$ to every core intervention and $φ$ to every filler intervention. It is feasible: $ϵ < φ < 1/2$ and $ϵ < 1/2 < 1 - ϵ$ give the box constraints, and $k \in I_{n} \sum q_{k} = d_{n} \cdot \frac{1}{2} + 2 d_{n} φ = d_{n} (\frac{1}{2} + 3 ρ - \frac{1}{2}) = 3 d_{n} ρ = B_{n} .$ The same block split, with a core-core pair now contributing $2^{d_{n}} + 2^{d_{n}} = 2^{d_{n} + 1}$ , gives $\frac{V _{env} ( G _{n} , q )}{4} = \frac{1}{∣ O _{n} ∣} {d_{n}^{2} 2^{d_{n} + 1} + 2 d_{n} t_{n}^{2} R (φ)} .$
The envelope minimum is positive. The bounded-outcome-degree condition holds here with $\overset{ˉ}{d} = d_{n}$ , since core outcomes have degree $d_{n}$ and filler outcomes degree $1$ . Hence the lower half of the sandwich in Theorem 7, applied at the envelope-optimal design $p_{n}^{*} (G_{n})$ , gives $0 < \frac{d _{n}}{∣ O _{n} ∣} k \in I_{n} \sum R ((p_{n}^{*} (G_{n}))_{k}) = k \in I_{n} \sum h_{k} (G_{n}) {(p_{n}^{*} (G_{n}))_{k}^{- 1} + (1 - (p_{n}^{*} (G_{n}))_{k})^{- 1}} \leq \frac{V _{env} ( G _{n} , p _{n}^{*} ( G _{n} ))}{4},$ the strict positivity because $d_{n} /∣ O_{n} ∣ > 0$ , $I_{n} \neq = \emptyset$ , and $R > 0$ on $(0, 1)$ . Thus $V_{env} (G_{n}, p_{n}^{*} (G_{n})) > 0$ .
Lower bound on the ratio. The positivity just proved selects the positive branch of Definition 11, and the surrogate-design calculation identifies its numerator with the homogeneous envelope. Since $q$ is feasible, $V_{env} (G_{n}, p_{n}^{*} (G_{n})) \leq V_{env} (G_{n}, q)$ , and $V_{env} (G_{n}, p^{hom}) \geq 0$ , so $α_{cert} (G_{n}) = \frac{V _{env} ( G _{n} , p ^{hom} )}{V _{env} ( G _{n} , p _{n}^{*} ( G _{n} ))} \geq \frac{V _{env} ( G _{n} , p ^{hom} )}{V _{env} ( G _{n} , q )} .$

Substituting the two envelope evaluations above, cancelling the common factor $∣ O_{n} ∣^{- 1}$ , and using $2 d_{n} t_{n}^{2} = 2 d_{n}^{2}$ so that $d_{n}^{2}$ cancels as well, $\frac{V _{env} ( G _{n} , p ^{hom} )}{V _{env} ( G _{n} , q )} = \frac{ρ ^{- d_{n}} + ( 1 - ρ ) ^{- d_{n}} + 2 R ( ρ )}{2 ^{d_{n} + 1} + 2 R ( φ )} \geq \frac{ρ ^{- d_{n}}}{2 ^{d_{n} + 1} + 2 R ( φ )},$ the inequality because $(1 - ρ)^{- d_{n}} \geq 0$ and $R (ρ) > 0$ . Hence $α_{cert} (G_{n}) \geq \frac{ρ ^{- d_{n}}}{2 ^{d_{n} + 1} + 2 R ( φ )} .$
Since $2^{d_{n}} \to \infty$ , eventually $2 R (φ) \leq 2^{d_{n}}$ , so the denominator is at most $2^{d_{n} + 1} + 2^{d_{n}} = 3 \cdot 2^{d_{n}}$ and $α_{cert} (G_{n}) \geq \frac{ρ ^{- d_{n}}}{3 \cdot 2 ^{d_{n}}} = \frac{1}{3} (2 ρ)^{- d_{n}} .$ Finally, $ρ < 1/2$ , so $(2 ρ)^{- 1} > 1$ ; as $d_{n} \to \infty$ , the right-hand side tends to $+ \infty$ . Therefore $α_{cert} (G_{n}) \to \infty$ .

∎

Proof of Theorem 6.

Throughout, $e_{k}$ is the $k$ -th coordinate vector on $R^{I_{n}}$ , and we write $η_{box} = min {ρ - ϵ, 1 - ϵ - ρ} > 0,$ which is positive because $ϵ < ρ < 1 - ϵ$ . Recall from Definition 8 the summation formula defining the envelope gradient score $g_{k} (G_{n}, p)$ . Throughout we use the reciprocal convention $1/0 = 0,$ so that the normalizing factor $1/ n$ , with $n = ∣ O_{n} ∣$ , is defined for every finite outcome-unit set: it is the ordinary reciprocal when $O_{n} \neq = \emptyset$ and equals $0$ when $O_{n} = \emptyset$ . Under this convention the gradient formula of Definition 8 and the identities derived from it below hold verbatim, with no separate nonemptiness hypothesis.

Suppose that the homogeneous-point gradient scores are not all equal. First, $p^{hom} \in P_{n, B_{n}, ϵ}$ : each coordinate equals $ρ \in (ϵ, 1 - ϵ) \subseteq [0, 1]$ , and $k \in I_{n} \sum p_{k}^{hom} = m_{n} ρ = B_{n} .$

We next show that $p^{hom}$ is not a minimizer. Otherwise, Theorem 3 supplies a budget multiplier $λ_{n}$ and nonnegative upper- and lower-box multipliers $ν_{k, n}^{+}$ and $ν_{k, n}^{-}$ satisfying $g_{k} (G_{n}, p^{hom}) = λ_{n} - ν_{k, n}^{+} + ν_{k, n}^{-},$ together with the complementary-slackness identities $ν_{k, n}^{+} (p_{k}^{hom} - (1 - ϵ)) = 0, ν_{k, n}^{-} (ϵ - p_{k}^{hom}) = 0.$ Since $p_{k}^{hom} = ρ$ and $ϵ < ρ < 1 - ϵ$ , both factors multiplying the respective multipliers are nonzero. Thus $ν_{k, n}^{+} = ν_{k, n}^{-} = 0$ for every $k$ , so all gradient scores equal $λ_{n}$ , a contradiction.

Choose $a$ attaining the maximum and $b$ attaining the minimum of $k \mapsto g_{k} (G_{n}, p^{hom})$ , which exist because $I_{n}$ is finite and nonempty. If these extrema were equal, all scores would be equal, contrary to hypothesis. Hence $Δ_{g} = g_{a} (G_{n}, p^{hom}) - g_{b} (G_{n}, p^{hom}) > 0.$ For these extremal indices, set $d = e_{b} - e_{a}, γ (s) = \frac{1}{4} V_{env} (G_{n}, p^{hom} + s d) .$ The segment $p^{hom} + s d$ is feasible for $s \in [- η_{box}, η_{box}]$ . Indeed $∣ d_{k} ∣ \leq 1$ , so for $0 \leq s \leq η_{box}$ every coordinate satisfies $ϵ \leq ρ - s \leq ρ + s d_{k} \leq ρ + s \leq 1 - ϵ$ by the two bounds defining $η_{box}$ ; the budget is preserved because $k \in I_{n} \sum d_{k} = 1 - 1 = 0,$ so $\sum_{k} (p_{k}^{hom} + s d_{k}) = B_{n}$ . For $s < 0$ the same argument applies with the direction reversed. Moreover, on $0 \leq s \leq η_{box}$ , $p_{k}^{hom} + s d_{k} \geq ρ - s \geq ϵ \geq ϵ /2, 1 - (p_{k}^{hom} + s d_{k}) \geq 1 - ρ - s \geq ϵ \geq ϵ /2.$ On this region the envelope agrees with the globally twice continuously differentiable cutoff extension obtained by replacing each reciprocal factor by a $C^{2}$ reciprocal cutoff that agrees with $x^{- 1}$ for $x \geq ϵ /2$ . Consequently $γ$ is twice continuously differentiable on $[0, η_{box}]$ and differentiable at $0$ . The line-calculus identity for $V_{env} (G_{n}, \cdot) /4$ along $d$ gives $γ^{'} (0) = k \in I_{n} \sum d_{k} g_{k} (G_{n}, p^{hom}) = g_{b} (G_{n}, p^{hom}) - g_{a} (G_{n}, p^{hom}) = - Δ_{g} .$

Define the directional second-order modulus for this same pair by $L_{ab} = q \in P_{n, B_{n}, ϵ} sup \frac{d ^{2}}{d t ^{2}} {\frac{1}{4} V_{env} (G_{n}, q + t (e_{b} - e_{a}))}_{t = 0} .$ The supremum is finite: the feasible class is compact by Theorem 3, and the displayed directional curvature is continuous in the base point through the same $C^{2}$ cutoff extension. For $0 \leq t \leq η_{box}$ , the shifted base point $p^{hom} + t d$ is feasible, and the second derivative of $γ$ at $t$ is precisely the directional curvature at that base point. Hence $γ^{''} (t) \leq L_{ab} (0 \leq t \leq η_{box}) .$ Convexity of $V_{env} (G_{n}, \cdot)$ on $P_{n, B_{n}, ϵ}$ , supplied by Theorem 3, makes $γ$ convex on the feasible line segment. Thus the curvature at the homogeneous base point is nonnegative, and since that curvature is one of the feasible values bounded by the displayed supremum, $0 \leq L_{ab} .$

Define $s_{*} = {η_{box}, min {η_{box}, Δ_{g} / L_{ab}}, L_{ab} = 0, L_{ab} \neq = 0.$ Then $s_{*} \in [0, η_{box}]$ . The one-dimensional second-order descent bound applied to $γ$ , with initial slope at most $- Δ_{g}$ and second derivative bounded above by $L_{ab}$ on the segment, gives $γ (0) - γ (s_{*}) \geq \frac{Δ _{g}}{2} s_{*} .$ The design $q = p^{hom} + s_{*} d$ is feasible by the segment argument above. Therefore, for every $p_{n}^{*} (G_{n}) \in argmin_{p \in P_{n, B_{n}, ϵ}} V_{env} (G_{n}, p)$ , $V_{env} (G_{n}, p_{n}^{*} (G_{n})) \leq V_{env} (G_{n}, q) .$ Multiplying the preceding descent inequality by $4$ , and using $4 γ (0) = V_{env} (G_{n}, p^{hom})$ and $4 γ (s_{*}) = V_{env} (G_{n}, q)$ , gives $V_{env} (G_{n}, p^{hom}) - V_{env} (G_{n}, p_{n}^{*} (G_{n})) \geq V_{env} (G_{n}, p^{hom}) - V_{env} (G_{n}, q) \geq 2 Δ_{g} s_{*},$ which is the asserted bound after substituting $η_{box}$ and $s_{*}$ .

Finally, $p_{n}^{*} (G_{n}) \neq = p^{hom}$ , since otherwise $p^{hom}$ would be a minimizer. Optimality and feasibility of $p^{hom}$ give $V_{env} (G_{n}, p_{n}^{*} (G_{n})) \leq V_{env} (G_{n}, p^{hom})$ ; equality would again make $p^{hom}$ a minimizer. Thus $V_{env} (G_{n}, p_{n}^{*} (G_{n})) < V_{env} (G_{n}, p^{hom}) .$
Now suppose that $∣ N_{i} (G_{n}) ∣ = 1$ for every $i \in O_{n}$ , and fix $k \in I_{n}$ . If $k \in S_{ij} (G_{n})$ , then $S_{ij} (G_{n})$ is a nonempty subset of $N_{i} (G_{n})$ , and hence has cardinality one. Since $p^{hom}$ is constant, every nonzero summand in the gradient formula of Definition 8, evaluated at $p^{hom}$ , equals $- ρ^{- 1} ρ^{- 1} + (1 - ρ)^{- 1} (1 - ρ)^{- 1} = ((1 - ρ)^{2})^{- 1} - (ρ^{2})^{- 1} .$ For the counting term, the intervention-side degree is $s_{k} = ∣ {i \in O_{n} : k \in N_{i} (G_{n})} ∣ .$ The condition $k \in S_{ij} (G_{n})$ is exactly the conjunction $k \in N_{i} (G_{n})$ and $k \in N_{j} (G_{n})$ . Hence the ordered pairs $(i, j)$ contributing to the sum are precisely ${i \in O_{n} : k \in N_{i} (G_{n})} \times {j \in O_{n} : k \in N_{j} (G_{n})},$ and their number is $s_{k}^{2}$ . Substitution into the gradient formula gives, for $ρ \in (0, 1)$ and $n = ∣ O_{n} ∣$ , $g_{k} (G_{n}, p^{hom}) = \frac{s _{k}^{2}}{n} ((1 - ρ)^{- 2} - ρ^{- 2}),$ which is the displayed formula. When $O_{n} \neq = \emptyset$ both sides are read in the ordinary way; when $O_{n} = \emptyset$ the defining double sum is empty and $s_{k} = 0$ for every $k$ , so both sides are $0$ under the reciprocal convention fixed above.
Retain the singleton-neighborhood condition and suppose that $s_{a}^{2} \neq = s_{b}^{2}$ for some $a, b \in I_{n}$ . Put $C = ((1 - ρ)^{2})^{- 1} - (ρ^{2})^{- 1} .$ This scalar is nonzero. Indeed, if $C = 0$ , then $(1 - ρ)^{2} = ρ^{2}$ ; thus either $1 - ρ = ρ$ , contradicting $ρ \neq = 1/2$ , or $1 - ρ = - ρ$ , which would imply $1 = 0$ .

Also $n = ∣ O_{n} ∣ > 0$ . Otherwise $O_{n}$ would be empty, so ${i \in O_{n} : k \in N_{i} (G_{n})}$ would be empty and $s_{k} = 0$ for every $k$ , making $s_{a}^{2} \neq = s_{b}^{2}$ impossible. Hence $C / n \neq = 0$ , and the formula of the preceding step gives $g_{a} (G_{n}, p^{hom}) - g_{b} (G_{n}, p^{hom}) = \frac{C}{n} (s_{a}^{2} - s_{b}^{2}) \neq = 0,$ so that $g_{a} (G_{n}, p^{hom}) \neq = g_{b} (G_{n}, p^{hom}) .$ The conclusions of the first step therefore apply.

∎

Proof of Theorem 7.

Put $A (q) := k \in I_{n} \sum h_{k} (G_{n}) {q_{k}^{- 1} + (1 - q_{k})^{- 1}}, C := max {1, ϵ^{- (\overset{ˉ}{d} - 1)}} .$ Then $C \geq 1$ , hence $C \geq 0$ . Recall also the three covariance loads, for $i, j \in O_{n}$ : $r_{ij}^{1} (G_{n}, q) = 1 {∣ S_{ij} (G_{n}) ∣ > 0} k \in S_{ij} (G_{n}) \prod q_{k}^{- 1} - 1, r_{ij}^{0} (G_{n}, q) = 1 {∣ S_{ij} (G_{n}) ∣ > 0} k \in S_{ij} (G_{n}) \prod (1 - q_{k})^{- 1} - 1,$ $r_{ij}^{10} (G_{n}) = 1 {∣ S_{ij} (G_{n}) ∣ > 0} .$

By Theorem 3, whose positivity-margin and feasible-budget hypotheses are exactly those assumed here, the envelope-optimal design $p_{n}^{*} (G_{n})$ is feasible and satisfies $V_{env} (G_{n}, p_{n}^{*} (G_{n})) \leq V_{env} (G_{n}, q) for every q \in P_{n, B_{n}, ϵ} .$
On $P_{n, B_{n}, ϵ}$ , every $q_{k}$ and $1 - q_{k}$ lies in $[ϵ, 1 - ϵ]$ , hence is strictly positive. Thus $A$ is continuous there, being a finite sum of reciprocals of nonvanishing continuous coordinate functions. Nonemptiness and compactness from Theorem 3 therefore yield a feasible surrogate design $p_{n}^{d e g} (G_{n})$ such that $A (p_{n}^{d e g} (G_{n})) \leq A (q) for every q \in P_{n, B_{n}, ϵ} .$
Fix $q \in P_{n, B_{n}, ϵ}$ , and write $K_{ij} := r_{ij}^{1} (G_{n}, q) + r_{ij}^{0} (G_{n}, q) + 2 r_{ij}^{10} (G_{n}) .$ Substituting the definition of $h_{k} (G_{n})$ into $A (q)$ and exchanging the order of the finite summations, $A (q) = i \in O_{n} \sum j \in O_{n} \sum k \in S_{ij} (G_{n}) \sum n^{- 1} ∣ S_{ij} (G_{n}) ∣^{- 1} {q_{k}^{- 1} + (1 - q_{k})^{- 1}},$ and Definition 6 gives $\frac{V _{env} ( G _{n} , q )}{4} = i \in O_{n} \sum j \in O_{n} \sum n^{- 1} K_{ij} .$ For a fixed pair $(i, j)$ , let $S = S_{ij} (G_{n})$ . If $S = \emptyset$ , then $K_{ij} = 0$ and the corresponding triple-sum contribution to $A (q)$ is an empty sum. Otherwise, since $0 < q_{k} < 1$ for each $k \in S$ , the two reciprocal factors $q_{k}^{- 1}$ and $(1 - q_{k})^{- 1}$ are at least one. Hence the product of the remaining treated reciprocal factors is at least one, so $q_{k}^{- 1} \leq ℓ \in S \prod q_{ℓ}^{- 1} (k \in S),$ and averaging over $k \in S$ gives $∣ S ∣^{- 1} k \in S \sum q_{k}^{- 1} \leq k \in S \prod q_{k}^{- 1} .$ The same argument applied to the control reciprocal factors gives $∣ S ∣^{- 1} k \in S \sum (1 - q_{k})^{- 1} \leq k \in S \prod (1 - q_{k})^{- 1} .$ For nonempty $S$ , the displayed definitions of the loads give $K_{ij} = (k \in S \prod q_{k}^{- 1} - 1) + (k \in S \prod (1 - q_{k})^{- 1} - 1) + 2 = k \in S \prod q_{k}^{- 1} + k \in S \prod (1 - q_{k})^{- 1} .$ Adding the preceding two inequalities yields $∣ S ∣^{- 1} k \in S \sum {q_{k}^{- 1} + (1 - q_{k})^{- 1}} \leq K_{ij} .$ Multiplication by $n^{- 1} \geq 0$ and summation over $(i, j)$ , with the empty-shared-neighborhood pairs contributing zero on both sides, prove $A (q) \leq \frac{V _{env} ( G _{n} , q )}{4} .$
For the reverse bound, retain $S \neq = \emptyset$ . Since $S \subseteq N_{i} (G_{n})$ , Assumption 6 gives $∣ S ∣ \leq d_{i} \leq \overset{ˉ}{d}$ . Moreover, the feasibility bounds $ϵ \leq q_{k} \leq 1 - ϵ$ give $0 \leq q_{k}^{- 1} \leq ϵ^{- 1}, 0 \leq (1 - q_{k})^{- 1} \leq ϵ^{- 1} .$ After deleting any single index $k \in S$ , each treated or control reciprocal product has $∣ S ∣ - 1$ factors and is therefore bounded by $(ϵ^{- 1})^{∣ S ∣ - 1} = ϵ^{- (∣ S ∣ - 1)} \leq ϵ^{- (\overset{ˉ}{d} - 1)} \leq C,$ the first inequality because $0 < ϵ \leq 1$ makes $t \mapsto ϵ^{- t}$ nondecreasing and $∣ S ∣ \leq \overset{ˉ}{d}$ . For nonnegative reciprocal factors whose product after removal of any one factor is at most $C$ , the full product is at most $C$ times the factors’ average: for each $k \in S$ , $ℓ \in S \prod q_{ℓ}^{- 1} = q_{k}^{- 1} ℓ \in S ∖ {k} \prod q_{ℓ}^{- 1} \leq C q_{k}^{- 1},$ and averaging over $k \in S$ gives the treated reciprocal claim. Applying the same argument to the control reciprocal factors gives $k \in S \prod q_{k}^{- 1} \leq C ∣ S ∣^{- 1} k \in S \sum q_{k}^{- 1}, k \in S \prod (1 - q_{k})^{- 1} \leq C ∣ S ∣^{- 1} k \in S \sum (1 - q_{k})^{- 1} .$ Adding these and using the preceding identity for $K_{ij}$ , $K_{ij} \leq C ∣ S ∣^{- 1} k \in S \sum {q_{k}^{- 1} + (1 - q_{k})^{- 1}} .$ If $S = \emptyset$ , then $K_{ij} = 0$ by the displayed load definitions, and the associated triple-sum contribution on the right-hand side of the final summed inequality is empty. Multiplying the nonempty-pair inequality by $n^{- 1} \geq 0$ , summing over all nonempty $(i, j)$ , and adding the empty pairs with zero contribution on both sides, the displayed expansions above yield $\frac{V _{env} ( G _{n} , q )}{4} \leq C A (q) .$ This proves the asserted sandwich for every feasible $q$ .
Let $V_{*} := V_{env} (G_{n}, p_{n}^{*} (G_{n}))$ . If $V_{*} > 0$ , the two sandwich bounds and the minimizing property of $p_{n}^{d e g} (G_{n})$ established above imply $\frac{V _{env} ( G _{n} , p _{n}^{d e g} ( G _{n} ) )}{4} \leq C A (p_{n}^{d e g} (G_{n})) \leq C A (p_{n}^{*} (G_{n})) \leq C \frac{V _{*}}{4},$ the middle step because $p_{n}^{*} (G_{n})$ is feasible and $C \geq 0$ . Thus $V_{env} (G_{n}, p_{n}^{d e g} (G_{n})) \leq C V_{*},$ and division by $V_{*} > 0$ , together with Definition 11, gives $α_{cert} (G_{n}) \leq C$ . If $V_{*} \neq > 0$ , that definition assigns $α_{cert} (G_{n}) = 1$ , which is at most $C$ . The claimed approximation-ratio bound follows.

∎

References

Lu, Sizhu and Shi, Lei and Fang, Yue and Zhang, Wenxin and Ding, Peng (2025). Design-based causal inference in bipartite experiments. . arXiv
Harshaw, Christopher and S{\"a}vje, Fredrik and Eisenstat, David and Mirrokni, Vahab and Pouget-Abadie, Jean (2021). Design and Analysis of Bipartite Experiments under a Linear Exposure-Response Model. . arXiv
Davide Viviano (2020). Experimental Design under Network Interference. . arXiv
Michael P. Leung (2019). Causal Inference Under Approximate Neighborhood Interference. . arXiv
Aronow, Peter M. and Samii, Cyrus (2017). Estimating Average Causal Effects under General Interference, with Application to a Social Network Experiment. The Annals of Applied Statistics. doi
Ugander, Johan and Yin, Hao (2020). Randomized Graph Cluster Randomization. . arXiv
Eichhorn, Matthew and Khan, Samir and Ugander, Johan and Yu, Christina Lee (2024). Low-Order Outcomes and Clustered Designs: Combining Design and Analysis for Causal Inference under Network Interference. . arXiv
Chattopadhyay, Ambarish and Imai, Kosuke and Zubizarreta, Jos{\'e} R. (2023). Design-Based Inference for Generalized Network Experiments with Stochastic Interventions. . arXiv
Doudchenko, Nick and Zhang, Minzhengxiong and Drynkin, Evgeni and Airoldi, Edoardo and Mirrokni, Vahab and Pouget-Abadie, Jean (2020). Causal Inference with Bipartite Designs. . arXiv
Brennan, Jennifer and Mirrokni, Vahab and Pouget-Abadie, Jean (2022). Cluster Randomized Designs for One-Sided Bipartite Experiments. Advances in Neural Information Processing Systems.
Hudgens, Michael G. and Halloran, M. Elizabeth (2008). Toward Causal Inference with Interference. Journal of the American Statistical Association. doi
Eckles, Dean and Karrer, Brian and Ugander, Johan (2017). Design and Analysis of Experiments in Networks: Reducing Bias from Interference. Journal of Causal Inference. doi
Sävje, Fredrik and Aronow, Peter M. and Hudgens, Michael G. (2021). Average treatment effects in the presence of unknown interference. The Annals of Statistics. doi
Zigler, Corwin M. and Papadogeorgou, Georgia (2018). Bipartite Causal Inference with Interference. . arXiv
Baldi, Pierre and Rinott, Yosef (1989). On Normal Approximations of Distributions in Terms of Dependency Graphs. The Annals of Probability. doi
Boyd, Stephen and Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press.

Formal layer — Lean correspondence

Every object below is formalized in Lean 4. Click a verified row to view its statement; the rest link to the Lean source.

Setups (2)

Setup S-1 — Finite-population Bernoulli randomization design (assignment world): probability comes from the experimenter's independent heterogeneous Bernoulli coin flips over the finite assignment space Ω = (I_n → Bool); the design variable p and its feasible class are the decision objects. — Reuse the finite-sum design layer FiniteDesign (E/Var/Cov as Finset algebra) and the product Bernoulli design bernoulliDesign p (per-unit coin flips, cross-unit independence STRUCTURAL via prodDesign). This directly realizes ass:independent-heterogeneous-bernoulli. bernoulliDesign_E_treat/_E_ctrl give the marginal treatment/control expectations feeding pi_i^1/pi_i^0. The positivity floor epsilon and budget B_n restrict p but do not change the world. Verified signatures: bernoulliDesign (Bernoulli.lean:60), FiniteDesign (Design.lean).
Setup S-2 — Bipartite interference graph + fixed finite-population potential-outcome schedule: known bipartite graph G_n over I_n × O_n, outcome neighborhoods N_i(G_n), fixed bounded potential outcomes Y_i(z_{N_i}), Hajek exposure estimator and its graph-only conservative variance objects. — Search trace: grepped '## Experimentation' in ../doc/API.md + scanned Causalean/Experimentation/{DesignBased,UnknownInterference}; no BipartiteDesign / bipartite-graph structure exists (all interference substrate is one-mode: ExposureMappingInterference, UnknownInterference.Interferes/InterfDep). So the bipartite graph layer (I_n, O_n, G_n, N_i, M_k, degrees, shared sets S_ij) is new local scaffolding. It nonetheless SITS INSIDE the S1 FiniteDesign world: fixed potential outcomes Y_i as functions of the treatment subvector on N_i mirror UnknownInterference.y / y_eq_of_agree_on_interferers (analogue F3 should follow for the interference-restriction algebra), and the all-treated/all-control exposure indicators T_i/C_i are products over N_i (compare Exposure.expoInd). Define a local BipartiteExperiment structure bundling G_n and the neighborhood accessors.

Definitions (11)

Definition P-1 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.FeasibleDesign P_{n,B_n,epsilon} = {p in [0,1]^{m_n} : epsilon <= p_k <= 1-epsilon for every k in I_n, and sum_{k in I_n} p_k = B_n}
Definition P-2 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.BipartiteExperiment.hajekDenominators D_1(p,Z) = sum_{i in O_n} T_i(Z) / pi_i^1(p), D_0(p,Z) = sum_{i in O_n} C_i(Z) / pi_i^0(p)
Definition P-3 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.BipartiteExperiment.hajekEstimator hat_tau_H(p) = 1{D_1(p,Z) > 0}{sum_{i in O_n} T_i(Z) Y_i^obs / pi_i^1(p)} / D_1(p,Z) - 1{D_0(p,Z) > 0}{sum_{i in O_n} C_i(Z) Y_i^obs / pi_i^0(p)} / D_0(p,Z)
Definition P-4 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.BipartiteExperiment.linScore eta_i(p,Z) = (T_i(Z)/pi_i^1(p) - 1)(Y_i^1-mu_1) - (C_i(Z)/pi_i^0(p) - 1)(Y_i^0-mu_0)
Definition P-5 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.BipartiteExperiment.varScale sigma_{G_n,p}^2(Y) = n Var_p(n^(-1) sum_{i in O_n} eta_i(p,Z)) = n^(-1) sum_{i,j in O_n} E_p[eta_i(p,Z) eta_j(p,Z)]
Definition P-6 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.BipartiteExperiment.varEnvelope V_env(G_n,p) = 4 n^(-1) sum_{i,j in O_n} {r_{ij}^1(G_n,p) + r_{ij}^0(G_n,p) + 2 r_{ij}^{10}(G_n)}
Definition P-7 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.optimalDesign p_n^*(G_n) in argmin_{p in P_{n,B_n,epsilon}} V_env(G_n,p), whenever the argmin set is nonempty
Definition P-8 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.BipartiteExperiment.envelopeGrad g_k(G_n,p) = partial_{p_k}(V_env(G_n,p)/4) = n^(-1) sum_{i,j in O_n : k in S_{ij}(G_n)} {-(product_{ell in S_{ij}(G_n)} p_ell^(-1)) p_k^(-1) + (product_{ell in S_{ij}(G_n)} (1-p_ell)^(-1)) (1-p_k)^(-1)}
Definition P-9 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.BipartiteExperiment.varEstCons hat_V_cons(G_n,p) = V_env(G_n,p)
Definition P-10 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.surrogateDesign p_n^{deg}(G_n) in argmin_{p in P_{n,B_n,epsilon}} sum_{k in I_n} h_k(G_n){p_k^(-1) + (1-p_k)^(-1)}, whenever the argmin set is nonempty
Definition P-11 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.approxRatio alpha_cert(G_n) = V_env(G_n,p_n^{deg}(G_n)) / min_{p in P_{n,B_n,epsilon}} V_env(G_n,p) when min_{p in P_{n,B_n,epsilon}} V_env(G_n,p) > 0, and alpha_cert(G_n) = 1 when min_{p in P_{n,B_n,epsilon}} V_env(G_n,p) = 0 (no-loss convention: a zero envelope minimum forces V_env(G_n,p_n^{deg}(G_n))=0 as well, since V_env is a nonnegative sum over shared-neighborhood pairs that vanishes for every feasible design precisely when there are no such pairs, so there is no relative loss). Thus alpha_cert(G_n) is a total, [1,infty)-valued observable on the admitted bounded-degree graph class.

Assumptions (8)

Assumption A-1 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.BipartiteInterference For every i in O_n and every z,z' in {0,1}^{m_n}, z_{N_i(G_n)} = z'_{N_i(G_n)} implies Y_i(z_{N_i}) = Y_i(z'_{N_i}).
Assumption A-2 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.IndepHeteroBernoulli For every k in I_n, Z_k is Bernoulli(p_k), and the collection {Z_k : k in I_n} is mutually independent.
Assumption A-3 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.PositivityFloor For every k in I_n, epsilon <= p_k <= 1-epsilon.
Assumption A-4 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.BudgetBalance sum_{k in I_n} p_k = B_n.
Assumption A-5 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.BoundedOutcomes For every i in O_n, |Y_i^1| <= 1 and |Y_i^0| <= 1.
Assumption A-6 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.BoundedOutcomeDegree max_{i in O_n} d_i <= dbar.
Assumption A-7 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.BoundedOverlapDependency Delta_n <= Dbar.
Assumption A-8 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.VarianceNondegenerate liminf_{n -> infty} sigma_{G_n,p_n^*(G_n)}^2(Y) > 0.

Lemmas (2)

Lemma L-1 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.denominator_positivity Under ass:independent-heterogeneous-bernoulli, ass:bounded-outcome-degree, and ass:bounded-overlap-dependency, sup_{p in P_{n,B_n,epsilon}} P_p(D_1(p,Z) = 0 or D_0(p,Z) = 0) = O(n^{-1}). ↗ Lean
Lemma L-2 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.bounded_degree_dependency_clt Let {X_{n,i}:1<=i<=n} be centered real random variables with a dependency graph of maximum degree at most D, |X_{n,i}|<=M for fixed finite D and M, and Var(sum_i X_{n,i})=v_n with v_n>=c n for some c>0 eventually. Then (sum_i X_{n,i})/sqrt(v_n) converges in distribution to N(0,1).

Theorems (8)

Theorem T-1 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.homogeneous_reduction Under ass:independent-heterogeneous-bernoulli, if p_k = p for every k in I_n for a common scalar p in (0,1), then r_{ij}^1(G_n,p) = 1{S_{ij}(G_n) != emptyset}(p^(-|S_{ij}(G_n)|) - 1), r_{ij}^0(G_n,p) = 1{S_{ij}(G_n) != emptyset}((1-p)^(-|S_{ij}(G_n)|) - 1), r_{ij}^{10}(G_n) = 1{S_{ij}(G_n) != emptyset}, and sigma_{G_n,p}^2(Y) = n^(-1) sum_{i,j in O_n} [r_{ij}^1(G_n,p)(Y_i^1-mu_1)(Y_j^1-mu_1) + r_{ij}^0(G_n,p)(Y_i^0-mu_0)(Y_j^0-mu_0) + 2 r_{ij}^{10}(G_n)(Y_i^1-mu_1)(Y_j^0-mu_0)], which is the homogeneous Bernoulli Hajek overlap formula of Lu, Shi, Fang, Zhang, and Ding (2025).
Theorem T-2 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.hetero_envelope Under ass:independent-heterogeneous-bernoulli and ass:bounded-outcomes, for every p in (0,1)^{m_n}, E_p[eta_i(p,Z) eta_j(p,Z)] = r_{ij}^1(G_n,p)(Y_i^1-mu_1)(Y_j^1-mu_1) + r_{ij}^0(G_n,p)(Y_i^0-mu_0)(Y_j^0-mu_0) + r_{ij}^{10}(G_n){(Y_i^1-mu_1)(Y_j^0-mu_0) + (Y_i^0-mu_0)(Y_j^1-mu_1)} for every i,j in O_n. Consequently sigma_{G_n,p}^2(Y) = n^(-1) sum_{i,j in O_n} [r_{ij}^1(G_n,p)(Y_i^1-mu_1)(Y_j^1-mu_1) + r_{ij}^0(G_n,p)(Y_i^0-mu_0)(Y_j^0-mu_0) + r_{ij}^{10}(G_n){(Y_i^1-mu_1)(Y_j^0-mu_0) + (Y_i^0-mu_0)(Y_j^1-mu_1)}] <= V_env(G_n,p).
Theorem T-3 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.convex_design The feasible set P_{n,B_n,epsilon} is a nonempty compact convex subset of [0,1]^{m_n}, the map p -> V_env(G_n,p) is convex on P_{n,B_n,epsilon}, and therefore the argmin set in def:optimal-design is nonempty. For every minimizer p_n^*(G_n) there exist lambda_n in R and box multipliers nu_{k,n}^+ >= 0, nu_{k,n}^- >= 0 (k in I_n) such that the observable KKT system g_k(G_n,p_n^*(G_n)) = lambda_n - nu_{k,n}^+ + nu_{k,n}^- holds for each k in I_n, together with nu_{k,n}^+((p_n^*(G_n))_k-(1-epsilon)) = 0 and nu_{k,n}^-(epsilon-(p_n^*(G_n))_k) = 0.
Theorem T-4 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.hetero_clt Under ass:bipartite-interference, ass:independent-heterogeneous-bernoulli, ass:bounded-outcomes, ass:bounded-outcome-degree, ass:bounded-overlap-dependency, and ass:variance-nondegenerate, sqrt(n){hat_tau_H(p_n^*(G_n)) - tau_n} = n^(-1/2) sum_{i in O_n} eta_i(p_n^*(G_n),Z) + o_p(1), and sqrt(n){hat_tau_H(p_n^*(G_n)) - tau_n} / sqrt(sigma_{G_n,p_n^*(G_n)}^2(Y)) ->d N(0,1).
Theorem T-5 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.postdesign_wald Under the assumptions of thm:hetero-clt, hat_V_cons(G_n,p_n^*(G_n)) = V_env(G_n,p_n^*(G_n)) is conservative for sigma_{G_n,p_n^*(G_n)}^2(Y), and for every sequence of potential-outcome schedules satisfying those assumptions, liminf_{n -> infty} P_{p_n^*(G_n)}(tau_n in [hat_tau_H(p_n^*(G_n)) - z_{1-alpha_cov/2} sqrt{hat_V_cons(G_n,p_n^*(G_n)) / n}, hat_tau_H(p_n^*(G_n)) + z_{1-alpha_cov/2} sqrt{hat_V_cons(G_n,p_n^*(G_n)) / n}]) >= 1-alpha_cov.
Theorem T-6 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionCertificateUnbounded For every epsilon in (0,1/2), every c_disp > 0, and every C_disp >= 1, there is a sequence of finite bipartite graphs satisfying the stated positive-energy, degree-dispersion, and h-weight-ratio bounds for which alpha_cert(G_n) tends to infinity. Thus those first-order dispersion summaries do not uniformly bound the surrogate approximation ratio.
Theorem T-7 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.heterogeneity_separation Set rho = B_n / m_n and let p^hom denote the homogeneous feasible design with (p^hom)_k = rho for every k in I_n; assume rho in (epsilon, 1-epsilon) and rho != 1/2. If the homogeneous-point envelope-gradient scores {g_k(G_n, p^hom) : k in I_n} of def:kkt-gradient are not all equal, then p^hom is not a minimizer of p -> V_env(G_n,p) over P_{n,B_n,epsilon}; consequently every envelope-optimal design p_n^*(G_n) of def:optimal-design is non-homogeneous and satisfies the strict inequality V_env(G_n, p_n^*(G_n)) < V_env(G_n, p^hom), and the gap admits the explicit observable lower bound V_env(G_n,p^hom) - V_env(G_n,p_n^*(G_n)) >= 2 Delta_g min{eta_box, Delta_g / L_ab}, where Delta_g = max_{k in I_n} g_k(G_n,p^hom) - min_{k in I_n} g_k(G_n,p^hom) > 0 is the gradient-score spread, eta_box = min{rho - epsilon, 1 - epsilon - rho} > 0, a in argmax_{k in I_n} g_k(G_n,p^hom), b in argmin_{k in I_n} g_k(G_n,p^hom), and L_ab = sup_{q in P_{n,B_n,epsilon}} (e_b - e_a)^T Hess(V_env(G_n,cdot)/4)(q) (e_b - e_a) is the directional second-order modulus of the graph-only envelope along the budget-feasible direction e_b - e_a (all four quantities being observable functions of G_n, epsilon, and B_n), with the bound read as 2 Delta_g eta_box when L_ab = 0. In particular, for singleton-exposure graphs, in which each outcome unit's neighborhood is a single intervention unit so that every nonempty S_{ij}(G_n) is a singleton, the gradient scores reduce to observable per-unit degree summaries, and the hypothesis (hence the strict improvement of the optimal heterogeneous design over the homogeneous design) holds whenever those summaries are not all equal.
Theorem T-8 verified CausalSmith.Experimentation.BipartiteMinimaxDesign.surrogate_certificate Under ass:bounded-outcome-degree, which forces max_{i,j in O_n} |S_{ij}(G_n)| <= dbar, with the explicit constant C(epsilon, dbar) = max{1, epsilon^{-(dbar-1)}} depending only on epsilon and dbar, the observable approximation ratio of def:approximation-ratio satisfies alpha_cert(G_n) <= C(epsilon, dbar). The bound follows from a uniform sandwich, valid for every feasible p in P_{n,B_n,epsilon}, between the graph-only envelope V_env(G_n,p) of def:graph-envelope and the additive degree-surrogate objective sum_{k in I_n} h_k(G_n){p_k^{-1} + (1-p_k)^{-1}} minimized in def:surrogate-design, in which the per-pair product loads over the shared-neighborhood sets S_{ij}(G_n) are comparable to their additive per-coordinate counterparts up to a multiplicative factor controlled by the bounded shared-neighborhood size dbar and the positivity floor epsilon. This is the positive counterpart, in the paper's own sparse bounded-degree regime, of the negative first-order-summary answer proved in oeq:dispersion-certificate.

Auxiliary Lean lemmas (machine-checked) (137)

Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.treatDenominator_zero_prob_le —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.ctrlDenominator_zero_prob_le —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.ctrlDenominator_var_le —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.denominatorKernelBound —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.denominatorKernelBound_nonneg —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.denominatorKernelBound_le_of_floor —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.r1_le_denominatorKernelBound —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.r0_le_denominatorKernelBound —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.treatDenominator_mean —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.ctrlDenominator_mean —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.treatDenominator_var_le —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.denominatorKernelBound_div_card_tendsto_zero —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.prod_union_div_prod_prod_eq_prod_inter_inv —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.centered_treat_treat_moment —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.centered_ctrl_ctrl_moment —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.centered_treat_ctrl_moment —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.mu1_abs_le_one —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.mu0_abs_le_one —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.piT_inv_le_denominatorKernelBound_add_one —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.piC_inv_le_denominatorKernelBound_add_one —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.linScore_abs_le_uniform —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.linScore_abs_le_uniform_floor —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.linScoreOutcomeBlock —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.expT_depends_on_neighborhood —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.expC_depends_on_neighborhood —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.linScore_depends_on_neighborhood —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.disjoint_linScoreOutcomeBlock_of_no_overlap —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.linScoreDepGraph —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.linScoreDepGraph_degree_le —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.linScore_mean_zero —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.r10_comm —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.cross_sum_symm_r10 —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.linScore_pair_moment —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.varScale_pair_moments —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.sum_pair_moment_cross_combined —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.varScale_homogeneous_formula —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.prod_ite_disjoint —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.treat_prod_mul_eq_union —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.ctrl_prod_mul_eq_union —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.treat_ctrl_prod_eq_zero_of_inter_nonempty —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.treat_ctrl_prod_eq_mixed_of_disjoint —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.bernoulli_E_treat_prod —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.bernoulli_E_ctrl_prod —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.bernoulli_E_treat_mul_treat —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.bernoulli_E_ctrl_mul_ctrl —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.average_le_prod_of_one_le —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.prod_le_const_mul_average —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.prod_sdiff_le_inv_pow_card_sub_one —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.inv_pow_card_sub_one_le_certificate —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.surrogateObjective_eq_pairAverage —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.varEnvelope_div_four_eq_pairSum —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.pairAverage_le_envelopeKernel —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.envelopeKernel_le_certificate_pairAverage —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.envelopeGrad_eq_gradient_varEnvelopeExt —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.heteroLinearizationRemainder —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.HeteroLinearization —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.HeteroDenominatorTightnessInput —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.hetero_linearization_of_denominator_tightness —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.HeteroLinScoreCLTInput —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.linScore_sum_square_integral_eq_card_mul_varScale —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.hetero_linscore_clt_of_depgraph —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.hetero_studentized_slutsky —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.remainder_tendstoInProb_zero —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.heteroDenominatorTightness_discharged —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.abs_scaled_univ_sum_le_one —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.mu1_abs_le_one_of_bounded —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.mu0_abs_le_one_of_bounded —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.centeredY1_abs_le_two —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.centeredY0_abs_le_two —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.r1_nonneg —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.r0_nonneg —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.r10_nonneg —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.mul_centered_pair_le_four_mul_of_nonneg —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.pair_kernel_le_envelope_kernel —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.shared_card_eq_one_of_singleton —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.sum_indicator_shared_eq_sdeg_sq_mul —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.singleton_envelopeGrad_eq_sdeg_sq —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.EnvelopeLineC2Data —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.homogeneous_feasible —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.homogeneous_not_minimizer_of_gradient_spread —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.singleton_degree_spread_to_gradient_spread —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.envelope_segment_descent_gap —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.surrogateObjective_continuousOn_feasible —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.optimalDesign_feasible_minimizes —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.surrogateDesign_feasible_minimizes —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionD_tendsto_atTop —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersion_geometric_lower_bound —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionApproxRatio_tendsto_atTop —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionT —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionD —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.DispersionIntervention —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.DispersionOutcome —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_N_core —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_N_filler —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_sdeg_core —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_sdeg_filler —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_shared_core —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_shared_filler —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_shared_core_filler —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_shared_filler_core —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_hWeight_core —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_hWeight_filler —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionD_pos —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_degree_energy —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_degree_energy_pos —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_hWeight_eq —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_hWeight_pos —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionExperiment_boundedOutcomeDegree —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionRho —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionFillerRho —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionBudget —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionHomogeneousDesign —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionComparisonDesign —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionRho_bounds —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionFillerRho_bounds —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionBudget_admissible —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionHomogeneousDesign_feasible —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionComparisonDesign_feasible —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersion_surrogateObjective_eq_weighted_sum —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersion_surrogateDesign_eq_homogeneous —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionHomogeneous_envelope —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionComparison_envelope —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.reciprocalBarrier_pos —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersion_envMin_pos —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersion_approxRatio_ge_envelopeRatio —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersion_approxRatio_lower_bound —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.reciprocalBarrier —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.reciprocalBarrierSlope —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.reciprocalBarrier_tangent_gap —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.reciprocalBarrier_tangent_eq_iff —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.reciprocalBarrier_sum_minimized_at_mean —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.reciprocalBarrier_sum_unique_minimizer —
Definition CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionCore —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.mem_dispersionCore_inl —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.mem_dispersionCore_inr —
Lemma CausalSmith.Experimentation.BipartiteMinimaxDesign.dispersionCore_card —

Symbol realizations (Lean @realizes) (50)

N_i(G_n) verified realized by BipartiteExperiment
Y_i(z_{N_i}) verified realized by BipartiteExperiment
Z verified realized by BipartiteExperiment, expT, variable@175, IndepHeteroBernoulli
Z_k verified realized by BipartiteExperiment, expT, variable@175, IndepHeteroBernoulli
Y_i^1 verified realized by Y1
Y_i^0 verified realized by Y0
mu_1 verified realized by mu1
mu_0 verified realized by mu0
tau_n verified realized by tau
Y verified realized by schedule, BoundedOutcomes
T_i(Z) verified realized by expT
C_i(Z) verified realized by expC
pi_i^1(p) verified realized by piT, EpsilonAdmissible, PositivityFloor, FeasibleDesign
pi_i^0(p) verified realized by piC, EpsilonAdmissible, PositivityFloor, FeasibleDesign
d_i verified realized by deg
M_k(G_n) verified realized by M
s_k verified realized by sdeg
S_{ij}(G_n) verified realized by shared
Delta_n verified realized by overlapNbrs
r_{ij}^1(G_n,p) verified realized by r1
r_{ij}^0(G_n,p) verified realized by r0
r_{ij}^{10}(G_n) verified realized by r10
D_1(p,Z) verified realized by hajekDenominators, denominator_positivity
D_0(p,Z) verified realized by hajekDenominators, denominator_positivity
sigma_{G_n,p}^2(Y) verified realized by varScale
p verified realized by variable@175, ProbVector
epsilon verified realized by EpsilonAdmissible, PositivityFloor, dispersionCertificateUnbounded
V_env(G_n,p) verified realized by EpsilonAdmissible, PositivityFloor, FeasibleDesign, varEnvelope
hat_V_cons(G_n,p) verified realized by EpsilonAdmissible, PositivityFloor, FeasibleDesign, varEstCons
B_n verified realized by BudgetBalance, BudgetAdmissible, denominator_positivity
dbar verified realized by BoundedOutcomeDegree
Dbar verified realized by BoundedOverlapDependency
P_{n,B_n,epsilon} verified realized by FeasibleDesign, feasibleSet, denominator_positivity
h_k(G_n) verified realized by hWeight
p_n^*(G_n) verified realized by optimalDesign
p_n^{deg}(G_n) verified realized by surrogateDesign
L_ab verified realized by dirModulus
alpha_cert(G_n) verified realized by approxRatio
O_n verified realized by denominator_positivity, hetero_clt
n verified realized by denominator_positivity, hetero_clt, postdesign_wald
lambda_n verified realized by convex_design
nu_{k,n}^+ verified realized by convex_design
nu_{k,n}^- verified realized by convex_design
nu_{k,n}^+(range clause pinning the space [0,∞) of ν_k^+) verified realized by convex_design
nu_{k,n}^-(range clause pinning the space [0,∞) of ν_k^-) verified realized by convex_design
c_disp verified realized by dispersionCertificateUnbounded
C_disp verified realized by dispersionCertificateUnbounded
C_disp(nonvacuous theorem regime C_disp ∈ [1,∞), which pins the declared positive domain) verified realized by dispersionCertificateUnbounded
alpha_cov verified realized by postdesign_wald
mu_a verified realized by mu0, mu1

Proof map 9 statements · 6 edges

Graph-Adaptive Bernoulli Design for Bipartite Interference

Abstract

Introduction

Setup and assumptions

Main results

Variance representation and envelope optimization

Large-sample inference and design-stage coverage

When heterogeneous probabilities improve on homogeneity

A bounded-degree surrogate and its limitation

Discussion and extensions

A prespecified design checklist

Limitations and future work

Appendices

Proofs and auxiliary lemmas

Dependency-graph normal approximation

Convex-program provenance

Verification note.

Proofs of the main results

References