Optimal Matching with Minimal Deviation from Fine Balance in a Study of Obesity and Surgical Outcomes

Dan Yang, Dylan S. Small, Jeffrey H. Silber, Paul R. Rosenbaum

Research output: Contribution to journalArticle

38 Citations (Scopus)

Abstract

In multivariate matching, fine balance constrains the marginal distributions of a nominal variable in treated and matched control groups to be identical without constraining who is matched to whom. In this way, a fine balance constraint can balance a nominal variable with many levels while focusing efforts on other more important variables when pairing individuals to minimize the total covariate distance within pairs. Fine balance is not always possible; that is, it is a constraint on an optimization problem, but the constraint is not always feasible. We propose a new algorithm that returns a minimum distance finely balanced match when one is feasible, and otherwise minimizes the total distance among all matched samples that minimize the deviation from fine balance. Perhaps we can come very close to fine balance when fine balance is not attainable; moreover, in any event, because our algorithm is guaranteed to come as close as possible to fine balance, the investigator may perform one match, and on that basis judge whether the best attainable balance is adequate or not. We also show how to incorporate an additional constraint. The algorithm is implemented in two similar ways, first as an optimal assignment problem with an augmented distance matrix, second as a minimum cost flow problem in a network. The case of knee surgery in the Obesity and Surgical Outcomes Study motivated the development of this algorithm and is used as an illustration. In that example, 2 of 47 hospitals had too few nonobese patients to permit fine balance for the nominal variable with 47 levels representing the hospital, but our new algorithm came very close to fine balance. Moreover, in that example, there was a shortage of nonobese diabetic patients, and incorporation of an additional constraint forced the match to include all of these nonobese diabetic patients, thereby coming as close as possible to balance for this important but recalcitrant covariate.

Original languageEnglish (US)
Pages (from-to)628-636
Number of pages9
JournalBiometrics
Volume68
Issue number2
DOIs
StatePublished - Jun 1 2012

Fingerprint

Obesity
balance studies
obesity
Deviation
Categorical or nominal
Minimise
Covariates
Augmented matrix
Minimum Cost Flow
Distance Matrix
knees
system optimization
Shortage
Assignment Problem
Minimum Distance
Marginal Distribution
Pairing
Surgery
Knee
Research Design

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Biochemistry, Genetics and Molecular Biology(all)
  • Immunology and Microbiology(all)
  • Agricultural and Biological Sciences(all)
  • Applied Mathematics

Keywords

  • Assignment algorithm
  • Fine balance
  • Matching
  • Network optimization
  • Observational study
  • Optimal matching

Cite this

Yang, Dan ; Small, Dylan S. ; Silber, Jeffrey H. ; Rosenbaum, Paul R. / Optimal Matching with Minimal Deviation from Fine Balance in a Study of Obesity and Surgical Outcomes. In: Biometrics. 2012 ; Vol. 68, No. 2. pp. 628-636.
@article{28ac64fe570442d28541cd7c55193f5f,
title = "Optimal Matching with Minimal Deviation from Fine Balance in a Study of Obesity and Surgical Outcomes",
abstract = "In multivariate matching, fine balance constrains the marginal distributions of a nominal variable in treated and matched control groups to be identical without constraining who is matched to whom. In this way, a fine balance constraint can balance a nominal variable with many levels while focusing efforts on other more important variables when pairing individuals to minimize the total covariate distance within pairs. Fine balance is not always possible; that is, it is a constraint on an optimization problem, but the constraint is not always feasible. We propose a new algorithm that returns a minimum distance finely balanced match when one is feasible, and otherwise minimizes the total distance among all matched samples that minimize the deviation from fine balance. Perhaps we can come very close to fine balance when fine balance is not attainable; moreover, in any event, because our algorithm is guaranteed to come as close as possible to fine balance, the investigator may perform one match, and on that basis judge whether the best attainable balance is adequate or not. We also show how to incorporate an additional constraint. The algorithm is implemented in two similar ways, first as an optimal assignment problem with an augmented distance matrix, second as a minimum cost flow problem in a network. The case of knee surgery in the Obesity and Surgical Outcomes Study motivated the development of this algorithm and is used as an illustration. In that example, 2 of 47 hospitals had too few nonobese patients to permit fine balance for the nominal variable with 47 levels representing the hospital, but our new algorithm came very close to fine balance. Moreover, in that example, there was a shortage of nonobese diabetic patients, and incorporation of an additional constraint forced the match to include all of these nonobese diabetic patients, thereby coming as close as possible to balance for this important but recalcitrant covariate.",
keywords = "Assignment algorithm, Fine balance, Matching, Network optimization, Observational study, Optimal matching",
author = "Dan Yang and Small, {Dylan S.} and Silber, {Jeffrey H.} and Rosenbaum, {Paul R.}",
year = "2012",
month = "6",
day = "1",
doi = "10.1111/j.1541-0420.2011.01691.x",
language = "English (US)",
volume = "68",
pages = "628--636",
journal = "Biometrics",
issn = "0006-341X",
publisher = "Wiley-Blackwell",
number = "2",

}

Optimal Matching with Minimal Deviation from Fine Balance in a Study of Obesity and Surgical Outcomes. / Yang, Dan; Small, Dylan S.; Silber, Jeffrey H.; Rosenbaum, Paul R.

In: Biometrics, Vol. 68, No. 2, 01.06.2012, p. 628-636.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Optimal Matching with Minimal Deviation from Fine Balance in a Study of Obesity and Surgical Outcomes

AU - Yang, Dan

AU - Small, Dylan S.

AU - Silber, Jeffrey H.

AU - Rosenbaum, Paul R.

PY - 2012/6/1

Y1 - 2012/6/1

N2 - In multivariate matching, fine balance constrains the marginal distributions of a nominal variable in treated and matched control groups to be identical without constraining who is matched to whom. In this way, a fine balance constraint can balance a nominal variable with many levels while focusing efforts on other more important variables when pairing individuals to minimize the total covariate distance within pairs. Fine balance is not always possible; that is, it is a constraint on an optimization problem, but the constraint is not always feasible. We propose a new algorithm that returns a minimum distance finely balanced match when one is feasible, and otherwise minimizes the total distance among all matched samples that minimize the deviation from fine balance. Perhaps we can come very close to fine balance when fine balance is not attainable; moreover, in any event, because our algorithm is guaranteed to come as close as possible to fine balance, the investigator may perform one match, and on that basis judge whether the best attainable balance is adequate or not. We also show how to incorporate an additional constraint. The algorithm is implemented in two similar ways, first as an optimal assignment problem with an augmented distance matrix, second as a minimum cost flow problem in a network. The case of knee surgery in the Obesity and Surgical Outcomes Study motivated the development of this algorithm and is used as an illustration. In that example, 2 of 47 hospitals had too few nonobese patients to permit fine balance for the nominal variable with 47 levels representing the hospital, but our new algorithm came very close to fine balance. Moreover, in that example, there was a shortage of nonobese diabetic patients, and incorporation of an additional constraint forced the match to include all of these nonobese diabetic patients, thereby coming as close as possible to balance for this important but recalcitrant covariate.

AB - In multivariate matching, fine balance constrains the marginal distributions of a nominal variable in treated and matched control groups to be identical without constraining who is matched to whom. In this way, a fine balance constraint can balance a nominal variable with many levels while focusing efforts on other more important variables when pairing individuals to minimize the total covariate distance within pairs. Fine balance is not always possible; that is, it is a constraint on an optimization problem, but the constraint is not always feasible. We propose a new algorithm that returns a minimum distance finely balanced match when one is feasible, and otherwise minimizes the total distance among all matched samples that minimize the deviation from fine balance. Perhaps we can come very close to fine balance when fine balance is not attainable; moreover, in any event, because our algorithm is guaranteed to come as close as possible to fine balance, the investigator may perform one match, and on that basis judge whether the best attainable balance is adequate or not. We also show how to incorporate an additional constraint. The algorithm is implemented in two similar ways, first as an optimal assignment problem with an augmented distance matrix, second as a minimum cost flow problem in a network. The case of knee surgery in the Obesity and Surgical Outcomes Study motivated the development of this algorithm and is used as an illustration. In that example, 2 of 47 hospitals had too few nonobese patients to permit fine balance for the nominal variable with 47 levels representing the hospital, but our new algorithm came very close to fine balance. Moreover, in that example, there was a shortage of nonobese diabetic patients, and incorporation of an additional constraint forced the match to include all of these nonobese diabetic patients, thereby coming as close as possible to balance for this important but recalcitrant covariate.

KW - Assignment algorithm

KW - Fine balance

KW - Matching

KW - Network optimization

KW - Observational study

KW - Optimal matching

UR - http://www.scopus.com/inward/record.url?scp=84862892829&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862892829&partnerID=8YFLogxK

U2 - 10.1111/j.1541-0420.2011.01691.x

DO - 10.1111/j.1541-0420.2011.01691.x

M3 - Article

VL - 68

SP - 628

EP - 636

JO - Biometrics

JF - Biometrics

SN - 0006-341X

IS - 2

ER -