Pith. sign in

REVIEW 3 major objections 5 minor 24 references

Dependent Randomized Rounding for Budget Constrained Experimental Design

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Swap rounding can fix the number of treated units while preserving each unit's planned probability and cutting estimator variance.

desk verdict Worth a look for the idea, but the main algorithm as printed does not preserve marginals and the variance analysis is incomplete; the paper needs major repair. read the letter →

arxiv 2506.12677 v1 pith:2RN2VO6W submitted 2025-06-15 stat.ML cs.LG

Khurram Yamin , Edward Kennedy , Bryan Wilder This is my paper · ORCID
classification stat.MLcs.LG MSC 62K0562D05
keywords swaproundingbudget-constrainedexperimentaldesigninverseprobabilityweightingtreatmenteffectestimationnegativecorrelationvariancereductionexactbudgetconstraintmartingale
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that a combinatorial optimization technique called swap rounding can convert fractional treatment probabilities into binary treatment assignments that use exactly B treatments, preserve every unit's original probability of treatment, and induce negative correlations between assignments. If correct, this would remove a long-standing tension in budget-constrained experiments: an inverse-probability-weighted estimator based on the rounded assignments would remain unbiased and would have variance no larger than the same estimator under independent Bernoulli randomization. The authors also claim the same guarantees for any estimator linear in the treatment indicators, and they propose a covariate-ordered variant that pairs similar units to strengthen the variance reduction. A careful reader would care because public-health and social-policy trials often have a fixed number of treatments available and currently must choose between violating the budget or distorting the planned assignment probabilities.

What carries the argument

The load-bearing object is the swap rounding algorithm, which repeatedly chooses a pair of fractional probabilities, transfers probability mass between them in a randomized way, and continues until every entry is 0 or 1. The key identity is the pairwise covariance induced by the rounding: for two entries involved in a swap, Cov(A_i, A_j) is negative, equal to $-p_i p_j$ when $p_i + p_j \leq 1$ and to $-(1-p_i)(1-p_j)$ when $p_i + p_j > 1$, and this negativity is what converts the coupling into variance reduction. The martingale argument runs through the intermediate fractional vectors $p^{(t)}$: if each step preserves conditional expectations of the entries, then the IPW estimator at the final rounded assignment has the same expectation as at the start, and its variance decomposition contains only nonpositive covariance terms.

What would settle it

Run one documented swap step of Algorithm 1 on the pair $p = (0.4, 0.8)$ using the printed Case 2 probability: the probability of rounding $p_i$ up is $(1 - 0.4)/(2 - 0.4 - 0.8) = 0.75$, so the expected value of $p_i$ after the step is $0.75 \cdot 1 + 0.25 \cdot 0.2 = 0.8$, not the required $0.4$; observing this mismatch in simulation would settle that the marginal-preservation and martingale conditions fail for the algorithm as printed.

Watch

Extended reading notes

Core claim

The central claim is that dependent randomized rounding via swap rounding gives a joint distribution over binary treatment vectors with three simultaneous properties: exact feasibility, because the sum of the assignments is always exactly B; marginal preservation, because Pr(A_i = 1) = p_i for every unit; and negative covariance between assignments. The paper shows that under these properties the IPW estimator for the average treatment effect is unbiased, has variance no larger than the IPW estimator under independent Bernoulli assignment, and can be paired with a consistent variance estimator and a martingale central limit theorem to produce asymptotically valid confidence intervals. The same argument is extended to any estimator linear in the treatment assignments with nonnegative coefficients, and a covariate-ordered swap variant is claimed to reduce variance further when outcomes vary smoothly with covariates.

Load-bearing premise

The load-bearing premise is that every swap step leaves each unit's expected probability unchanged; if a printed update probability violates this marginal-preservation condition, the claimed unbiasedness and variance reduction do not follow from the algorithm as written.

Editorial extensions

If this is right

  • An experimenter can fix the number of treated units at B while keeping each unit's planned treatment probability exactly as designed, so the hard budget constraint no longer forces a trade-off against unbiasedness.
  • Because assignments are negatively correlated, the IPW estimate of the average treatment effect has variance no larger than independent Bernoulli assignment, meaning the exact-budget requirement does not cost precision.
  • Any estimator linear in the treatment indicators, not just IPW, inherits the same unbiasedness and variance-reduction guarantee under the stated conditions.
  • Pairing swaps between covariate-similar units can strengthen the variance reduction when outcomes and effective weights vary smoothly with covariates.
  • A martingale central limit theorem, together with the proposed variance estimator, gives confidence intervals for the average treatment effect that are asymptotically valid under the superpopulation assumption.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The negative-correlation mechanism is broader than swap rounding itself: any randomized assignment scheme that preserves marginals and induces nonpositive pairwise covariances would dominate independent Bernoulli assignment in variance, so the paper's argument points toward a general design principle for dependent randomization.
  • The covariate-ordered variant is one instance of a larger family of pair-selection rules; choosing pairs to minimize within-pair differences in the effective weight M_i could be optimized inside the same swap framework, with direct connections to rerandomization and matched-pair designs.
  • A natural empirical test beyond the paper's experiments is to repeatedly re-randomize a real trial dataset with known propensity scores, comparing the empirical variance and confidence-interval coverage of the swap-rounded estimator against independent Bernoulli draws.
  • The paper's guarantees depend only on the marginal-preservation and nonpositive-covariance structure, which suggests the same rounding approach could be combined with stratification or rerandomization to satisfy resource limits and covariate-balance goals simultaneously.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes using swap rounding, in the sense of Chekuri and Vondrák, to convert a fractional assignment probability vector p (with sum B) into a binary treatment vector A with exactly B treated units. It claims that the procedure preserves each marginal probability Pr(A_i = 1) = p_i, induces negative correlations between assignments, and leads to an IPW estimator that is unbiased and has variance no larger than independent Bernoulli assignment. It further claims asymptotic normality, consistent variance estimation, an extension to general linear estimators, and a covariate-ordered variant, supported by synthetic and semi-synthetic experiments. The central theoretical results are Propositions 1 and 2 and Theorem 1.

Significance. If the main claims were correct, the paper would offer a practically valuable method for enforcing exact budget constraints without sacrificing unbiasedness and with improved precision. The connection between swap rounding and budget-constrained experimental design is a useful idea, and the authors provide code and a broad empirical comparison. However, the central algorithmic guarantee as stated is false: the printed update probabilities in Algorithm 1 do not preserve marginals, so the martingale property, unbiasedness, variance reduction, and confidence-interval results do not follow from the paper's own algorithm.

major comments (3)
  1. [§3.1, Algorithm 1] The Case 2 update probability is inverted. When p_i^{(t)} + p_j^{(t)} > 1, the algorithm rounds p_i up to 1 with probability (1-p_i^{(t)})/(2-p_i^{(t)}-p_j^{(t)}), but marginal preservation requires probability (1-p_j^{(t)})/(2-p_i^{(t)}-p_j^{(t)}). For p = (0.4, 0.8), the printed rule gives E[p_i'] = 0.75*1 + 0.25*0.2 = 0.8, not 0.4. Consequently, Eq. (4) is false, the martingale argument in §4.1.2 fails, and Propositions 1 and 2, Theorem 1, and Theorem 2 do not follow for the algorithm as written. The same inverted ratio appears in Algorithm 2 in the appendix, so this is not an isolated typo; replacing the probability with (1-p_j^{(t)})/(2-p_i^{(t)}-p_j^{(t)}) would restore the intended identity, but that correction must be propagated through the proofs.
  2. [§4.1.3, Eq. (7)] The variance decomposition sums covariance terms only over S, the set of pairs that are directly swapped. The variance of a sum over all n units includes covariances for every pair of units, and Eq. (9) states a formula for ρ_{ij} for arbitrary i,j. Unless S is the set of all unordered pairs, Eq. (7) omits covariance terms, and the paper does not prove that cov(X_i, X_j) = 0 for pairs outside S. This affects Proposition 2 and the asymptotic variance used in Theorem 1, and it is inconsistent with the appendix's derivation in §10.8, which applies cov(X_i, X_j) to any pair.
  3. [§4.1.6, Proposition 3] The claimed unbiasedness and consistency of the variance estimator σ̂ are not proved. The main text states the result without proof, and the appendix derives population variance quantities but does not derive the expectation of the plug-in estimator in Eqs. (12)–(14). In particular, replacing terms such as E[Y_i(1)^2] with A_i' Y_i^2 / (p_i^0)^2 and subtracting n τ_swap^2 requires a careful argument about the joint distribution of A' and the potential outcomes under swap rounding; no such argument is given. Since Proposition 3 underpins the confidence-interval claim in Theorem 1, this is a load-bearing gap.
minor comments (5)
  1. [References] In the Introduction and references, 'V ondrák' should read 'Vondrák'.
  2. [§3.2] The sentence 'We will also that Y (0) and Y (1) are always nonnegative' is missing the verb 'assume'.
  3. [Theorem 1] The sentence beginning 'Them, the IPW estimator' should read 'Then, the IPW estimator', and the last bullet in the assumption list ends with a stray comma.
  4. [§6.3.2 and §6.4.2] The synthetic experiment text reports that Covariate Based Swap Rounding performs best, while the Housing sub-experiment reports that regular swap rounding performs best; the presentation should reconcile these statements or state explicitly that the ranking varies by setting.
  5. [Figures] The y-axis labels such as 'Empirical Variance of Uniform Distributed p-values' are awkward and should be reworded to describe the estimator variance rather than the variance of p-values.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation found; the paper's theoretical claims do not reduce to their inputs by construction, though Algorithm 1's unproved martingale condition is a correctness gap rather than a circularity.

full rationale

The paper's derivation chain is not circular. The central theoretical objects are specified independently of the conclusions: swap rounding is taken from the external reference Chekuri and Vondrák (2009), the IPW estimator is defined in Eqs. (1)-(2), the variance decomposition is given in Eq. (7), and the plug-in variance estimator is given in Eqs. (12)-(14). Proposition 1 is a direct consequence of linearity of expectation once marginal preservation holds; the paper states this preservation as a property of swap rounding (Eq. (4)) rather than as the conclusion it is trying to establish. Even if Eq. (4) is unproved or false as written, that is a soundness/completeness failure in the proof, not a circular reduction: the algorithm's update probabilities are not defined in terms of the target unbiasedness or variance-reduction claims. Proposition 2 and Theorem 2 use the negative pairwise covariance rho_ij induced by the rounding procedure to conclude variance reduction; the same rho_ij appears in the variance estimator, but using the same covariance structure for estimation and for the claimed variance is internal consistency of a plug-in estimator, not an assumption of the conclusion. The covariate-ordered result (Proposition 4) compares two pairing schemes under explicit Lipschitz and distance assumptions and follows by elementary algebra from Eq. (28); no fitted parameter is renamed as a prediction. The only self-citation is Wilder and Welle (2024), used as a public-housing data source in the experiments; it is not load-bearing for any theorem. The paper's main substantive risk is therefore a potential error in Algorithm 1's Case 2 probability, which would break the martingale condition in Eq. (4); that is a correctness concern, not a circularity. No uniqueness theorem is imported from the authors' prior work, no ansatz is smuggled in solely by self-citation, and no known empirical pattern is merely relabeled. Accordingly, the circularity score is 1, reflecting only a minor, non-load-bearing self-citation and the reviewer's explicit statement that the derivation is not circular.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central claim rests on standard causal assumptions plus two non-verifiable premises: the swap algorithm's marginal preservation, which is false as printed, and the variance decomposition limited to directly swapped pairs, which omits real covariance terms.

assumptions (7)
  • domain assumption Consistency and ignorability: Y = Y(A) and (Y(1),Y(0)) independent of A
    Section 3.2 states these standard RCT assumptions, required for IPW to identify the ATE.
  • domain assumption Positivity: 0 < p_i < 1 and 0 < p(V_i) < 1
    Section 3.2 requires positivity to define inverse probability weights.
  • domain assumption Nonnegative potential outcomes (achievable by translation)
    Section 3.2 assumes Y(0),Y(1) are nonnegative so that covariance terms in the variance analysis are negative.
  • domain assumption Superpopulation iid draws of (Y(0),Y(1),V)
    Section 3.2 introduces this assumption for the CLT and the consistency of the variance estimator (Proposition 3, Theorem 1).
  • ad hoc to paper Swap rounding preserves marginals: E[p_i^{(t)}|p_i^{(t-1)}] = p_i^{(t-1)}
    Equation (4) asserts this property, but Algorithm 1's Case 2 probabilities do not satisfy it; the printed update changes the marginal expectation.
  • domain assumption Lower bound on quadratic variation and bounded second moments in Theorem 1
    Listed as conditions for the martingale central limit theorem, not verified in practice.
  • ad hoc to paper Bi-Lipschitz effective weight M(·) and pair-distance bounds in Section 5
    Assumptions (A1)-(A2) in the covariate-ordered proof are stylized and not verified in data.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dependent Randomized Rounding for Budget Constrained Experimental Design." pith.science (2026). https://pith.science/paper/2RN2VO6W

@misc{pith2026250612677,
  author       = {Pith},
  title        = {Pith review of: Dependent Randomized Rounding for Budget Constrained Experimental Design},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2RN2VO6W}},
  note         = {Machine review of arXiv:2506.12677}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2506.12677 by the authors.

Figure 1
Figure 1. Synthetic Experiment with p (0) ∼ Uniform (0.01,0.99). Mean empirical variance with 95 % CI. 50 100 250 500 1000 5000 Sample Size (n) 0.0 0.1 0.2 0.3 0.4 0.5 Empirical Variance of Gaussian p-values Standard IPW Swap Rounding Covariate Matched Swap Random Assignment Limited Bernoulli Re-randomization Self-Normalized IPW [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Synthetic Experiment with p (0) ∼ N (.5, .25) 50 100 250 500 1000 5000 Sample Size (n) 0.0 0.1 0.2 0.3 0.4 0.5 0.6 Empirical Variance of Covariate Based p-values Standard IPW Swap Rounding Covariate Matched Swap Random Assignment Limited Bernoulli Re-randomization Self-Normalized IPW [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Synthetic Experiment where [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Semi-Synthetic Experiment IDHP dataset 6.4.2 Housing Dataset In this setting, we use data provided by the Allegheny County Department of Human Services. The dataset (3163 individuals) was introduced by Wilder and Welle [2024] and contains individuals eligible for publi…
Figure 5
Figure 5. Figure 5: Semi-Synthetic Experiment Housing Dataset [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 23 canonical work pages

  1. [1]

    A. A. Ageev and M. Sviridenko. Approximation algorithms for maximization of submodular functions. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pages 793--802, 2004

    work page 2004

  2. [2]

    Comparisons between conditional poisson sampling and pareto πps sampling designs

    Nibia Aires. Comparisons between conditional poisson sampling and pareto πps sampling designs. Journal of Statistical Planning and Inference, 88 0 (1): 0 133--147, 2000. ISSN 0378-3758. doi:https://doi.org/10.1016/S0378-3758(99)00205-0. URL https://www.sciencedirect.com/science/article/pii/S0378375899002050

    work page doi:10.1016/s0378-3758(99)00205-0

  3. [3]

    Athey and G

    S. Athey and G. W. Imbens. The state of applied econometrics: Causality and policy evaluation. Journal of Economic Perspectives, 31 0 (2): 0 3--32, 2017

    work page 2017

  4. [4]

    Maximally balanced sampling in randomized experiments

    R Branson and Q Miao. Maximally balanced sampling in randomized experiments. Journal of Statistical Planning and Inference, 205: 0 1--10, 2019

    work page 2019

  5. [5]

    Selective trials: A principal-agent approach to randomized controlled experiments

    Sylvain Chassang, Gerard Padró I Miquel, and Erik Snowberg. Selective trials: A principal-agent approach to randomized controlled experiments. American Economic Review, 102 0 (4): 0 1279–1309, June 2012. doi:10.1257/aer.102.4.1279. URL https://www.aeaweb.org/articles?id=10.1257/aer.102.4.1279

    work page doi:10.1257/aer.102.4.1279 2012

  6. [6]

    Dependent Randomized Rounding for Matroid Polytopes and Applications

    Chandra Chekuri and Jan Vondr \' a k. Randomized pipage rounding for matroid polytopes and applications. CoRR, abs/0909.4348, 2009. URL http://arxiv.org/abs/0909.4348

    work page Pith review arXiv 2009

  7. [7]

    Sampling Techniques

    William G Cochran. Sampling Techniques. John Wiley & Sons, 1977

    work page 1977

  8. [8]

    Jyotishka Datta and Nicholas G. Polson. Inverse probability weighting: from survey sampling to evidence estimation. Working paper, Department of Statistics, Virginia Tech \\ and \\ Booth School of Business, University of Chicago, 2011. Unpublished manuscript

    work page 2011

Show all 24 references
  1. [9]

    Comparisons of methods for generating conditional poisson samples and sampford samples

    Anton Grafstr \"o m. Comparisons of methods for generating conditional poisson samples and sampford samples. 2005. URL https://api.semanticscholar.org/CorpusID:56873261

    2005

  2. [10]

    Ruth T. Gross. Infant health and development program (ihdp): Enhancing the outcomes of low birth weight, premature infants in the united states, 1985--1988. Inter-university Consortium for Political and Social Research, 2024. URL https://doi.org/10.3886/ICPSR09795.v2. Dataset,...

    1985 doi

  3. [11]

    Asymptotic theory of rejective sampling with varying probabilities

    J H \'a jek. Asymptotic theory of rejective sampling with varying probabilities. The Annals of Mathematical Statistics, pages 1006--1018, 1964

    1964

  4. [12]

    G. W. Imbens and D. B. Rubin. Causal Inference in Statistics, Social, and Biomedical Sciences. Cambridge University Press, 2015

    2015

  5. [13]

    Isaki and W

    C. Isaki and W. A. Fuller. Estimation for finite population sampling. Journal of the American Statistical Association, 79 0 (387): 0 137--145, 1984

    1984

  6. [14]

    Johnson and Laurence A

    David S. Johnson and Laurence A. McGeoch. The traveling salesman problem: A case study in local optimization. In Local Search in Combinatorial Optimization, pages 215--310. Princeton University Press, 1997

    1997

  7. [15]

    Incorporating preferences into treatment assignment problems, 2023

    Daido Kido. Incorporating preferences into treatment assignment problems, 2023. URL https://arxiv.org/abs/2311.08963

    2023 arXiv

  8. [16]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220 0 (4598): 0 671--680, 1983

    1983

  9. [17]

    X. Li, P. Ding, and D. B. Rubin. Rerandomization in experiments: A review. Annual Review of Statistics and Its Application, 5: 0 1--19, 2018

    2018

  10. [18]

    On inverse probability-weighted estimators in the presence of interference

    Lan Liu, Michael G Hudgens, and Sara Becker-Dreps. On inverse probability-weighted estimators in the presence of interference. Biometrika, 103 0 (4): 0 829--842, 2016. doi:10.1093/biomet/asw047

    2016 doi

  11. [19]

    D. L. Morgan and D. B. Rubin. Rerandomization to improve covariate balance in experiments. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 74 0 (4): 0 515--532, 2012

    2012

  12. [20]

    Incorporating ethics and welfare into randomized experiments

    Yusuke Narita. Incorporating ethics and welfare into randomized experiments. Proceedings of the National Academy of Sciences, 118 0 (1): 0 e2008740118, 2021. doi:10.1073/pnas.2008740118. URL https://www.pnas.org/doi/abs/10.1073/pnas.2008740118

    2021 doi

  13. [21]

    J. Neyman. On the problem of the most efficient allocation of units in stratified sampling. Journal of the Royal Statistical Society, 97: 0 544--557, 1934

    1934

  14. [22]

    Srinivasan

    A. Srinivasan. Distributions on level-sets with applications to approximation algorithms. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 588--597, 2001

    2001

  15. [23]

    Elizabeth A. Stuart. Matching methods for causal inference: A review and a look forward. Statistical Science, 25 0 (1): 0 1--21, 2010

    2010

  16. [24]

    Learning treatment effects while treating those in need, 2024

    Bryan Wilder and Pim Welle. Learning treatment effects while treating those in need, 2024. URL https://arxiv.org/abs/2407.07596

    2024 arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.