Dependent Randomized Rounding for Budget Constrained Experimental Design

Khurram Yamin, Edward Kennedy, Bryan Wilder

Introduction

In experimental design, researchers frequently encounter a fundamental conflict between target treatment probabilities and rigid resource constraints. For instance, a public health official might wish to prioritize high-risk patients for a new vaccine based on specific propensity scores, yet they are limited by a fixed supply of doses. Standard randomization techniques, such as independent Bernoulli trials, respect the intended probabilities but often fail to meet the exact budget. Conversely, deterministic allocation methods that strictly adhere to a budget often introduce bias by distorting inclusion probabilities.

Researchers from Carnegie Mellon University have proposed a solution to this dilemma by adapting Swap Rounding—a technique from combinatorial optimization—to the domain of experimental design. This framework allows for the satisfaction of strict budget constraints while maintaining unbiased treatment effect estimates and significantly reducing estimator variance.

The Challenge of Budgeted Randomization

The primary tension in budgeted experiments lies between feasibility (staying within budget) and statistical validity (unbiased, low-variance estimation). In many real-world scenarios, such as social program allocations, resources are finite. If independent coin flips are used for treatment assignment, the total number of treated units becomes a random variable, potentially exceeding or falling short of the budget.

A common but flawed workaround is to "force" the count to match the budget—for example, by treating the $N$ individuals with the highest probabilities. However, this distorts the marginal inclusion probabilities, leading to a mis-specified design. Such distortions result in biased estimates and inflated variance when employing standard tools like the Inverse Propensity Weighted (IPW) estimator.

Methodology: Swap Rounding

The proposed framework utilizes Swap Rounding to bridge the gap between optimization and inference. Originally developed for submodular optimization, swap rounding iteratively pairs units with fractional treatment probabilities and "swaps" probability mass between them until each unit is assigned a value of 0 or 1.

Structured Dependence and Negative Correlation

Unlike independent randomization, swap rounding is inherently dependent. When the algorithm increases the treatment probability for one individual in a pair, it must proportionally decrease it for the other to maintain the total sum. This process induces negative correlation between assignments. The authors demonstrate three critical properties of this approach:

  1. Preservation of Marginals: The expected probability of any individual being treated remains exactly as intended by the researcher.
  2. Martingale Property: The sequence of partial estimators during the rounding process forms a martingale, ensuring the final estimator remains unbiased.
  3. Variance Reduction: Due to the induced negative correlation, the variance of the IPW estimator is guaranteed to be lower than or equal to the variance under independent randomization.

Covariate-Ordered Swapping

To further enhance precision, the authors introduce Covariate-Ordered Swap Rounding. By solving a version of the Traveling Salesperson Problem (TSP) to order units based on covariate similarity, the algorithm ensures that swaps occur between similar individuals. This mimics the benefits of "matching" in causal inference, leading to even greater variance reduction.

Experimental Results

The framework was evaluated across three distinct environments: synthetic simulations, the Infant Health and Development Program (IDHP) dataset, and a public housing dataset from Allegheny County. In all experimental settings, the swap rounding method successfully met the treatment budget exactly ($ \sum A_i = B $). Furthermore, the method demonstrated superior precision compared to existing benchmarks.

Empirical variance of treatment effect estimators across sample sizes for uniform p-value distributions.

As shown in the synthetic trials, Covariate-Matched Swap Rounding consistently achieved the lowest empirical variance. It outperformed standard IPW, Re-randomization, and even biased "Self-Normalized" IPW estimators across various sample sizes and probability distributions.

Empirical variance comparison for covariate-based p-value distributions, highlighting the efficiency of Covariate Matched Swap.

On real-world datasets, the swap rounding approach remained competitive with, and often superior to, biased methodologies while preserving the gold standard of unbiasedness. The variance reduction is so substantial in small samples that the authors suggest using this technique even when budget constraints aren't strictly required, simply to improve the precision of the data.

Conclusion and Future Work

The integration of discrete optimization techniques into statistical inference provides a powerful tool for experimental design. By leveraging structured dependence, researchers can achieve a "free lunch" of variance reduction while adhering to strict feasibility constraints.

Future research directions include addressing the computational complexity of covariate ordering for massive datasets and extending these variance reduction proofs to more complex, non-linear, or doubly robust estimators. Additionally, exploring the implications of these methods outside of the "superpopulation" assumption remains an open area for investigation.

Summary updated

Abstract

Policymakers in resource-constrained settings require experimental designs that satisfy strict budget limits while ensuring precise estimation of treatment effects. We propose a framework that applies a dependent randomized rounding procedure to convert assignment probabilities into binary treatment decisions. Our proposed solution preserves the marginal treatment probabilities while inducing negative correlations among assignments, leading to improved estimator precision through variance reduction. We establish theoretical guarantees for the inverse propensity weighted and general linear estimators, and demonstrate through empirical studies that our approach yields efficient and accurate inference under fixed budget constraints.
BibTeX
@inproceedings{yamin2025dependent,
  author = {Khurram Yamin and Edward Kennedy and Bryan Wilder},
  title = {{Dependent Randomized Rounding for Budget Constrained Experimental Design}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2025},
  url = {https://openreview.net/forum?id=i0UuWNtrf8},
}
Figure