Help
Cart
Skip main navigation

Available Issues

April 16, 2013 - May 25, 2026

Available Issues

April 16, 2013 - May 25, 2026

Algorithms and Complexities of Matching Variants in Covariate Balancing

Published Online:26 Apr 2022https://doi.org/10.1287/opre.2022.2286

References

  • Ágoston KC, Biró P, Szántó R (2018) Stable project allocation under distributional constraints. Oper. Res. Perspect. 5:59–68.Crossref, Google Scholar
  • Ahuja RK, Orlin JB, Magnanti TL (1993) Network Flows: Theory, Algorithms, and Applications. (Prentice-Hall, Hoboken, NJ).Google Scholar
  • Ashlagi I, Saberi A, Shameli A (2020) Assignment mechanisms under distributional constraints. Oper. Res. 68(2):467–479. Abstract, Google Scholar
  • Bei X, Liu S, Poon CK, Wang H (2020) Candidate selections with proportional fairness constraints. Proc. 19th Internat. Conf. Autonomous Agents and MultiAgent Systems, 150–158.Google Scholar
  • Bennett M, Vielma JP, Zubizarreta JR (2020) Building representative matched samples with multi-valued treatments in large observational studies. J. Comput. Graph. Stat. 29(4):744–757.Crossref, Google Scholar
  • Brookhart MA, Schneeweiss S, Rothman KJ, Glynn RJ, Avorn J, Stürmer T (2006) Variable selection for propensity score models. Am. J. Epidemiol. 163(12):1149–1156.Crossref, Google Scholar
  • Busaker R, Gowen PJ (1961) A procedure for determining minimal-cost network flow patterns. Technical report, ORO Technical Report 15, Operational Research Office, John Hopkins University.Google Scholar
  • Dutta S, Jacobson SH, Sauppe JJ (2017) Identifying NCAA Tournament upsets using balance optimization subset selection. J. Quant. Anal. Sports. 13(2):79–93.Crossref, Google Scholar
  • Edmonds J, Karp RM (1972) Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2):248–264.Crossref, Google Scholar
  • Ho DE, Imai K, King G, Stuart EA (2007) Matching as nonparametric preprocessing for reducing model dependence in parametric causal inference. Polit. Anal. 15(3):199–236. Crossref, Google Scholar
  • Hochbaum DS, Rao X, Sauppe J (2022) Network flow methods for the minimum covariate imbalance problem. Eur. J. Oper. Res. 300(3):827–836.Crossref, Google Scholar
  • Imbens GW (2004) Nonparametric estimation of average treatment effects under exogeneity: A review. Rev. Econ. Stat. 86(1):4–29.Crossref, Google Scholar
  • Iri M (1960) A new method of solving transportation-network problems. J. Oper. Res. Soc. Japan. 3(1):2–87.Google Scholar
  • Jewell WS (1958) Optimal flow through networks. Oper. Res. 6:633–633.Google Scholar
  • Kannan R (1983) Improved algorithms for integer programming and related lattice problems. Johnson DS, Fagin R, Fredman ML, Harel D, Karp RM, Lynch NA, Papadimitriou CH, Rivest RL, Ruzzo WL, Seiferas JI, eds., Proc. 15th Annual ACM Sympos. on Theory of Comput., 25-27 April, 1983, Boston, Massachusetts, USA, 193–206 (ACM), http://dx.doi.org/10.1145/800061.808749.Google Scholar
  • Karmakar B, Small D, Rosenbaum P (2019) Using approximation algorithms to build evidence factors and related designs for observational studies. J. Comput. Graph. Statist. 28(3):698–709.Crossref, Google Scholar
  • King G, Lucas C, Nielsen RA (2017) The balance-sample size frontier in matching methods for causal inference. Am. J. Pol. Sci. 61:473–489. Crossref, Google Scholar
  • Kwon HY (2018) New developments in causal inference using balance optimization subset selection. Ph.D. thesis, University of Illinois at Urbana-Champaign.Google Scholar
  • Kwon HY, Sauppe JJ, Jacobson SH (2019a) Bias in balance optimization subset selection: Exploration through examples. J. Oper. Res. Soc. 70(1):67–80.Crossref, Google Scholar
  • Kwon HY, Sauppe JJ, Jacobson SH (2019b) Treatment effect decomposition and bootstrap hypothesis testing in observational studies. Annals of Data Science 6(3):491–511.Crossref, Google Scholar
  • Kwon HY, Sauppe JJ, Jacobson SH (2020) Duality in balance optimization subset selection. Ann. Oper. Res. 289:277–289.Crossref, Google Scholar
  • Lenstra Jr. HW (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538–548.Link, Google Scholar
  • Morgan SL, Harding DJ (2006) Matching estimators of causal effects: Prospects and pitfalls in theory and practice. Sociol. Methods Res. 35(1):3–60.Crossref, Google Scholar
  • Mulmuley K, Vazirani U, Vazirani V (1987) Matching is as easy as matrix inversion. Combinatorica. 7(1):105–113.Crossref, Google Scholar
  • Nguyen T, Vohra R (2019) Stable matching with proportionality constraints. Oper. Res. 67(6):1503–1519.Link, Google Scholar
  • Nguyen T, Nguyen H, Teytelboym A (2019) Stability in matching markets with complex constraints. Management Sci. 67(12):7291–7950.Google Scholar
  • Nikolaev AG, Jacobson SH, Cho WKT, Sauppe JJ, Sewell EC (2013) Balance optimization subset selection (boss): An alternative approach for causal inference with observational data. Oper. Res. 61(2):398–412.Link, Google Scholar
  • Papadimitriou CH, Yannakakis M (1982) The complexity of restricted spanning tree problems. J. ACM. 29(2):285–309.Crossref, Google Scholar
  • Pimentel SD, Kelz RR, Silber JH, Rosenbaum PR (2015) Large, sparse optimal matching with refined covariate balance in an observational study of the health outcomes produced by new surgeons. J. Am. Stat. Assoc. 110 (510):515–527. Google Scholar
  • Rosenbaum PR (2002) Overt Bias in Observational Studies. (Springer, New York), 71–104.Crossref, Google Scholar
  • Rosenbaum PR (2012) Optimal matching of an optimally chosen subset in observational studies. J. Comput. Graph. Statist. 21:57–71. Crossref, Google Scholar
  • Rosenbaum PR (2020) Modern algorithms for matching in observational studies. Annu. Rev. Stat. Appl. 7:143–176.Crossref, Google Scholar
  • Rosenbaum PR, Ross RN, Silber JH (2007) Minimum distance matched sampling with fine balance in an observational study of treatment for ovarian cancer. J. Am. Stat. Assoc. 102(477):75–83.Crossref, Google Scholar
  • Rubin DB, Stuart EA (2006) Affinely invariant matching methods with discriminant mixtures of proportional ellipsoidally symmetric distributions. Ann. Statist. 34(4):1814–1826.Crossref, Google Scholar
  • Sauppe JJ (2015) Balance optimization subset selection: A framework for causal inference with observational data. Ph.D. thesis, University of Illinois at Urbana-Champaign.Google Scholar
  • Sauppe JJ, Jacobson SH (2017) The role of covariate balance in observational studies. Naval Res. Logist. 64(4):323–344.Crossref, Google Scholar
  • Sauppe JJ, Jacobson SH, Sewell EC (2014) Complexity and approximation results for the balance optimization subset selection model for causal inference in observational studies. INFORMS J. Comput. 26(3):547–566.Link, Google Scholar
  • Sharma D, Willy C, Bischoff J (2020) Optimal subset selection for causal inference using machine learning ensembles and particle swarm optimization. Complex Intel. Sys. 7:41–59.Crossref, Google Scholar
  • Stuart EA (2010) Matching methods for causal inference: A review and a look forward. Statistical science: a review journal of the Institute of Mathematical Statistics 25(1):1. http://dx.doi.org/10.1214/09-STS313.Crossref, Google Scholar
  • Tam Cho WK, Sauppe JJ, Nikolaev AG, Jacobson SH, Sewell EC (2013) An optimization approach for making causal inferences. Stat. Neerl. 67(2):211–226. Crossref, Google Scholar
  • Tomizawa N (1971) On some techniques useful for solution of transportation network problems. Networks 1(2):173–194.Crossref, Google Scholar
  • Visconti G, Zubizarreta JR (2018) Handling limited overlap in observational studies with cardinality matching. Observational Studies. 4:217–249.Crossref, Google Scholar
  • Yahiro K, Zhang Y, Barrot N, Yokoo M (2020) Strategyproof and fair matching mechanism for ratio constraints. Auton. Agent. Multi Agent Syst. 34(1):1–29.Crossref, Google Scholar
  • Yang D, Small DS, Silber JH, Rosenbaum PR (2012) Optimal matching with minimal deviation from fine balance in a study of obesity and surgical outcomes. Biometrics 68(2):628–636.Crossref, Google Scholar
  • Zubizarreta JR (2012) Using mixed integer programming for matching in an observational study of kidney failure after surgery. J. Am. Stat. Assoc. 107(500):1360–1371.Crossref, Google Scholar
  • Zubizarreta JR, Paredes RD, Rosenbaum PR (2014) Matching for balance, pairing for heterogeneity in an observational study of the effectiveness of for-profit and not-for-profit high schools in Chile. Ann. Appl. Stat. 8:204–231.Crossref, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree