Graph-Adaptive Bernoulli Design

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)} \quad\Longrightarrow\quad Y_i\!\left(z_{N_i(G_n)}\right)=Y_i\!\left(z'_{N_i(G_n)}\right).$$

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.

For every $k\in I_n$, $$\epsilon\leq p_k\leq 1-\epsilon.$$

$$\sum_{k\in I_n}p_k=B_n.$$

Define $$\widehat\tau_H(p) = \mathbf 1\{D_1(p,Z)>0\} \frac{\displaystyle\sum_{i\in O_n}\frac{T_i(Z)Y_i^{obs}}{\pi_i^1(p)}}{D_1(p,Z)} - \mathbf 1\{D_0(p,Z)>0\} \frac{\displaystyle\sum_{i\in O_n}\frac{C_i(Z)Y_i^{obs}}{\pi_i^0(p)}}{D_0(p,Z)}.$$

Define $$V_{\mathrm{env}}(G_n,p) = \frac{4}{n}\sum_{i,j\in O_n} \left\{ r_{ij}^1(G_n,p) + r_{ij}^0(G_n,p) + 2r_{ij}^{10}(G_n) \right\}.$$

Let $G_n$ be a bipartite experiment with intervention-unit set $I_n$, and let $\epsilon,B_n\in\mathbb R$. Suppose that

• (Positivity margin.) $0<\epsilon<1/2$;
• (Feasible budget.) $m_n\epsilon\le B_n\le m_n(1-\epsilon)$.

Then $\mathcal P_{n,B_n,\epsilon}$ is nonempty, compact, and convex, and $p\mapsto V_{\mathrm{env}}(G_n,p)$ is convex on $\mathcal P_{n,B_n,\epsilon}$. Moreover, there exists a minimizer $p_n^*(G_n)\in\mathcal P_{n,B_n,\epsilon}$ such that $$V_{\mathrm{env}}(G_n,p_n^*(G_n)) \le V_{\mathrm{env}}(G_n,q) \qquad\text{for every }q\in\mathcal P_{n,B_n,\epsilon}.$$ For every such minimizer $p_n^*(G_n)$, there exist $\lambda_n\in\mathbb R$ and functions $\nu^+_{\cdot,n},\nu^-_{\cdot,n}:I_n\to\mathbb R$ such that, for every $k\in I_n$, $$\nu^+_{k,n}\ge0,\qquad \nu^-_{k,n}\ge0,\qquad g_k(G_n,p_n^*(G_n))=\lambda_n-\nu^+_{k,n}+\nu^-_{k,n},$$ and $$\nu^+_{k,n}\bigl((p_n^*(G_n))_k-(1-\epsilon)\bigr)=0, \qquad \nu^-_{k,n}\bigl(\epsilon-(p_n^*(G_n))_k\bigr)=0.$$

Let $G_n$ be a bipartite experiment with $m_n=|I_n|>0$, and let $\epsilon\in(0,1/2)$. Suppose that:

• (Admissible budget.) $m_n\epsilon\le B_n\le m_n(1-\epsilon)$.
• (Homogeneous rate.) $\rho=B_n/m_n$, with $\epsilon<\rho<1-\epsilon$ and $\rho\neq 1/2$.
• (Homogeneous design.) $p^{\mathrm{hom}}_k=\rho$ 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^{\mathrm{hom}})\neq g_b(G_n,p^{\mathrm{hom}}),$$ then $p^{\mathrm{hom}}$ is not a minimizer of $V_{\mathrm{env}}(G_n,\cdot)$ over $\mathcal P_{n,B_n,\epsilon}$. Moreover, there exist $a,b\in I_n$ attaining, respectively, the maximum and minimum homogeneous-point gradient scores, such that $$\Delta_g:=g_a(G_n,p^{\mathrm{hom}})-g_b(G_n,p^{\mathrm{hom}})>0.$$ For every $p_n^*(G_n)\in\operatorname{argmin}_{p\in\mathcal P_{n,B_n,\epsilon}}V_{\mathrm{env}}(G_n,p)$, $$p_n^*(G_n)\neq p^{\mathrm{hom}},\qquad V_{\mathrm{env}}(G_n,p_n^*(G_n))<V_{\mathrm{env}}(G_n,p^{\mathrm{hom}}),$$ and $$V_{\mathrm{env}}(G_n,p^{\mathrm{hom}})-V_{\mathrm{env}}(G_n,p_n^*(G_n)) \ge 2\Delta_g \begin{cases} \min\{\rho-\epsilon,\,1-\epsilon-\rho\}, & L_{ab}=0,\\ \min\!\left\{\min\{\rho-\epsilon,\,1-\epsilon-\rho\},\,\Delta_g/L_{ab}\right\}, & L_{ab}\neq0, \end{cases}$$ 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^{\mathrm{hom}}) = n^{-1}s_k^2\left((1-\rho)^{-2}-\rho^{-2}\right).$$
• 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.

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

• (Outcome indexing.) For all sufficiently large $n$, $|O_n|=n$.
• (Assignment and interference.) Assumption A-2 and Assumption A-1 hold at every $n$ for the assignment design $D_n$ and probabilities $p_n$.
• (Outcome and graph regularity.) Assumption A-5, Assumption A-6, and Assumption A-7 hold at every $n$, with constants $\bar d$ and $\bar D$, respectively.
• (Feasibility and optimality.) For every $n$, $p_n\in\mathcal P_{n,B_n,\epsilon_n}$ as in Definition P-1, and $$p_n=p_n^*(G_n)$$ as in Definition P-7.
• (Uniform positivity.) There exists $\epsilon_0>0$ such that $\epsilon_0\le\epsilon_n$ for all sufficiently large $n$.
• (Variance.) Assumption A-8 holds for $\sigma^2_{G_n,p_n}(Y)$ as in Definition P-5.

Then, for every $\delta>0$, $$\Pr_{D_n}\!\left( \left| \sqrt n\bigl\{\widehat\tau_H(p_n^*(G_n))-\tau_n\bigr\} -n^{-1/2}\sum_{i\in O_n}\eta_i(p_n^*(G_n),Z) \right|\ge\delta \right)\longrightarrow 0,$$ and, for every $s\in\mathbb R$, $$\Pr_{D_n}\!\left( \frac{\sqrt n\bigl\{\widehat\tau_H(p_n^*(G_n))-\tau_n\bigr\}} {\sqrt{\sigma^2_{G_n,p_n^*(G_n)}(Y)}}\le s \right) \longrightarrow \Pr\!\left\{N(0,1)\le s\right\}.$$

For a sequence of bipartite experiments $G_n$ with outcome sets $O_n$, finite assignment designs, probability vectors $p_n$, positivity margins $\epsilon_n$, and budgets $B_n$, suppose:

• (Outcome indexing.) $|O_n|=n$ for all sufficiently large $n$.
• (Assignment law.) The assignment design satisfies Assumption A-2 with $0\le p_{n,k}\le 1$ for every $n$ and $k\in I_n$.
• (Interference and boundedness.) Assumption A-1, Assumption A-5, Assumption A-6, and Assumption A-7 hold with constants $\bar d$ and $\bar D$.
• (Feasibility and optimality.) For every $n$, $p_n$ is a feasible design in the sense of Definition P-1, $\epsilon_n\in(0,1/2)$, and $$p_n=p_n^*(G_n)$$ in the sense of Definition P-7.
• (Uniform positivity.) There exists $\epsilon_0>0$ such that $\epsilon_0\le\epsilon_n$ for all sufficiently large $n$.
• (Nondegenerate variance.) Assumption A-8 holds for $\sigma^2_{G_n,p_n}(Y)$.
• (Wald critical value.) $\alpha_{\mathrm{cov}}\in(0,1)$, $z_{1-\alpha_{\mathrm{cov}}/2}\ge0$, and $$\Phi\!\left(z_{1-\alpha_{\mathrm{cov}}/2}\right) =1-\frac{\alpha_{\mathrm{cov}}}{2}.$$

Then, for every $n$, $$\sigma^2_{G_n,p_n}(Y)\le \widehat V_{\mathrm{cons}}(G_n,p_n),$$ where $\sigma^2_{G_n,p_n}(Y)$ and $\widehat V_{\mathrm{cons}}(G_n,p_n)$ are as in Definition P-5 and Definition P-9, respectively; moreover, $$1-\alpha_{\mathrm{cov}} \le \liminf_{n\to\infty} \Pr_{p_n}\!\left( \left|\tau_n-\widehat\tau_H(p_n)\right| \le z_{1-\alpha_{\mathrm{cov}}/2} \sqrt{\frac{\widehat V_{\mathrm{cons}}(G_n,p_n)}{n}} \right).$$

For a bipartite experiment on $G_n$, suppose:

• (Admissible floor.) $0<\epsilon<1/2$.
• (Bounded outcome degree.) Assumption A-6 holds with bound $\bar d$.
• (Admissible budget.) $m_n\epsilon\le B_n\le m_n(1-\epsilon)$.

Then, for every $p\in\mathcal P_{n,B_n,\epsilon}$ of Definition P-1, $$\sum_{k\in I_n}h_k(G_n)\!\left\{p_k^{-1}+(1-p_k)^{-1}\right\} \le \frac{V_{\mathrm{env}}(G_n,p)}{4} \le \max\!\left\{1,\epsilon^{-(\bar d-1)}\right\} \sum_{k\in I_n}h_k(G_n)\!\left\{p_k^{-1}+(1-p_k)^{-1}\right\}.$$ Moreover, the approximation ratio of Definition P-11 satisfies $$\alpha_{\mathrm{cert}}(G_n)\le \max\!\left\{1,\epsilon^{-(\bar d-1)}\right\}.$$

For every $\epsilon\in(0,1/2)$, $c_{\mathrm{disp}}>0$, and $C_{\mathrm{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\epsilon\leq B_n\leq m_n(1-\epsilon).$$
• (Positive energy.) $$0<\sum_{k\in I_n}s_k^2.$$

Moreover, for all sufficiently large $n$,

• (Degree dispersion.) For every $k\in I_n$, $$s_k^2\leq c_{\mathrm{disp}}\sum_{l\in I_n}s_l^2.$$
• ($h$-weight ratio.) For every $k,l\in I_n$, $$h_l(G_n)>0\ \Longrightarrow\ h_k(G_n)\leq C_{\mathrm{disp}}\,h_l(G_n).$$

Finally, the approximation ratio of Definition P-11 satisfies $$\alpha_{\mathrm{cert}}(G_n)\longrightarrow\infty .$$