Network flow methods for the minimum covariate imbalance problem

Dorit S. Hochbaum, Xu Rao and Jason Sauppe

European Journal of Operational Research, 2022, vol. 300, issue 3, 827-836

Abstract: In an observational study, one is given disjoint samples of treatment units and control (untreated) units, and the goal is to compare outcomes between the two samples in order to estimate a treatment effect. A complication is that the treatment and control units often differ on important pre-treatment attributes, and these differences, referred to as covariate imbalance, can bias the estimate. One method to correct for covariate imbalance is to select a subset of the control sample that has minimum imbalance with respect to the treatment sample, and then use this control subset for estimating the treatment effect. While this optimization problem is NP-hard in general, certain special cases can be solved efficiently. Specifically, the variant of this optimization problem with one covariate is easy to solve, the variant with three or more covariates is NP-hard, and the variant with two covariates is solvable in polynomial time. We present several network flow formulations for the problem of minimizing imbalance on two nominal covariates. First, we present a minimum cost network flow formulation for solving the problem with the constraint that the control subset must have the same size as the treatment sample. We then derive an improved maximum flow formulation. For alternate size restrictions on the control subset, we use a proportional imbalance objective which leads to non-integral supplies and demands in the preceding network flow formulations. We then derive an alternate minimum cost network flow formulation that ensures integrality and solves the proportional imbalance problem in polynomial time.

Keywords: Networks; Causal inference; Covariate imbalance (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721008924
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:300:y:2022:i:3:p:827-836

DOI: 10.1016/j.ejor.2021.10.041

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().