Purpose: To compare the greedy and optimal matching techniques in a propensity score matched-pair sample.

The greedy match is the most frequently used matching algorithm to match cases to controls. Once a match is made, it is fixed. The optimal matching algorithm reconsiders all previously made matches before making the current match.

Methods: We developed a propensity score model of medication usage in a cohort of 1819 osteoarthritis patients to match 410 cases to 1409 controls. The model included patient demographics, disease severity indicators, and clinically-plausible interactions. We used the SAS macro ‘%match’ to generate a series of optimal and greedy matched pairs based on propensity scores.

We then estimated the absolute difference between the propensity scores of each matched pair. We used this to obtain the mean absolute difference for the matched set. Lower mean absolute differences indicate closer matches and less bias in the matching algorithm. A bias ratio of absolute difference in propensity score between matched pairs (greedy matched/ optimal matched) was calculated to compare matches between greedy and optimal matching. Bias ratios >1 indicate superiority of the optimal match.

Results: Matched pairs created through optimal matching consistently show smaller absolute differences in propensity scores than pairs developed through greedy matching. The bias ratio is greater than 1 for all sets and it increases as the number of matched pairs increase.

Table: Absolute Differences in Propensity Scores

Number of matched pairs	Absolute Difference in Propensity Scores (x 10-5)		Bias Ratio (A/B)
	Greedy Matching (A)	Optimal Matching (B)
350	24.38	22.72	1.07
300	12.86	12.24	1.05
250	8.36	8.16	1.02
200	5.66	5.56	1.02
150	3.61	3.58	1.01
100	2.01	1.99	1.01
50	0.90	0.90	1.00

Conclusion: Optimal matching provides more closely matched pairs than the more commonly used greedy matching technique. The greedy match performs poorly when there is intense competition for controls. Hence as the number of matched pairs increase, and competition for controls increases, the greedy match performs increasingly biased matches as compared to the optimal match.