A closed-form randomization test finds the single worst-case allocation in matched-pair binary-outcome studies, enabling exact ATE confidence sets in O(log S) time and avoiding integer programming; the method also extends at no extra computational cost to Rosenbaum-style sensitivity analysis for observational matches.

Main Finding

The paper provides an exact randomization-based confidence set for the average treatment effect (ATE) in matched-pair studies with binary outcomes that requires no monotonicity or distributional assumptions beyond the within-pair coin flip. The core advance is an analytic characterization of the worst-case allocation of attributable effects: two binomial-symmetry lemmas show the hardest-to-reject compatible pattern is a single boundary corner, so testing a composite null reduces to O(1) Binomial-tail evaluation per candidate null and inversion by binary search yields the ATE interval in O(log S) Binomial-tail calculations. The method also extends directly to Rosenbaum’s Γ sensitivity model and yields a simple closed-form expression for design sensitivity.

Key Points

• Problem and target:

  • Focus: matched-pair designs (S pairs, 2S units) with binary outcomes.
  • Targets: attributable effects A1 (net effect among treated) and A0 (among untreated); A1 + A0 = 2S · ATE.
  • Aim: exact randomization inference for A1, A0 and ATE without monotonicity.

• Reduction and statistic:

  • Use McNemar-style reduction: compatible sharp nulls collapse into equivalence classes indexed by (m+0, m+1), the counts of discordant pairs where the treated (resp. control) unit would be the success-under-control.
  • Under random assignment (or strong ignorability), m+0 ∼ Binomial(m+0 + m+1, 1/2) under a sharp null.

• Two lemmas identify the worst-case:

  • Lemma 1 (pointwise monotonicity in a): for fixed b, p>(a,b) decreases in a — worst-case lies on the left boundary of the feasible region.
  • Lemma 2 (boundary monotonicity in b): along the boundary a = b + δ0 (with δ0 = S10 − S01 − a0), p′>(b) is either increasing, constant, or decreasing in b depending on δ0, so the worst-case is at a single boundary corner.
  • Proposition: for integer δ0 ≥ 2 (typical nontrivial cases) the supremum p-value over the consistent region is attained at an explicit (a, b) given by simple min formulas (top/right intersection of the box and the consistency line). For δ0 in {0,1} the test has limiting behaviors (cannot reject at conventional α when δ0 = 0 or 1).

• Computational consequences:

  • No integer programming or combinatorial search required — the worst-case null reduces to a single Binomial tail evaluation.
  • Inverting the one-sided tests over a0 by binary search produces a prediction set for A1 in O(log S) Binomial-tail evaluations; do the mirror for A0 and combine with Bonferroni (Rigdon & Hudgens 2015) to get an ATE confidence set at the same cost.
  • A continuity-corrected Gaussian approximation gives closed-form endpoints and a closed-form ATE interval for large S.

• Extensions:

  • Sensitivity analysis: the same corner-form argument extends to matched observational studies under Rosenbaum’s Γ model (hidden bias); the method gives adjusted p-values, closed-form Hodges–Lehmann bounds, expanded CIs.
  • Design sensitivity: derives a simple formula indicating the Γ threshold beyond which no matter how large S is, the null cannot be rejected — useful to assess whether an observational study can, in principle, provide evidence.

• Comparison with prior work:

  • Improves computational practicality over prior stratified/paired exact search approaches (avoids the integer-programming or pruned searches in Li et al., Zhang, Rigdon & Hudgens’ stratified suggestions).
  • Matches earlier unstratified/monotonicity results but removes monotonicity in the paired case and provides sensitivity analysis.

Data & Methods

• Data setup:

  • 2S units in S matched pairs; one unit per pair is treated (randomized or assumed equal selection probability under strong ignorability).
  • Binary potential outcomes rCsi, rTsi; observed outcomes Rsi; treatment effects τsi ∈ {−1,0,1}.
  • Counts Sjk = number of pairs with treated outcome = j and control outcome = k (j,k ∈ {0,1}).

• Test construction:

  • For a composite null H0: A1 ≤ a0, derive the consistency region for (m+0, m+1) subject to box constraints determined by Sjk and the linear constraint m+0 − m+1 ≥ δ0 (δ0 = S10 − S01 − a0).
  • Define p>(a,b) = Pr[Binomial(a+b, 1/2) ≥ a]. Reject H0 only if sup{p>(a,b) : (a,b) consistent} ≤ α.
  • Use Lemmas 1–2 to reduce the sup to a single boundary corner (explicit formulas (5)/(6) in the paper), so the sup is a single Binomial tail.

• Inversion and combining:

  • Invert one-sided tests across candidate a0 using binary search (log S steps) to produce a prediction set for A1; repeat for A0; combine by Bonferroni to obtain a (1 − α) confidence set for ATE.
  • Provide continuity-corrected Normal approximations for endpoints when S is large.

• Sensitivity analysis:

  • Replace the within-pair 1/2 assignment probability with Rosenbaum Γ-weighted probabilities; the same corner identification gives adjusted worst-case p-values and expanded intervals.
  • From this derive a closed-form design sensitivity (Γ*), the threshold of bias beyond which the study cannot reject the null asymptotically.

Implications for AI Economics

• Exact, robust inference for paired binary outcomes at scale:

  • Many AI-economics and experimentation settings have binary outcomes (click, conversion, retention) and either paired designs (user matching, blocking) or matched observational comparisons. This method gives exact inference without requiring monotonicity (treatment may harm some units), which is often unrealistic in practice.

• Computationally practical for industrial-scale experiments:

  • O(log S) Binomial-tail work and closed-form corner formulas mean the procedure is trivial to implement and scale (no integer programming or exhaustive search), making it suitable for production A/B testing pipelines at large user volumes.

• Transparent sensitivity analysis for observational studies:

  • The Rosenbaum Γ extension gives straightforward adjusted p-values and intervals that quantify robustness to hidden confounding — valuable when interpreting causal claims from matched observational analyses (e.g., feature rollouts with nonrandom selection, policy effects).

• Design & evaluation guidance:

  • The design sensitivity formula lets researchers and practitioners assess whether a proposed matched observational study can ever provide evidence against the null given plausible magnitudes of hidden bias — analogous to power analysis but for sensitivity to unobserved confounding.
  • The randomization-motivated point estimate matching McNemar’s formula connects to commonly used estimators, facilitating adoption and interpretability.

• Practical recipe (high level):

• Compute Sjk from observed treated/control outcomes in pairs.
• For a candidate a0, compute δ0 = S10 − S01 − a0 and the corner (a, b) via the paper’s min formulas.
• Evaluate p>(a, b) = Binomial-tail( a + b, 1/2, ≥ a*). Use binary search over a0 to invert and get A1 prediction set.
• Mirror for A0 and combine via Bonferroni to get ATE confidence set.
• If observational, repeat under Rosenbaum Γ to get sensitivity-adjusted results and compute design sensitivity.

Overall, the paper provides a concise, exact, and computationally efficient toolkit for matched-pair randomization inference with binary outcomes, with direct applicability to large-scale experimentation and observational causal analyses commonly encountered in AI economics.