Why a Locally Best Match May Not Be Best Overall
In nearest-neighbor matching, it is natural to give each treated unit the closest available control. But when controls cannot be reused, the choice for one treated unit changes the options left for the others. A choice that is best for the current unit can therefore lead to a larger total distance across all matched pairs than a different set of assignments would.
The issue is not that the nearest-neighbor rule calculates a distance incorrectly. It is that it makes assignments one at a time, while a joint assignment considers the pairs together. The distinction matters whenever the goal is to match multiple treated units without replacement.
For the comparisons here, assume the distance table is fixed, distances are comparable across all candidate pairs, each treated unit is to receive one match, controls are not reused, and every treated-control pairing in the table is allowed. A greedy result can depend on which treated unit is processed first and how ties are resolved. A joint assignment is better with respect to total distance if its sum is smaller; this comparison does not, by itself, say that it is better on every other matching criterion.
A Two-Pair Example
The following hypothetical units have estimated propensity scores between 0 and 1. Use absolute propensity-score distance, \(d_{ij}=|\hat{p}_i-\hat{p}_j|\). The entries in the table are distances in propensity-score units.
| Control C1: 0.58 | Control C2: 0.30 | |
|---|---|---|
| Treated A: 0.50 | 0.08 | 0.20 |
| Treated B: 0.72 | 0.14 | 0.42 |
Worked Example: The First Closest Pair Leads to a Larger Total
Process A first. Its closest control is C1, because \(0.08<0.20\). Without replacement, B must then be assigned to C2. The greedy pairs and total are
Now consider assigning both pairs jointly: assign A to C2 and B to C1. This is a valid one-to-one assignment, and its total is
The joint assignment has the smaller total: \(0.34<0.50\), a reduction of \(0.16\) propensity-score units. The greedy choice was locally closest for A, but it used the control that was especially close to B. Assigning A to its second-closest control leaves B with a much closer remaining option. This is the basic way a locally sensible choice can make the overall pairing worse.
The comparison uses the same two treated units, the same two controls, and the same number of pairs. Only the assignments differ. Thus the smaller sum is not a result of dropping a difficult-to-match unit or changing the distance measure.
Why Swapping Can Improve the Total
The two-pair comparison can be written as a simple condition. Suppose a greedy assignment pairs treated unit 1 with control 1 and treated unit 2 with control 2. Its total is \(d_{11}+d_{22}\). Swapping the controls gives total \(d_{12}+d_{21}\). The swap improves the total exactly when
or, equivalently, when the original total exceeds the swapped total. The fact that control 1 was closest to treated unit 1 does not prevent this inequality: the cost of assigning treated unit 2 to its remaining control may outweigh the local advantage.
Worked Example: Checking Whether an Exchange Helps
Consider another hypothetical distance table, again based on absolute differences between estimated propensity scores. Treated unit R has score \(0.45\), treated unit S has score \(0.68\), control X has score \(0.54\), and control Y has score \(0.25\). The distances are
If R is processed first, it takes X, its closest control. S then takes Y, so the greedy total is \(0.09+0.43=0.52\). The exchanged assignment has R paired with Y and S with X, giving \(0.20+0.14=0.34\). Substitution into the swap condition confirms the improvement:
The advantage is \(0.52-0.34=0.18\) propensity-score units. This calculation checks the two possible assignments directly; it does not require guessing from the table which combination will have the smaller sum.
Greedy Matching Is Not Always Suboptimal
A greedy assignment can equal a joint assignment or even be the best assignment for the total-distance criterion in a particular data set. The point is not that greedy matching always fails, but that its step-by-step rule does not guarantee the smallest possible total.
Worked Example: A Case Where Greedy Makes the Better Pairing
Suppose treated units U and V have estimated propensity scores \(0.20\) and \(0.55\), and controls M and N have scores \(0.24\) and \(0.60\). With absolute score distance, the four distances are
If U is processed first, it takes M at distance \(0.04\); V then takes N at distance \(0.05\). The greedy total is \(0.04+0.05=0.09\). The only alternative one-to-one assignment pairs U with N and V with M, with total \(0.40+0.31=0.71\). Here the greedy assignment has the smaller total because each treated unit is close to a different control.
A small example can show that an assignment is suboptimal, but a particular greedy result should be compared with feasible alternatives before making that claim. For larger matching problems, inspecting every possible assignment by hand quickly becomes impractical. The central lesson remains: a local nearest-neighbor rule alone supplies no general guarantee that the sum across all pairs is as small as it could be.
What to Check in Practice
When reviewing a matching result, inspect more than the first few pairs. A useful audit keeps the distance for each pair and the total distance, and checks whether the result is sensitive to the order in which treated units were processed. If changing the order changes pair identities or the total appreciably, the sequential procedure is exposing a genuine feature of the assignment problem, not a change in the distances themselves.
- Recalculate pair distances. Verify that the displayed distances agree with the stated score and distance definition.
- Check assignment constraints. Confirm that each treated unit received the intended number of matches and that no control was reused when matching without replacement.
- Compare totals on the same basis. Competing assignments should use the same units, distance measure, and number of pairs. Otherwise, a smaller sum may reflect a changed problem rather than a better allocation.
- Review the distances of individual pairs. A favorable sum can conceal one comparatively distant pair. The total summarizes all pair distances but does not describe their distribution.
- Assess covariate balance after matching. A smaller propensity-score-distance total does not prove that all measured covariates are adequately balanced, nor does it establish that unmeasured confounding is absent.
The distances should also be treated as estimates when they are based on estimated propensity scores. Uncertainty in those scores can affect which controls appear closest and can make small differences between assignments less compelling. This is a reason to examine the matching result and its balance diagnostics carefully, not a reason to regard the distance table as error-free evidence about causal effects.
How the Alternatives Differ
A joint assignment considers the complete set of pairs together and can select the assignment with the smaller total among the feasible assignments being compared. This addresses the particular weakness illustrated above: one treated unit’s local choice need not determine the control available to another. It is a different decision rule from sequential greedy assignment, not a change in the distance measure.
Matching with replacement is another possible design choice. It allows a control unit to serve as a match more than once, so it changes which assignments are feasible and may avoid forcing a treated unit to take a poor remaining control. That does not make it equivalent to a joint assignment without replacement: the matching constraints differ, and repeated use of a control must be accounted for in subsequent analysis. Neither allowing reuse nor minimizing a total distance guarantees acceptable balance on every covariate.
Finally, choosing the smallest total distance is only one criterion for a matching design. It may not correspond to a requirement that every individual pair be sufficiently close, and the matching result still needs substantive and statistical assessment. A low sum is a useful summary of the chosen distance, not a complete diagnostic or a causal conclusion.
Common Mistake
Check Your Understanding
Answer each question, then check the solutions.
- Two treated units have distances to controls C1 and C2 as follows: T1 has distances 0.07 and 0.16; T2 has distances 0.12 and 0.35. If T1 is processed first and matching is without replacement, what is the greedy assignment and its total? What is the total for the swapped assignment?
- For a two-pair assignment, state the inequality that must hold for swapping the controls to reduce total distance.
- Does finding one joint assignment with a smaller total prove that every greedy assignment is suboptimal? Explain.
- Give two checks, other than comparing total distances, that help evaluate a matching result.
Solutions. 1. T1 takes C1 at 0.07, leaving C2 for T2 at 0.35, so the greedy total is \(0.07+0.35=0.42\). The swapped assignment has T1-C2 and T2-C1, with total \(0.16+0.12=0.28\), which is smaller. 2. If the current pairs are 1-1 and 2-2, the swap reduces the total when \(d_{12}+d_{21}<d_{11}+d_{22}\). 3. No. That comparison establishes that the specific greedy assignment considered has a larger total than the feasible joint assignment; another processing order or another data set may yield a different greedy result. 4. Examples include checking that distances match the stated distance definition, verifying that controls were not reused when matching without replacement, inspecting individual pair distances, and assessing covariate balance after matching.