From distances to a matching rule
Once treated and control units have been identified and distances between them can be calculated, a matching procedure still needs a rule for turning those distances into pairs. Greedy nearest-neighbor matching applies a local rule repeatedly: take the next treated unit in a specified order and assign it the closest control that is currently eligible. “Greedy” means the choice is made at that step, without first optimizing all assignments together.
The procedure is simple to implement, but its output depends on more than a distance formula. A complete specification names the units to match, the distance measure, the order in which treated units are processed, the number of controls sought per treated unit, and what happens to a control after it has been selected. The last choice determines whether a control can be assigned again.
For example, the distance might be the absolute propensity-score difference \(d(i,j)=|\hat e_i-\hat e_j|\). Other distance choices are possible. The distance is the input to the algorithm; the greedy selection rule is the procedure that uses it. The example below uses propensity-score differences so each comparison can be checked directly.
Specify the procedure before running it
Write the treated units in the order they will be processed as \(i_{(1)},i_{(2)},\ldots\), and let \(C_1\) be the initial set of controls. At step \(k\), choose from the current eligible set \(C_k\):
If controls are not to be reused, remove \(j_k^*\) from the eligible set before processing the next treated unit. If controls may be reused, leave the eligible set unchanged. If the eligible set is empty, no control can be assigned at that step. When several controls have the same minimum distance, a prespecified tie rule is needed to make the procedure reproducible.
These mechanics are separate from the causal assumptions needed to interpret an effect. In a typical observational setting, a causal interpretation also requires consistency, conditional exchangeability given measured pre-treatment covariates, and positivity in the population relevant to the target. Matching on an estimated score does not establish these assumptions. Nor does a good score fit by itself prove that the matched sample is balanced on the covariates.
Worked Example: Assigning Controls Sequentially
Suppose three treated units have estimated scores \(0.20\), \(0.48\), and \(0.72\). Four controls have scores \(0.18\), \(0.35\), \(0.52\), and \(0.69\). Use absolute score difference, process treated units in the order listed, and do not reuse controls.
For the first treated unit, with score \(0.20\), the distances to the four controls are \(0.02\), \(0.15\), \(0.32\), and \(0.49\). The closest is the control with score \(0.18\), so the first pair has distance \(0.02\). That control is removed from the eligible set.
For the second treated unit, with score \(0.48\), the remaining distances are \(0.13\) to score \(0.35\), \(0.04\) to score \(0.52\), and \(0.21\) to score \(0.69\). It is assigned the control with score \(0.52\), at distance \(0.04\); that control is also removed.
For the third treated unit, with score \(0.72\), the remaining distances are \(0.37\) to score \(0.35\) and \(0.03\) to score \(0.69\). It is assigned the control with score \(0.69\), at distance \(0.03\). The resulting pairs are \(0.20\leftrightarrow0.18\), \(0.48\leftrightarrow0.52\), and \(0.72\leftrightarrow0.69\). The fourth control, with score \(0.35\), remains unused. Every assignment is the closest among the controls available at the time of that assignment.
What the control-pool policy changes
For one-to-one matching without reuse, a selected control is removed from the pool and cannot match another treated unit. This enforces distinct controls in the resulting pairs. For one-to-one matching with reuse, a selected control remains available and can be the closest control for more than one treated unit. The policy is part of the method, not a minor implementation detail: it changes the matched sets and how often each control contributes to a later analysis.
In either case, the distance minimum is taken over the currently eligible controls. It is not necessarily the closest control in the original control group, since earlier assignments may have changed the pool. A standard one-to-one procedure seeks at most one control for each treated unit. If the pool is exhausted under a no-reuse policy, later treated units cannot be paired unless the design explicitly allows them to remain unmatched or specifies a different rule.
Worked Example: Retaining a Selected Control
Suppose two treated units have scores \(0.31\) and \(0.35\), and two controls have scores \(0.30\) and \(0.50\). Use absolute score difference, process the treated units in the order listed, and retain selected controls for possible reuse.
For the treated unit with score \(0.31\), the distances are \(|0.31-0.30|=0.01\) and \(|0.31-0.50|=0.19\). It is assigned the control with score \(0.30\). Because the selected control is retained, both controls remain eligible for the next step.
For the treated unit with score \(0.35\), the distances are \(|0.35-0.30|=0.05\) and \(|0.35-0.50|=0.15\). It is also assigned the control with score \(0.30\). The output has two treated units and one distinct matched control, used twice. The arithmetic verifies the greedy choice at each step; the reuse policy explains why the second assignment was allowed.
A short justification of the algorithm
The selection rule guarantees a local nearest-neighbor property. At step \(k\), the chosen control \(j_k^*\) satisfies
This follows directly from choosing an element of the set of minimizers of \(d(i_{(k)},j)\) over \(C_k\). Under no reuse, the update \(C_{k+1}=C_k\setminus\{j_k^*\}\) also ensures that a control selected at one step is absent from every later eligible set. Under reuse, \(C_{k+1}=C_k\), so that restriction does not apply. These statements justify the step-by-step mechanics; they do not say that the procedure minimizes the total distance across all assignments.
Worked Example: When the Control Pool Runs Out
Consider treated scores \(0.22\), \(0.49\), and \(0.81\), processed in that order, and control scores \(0.25\) and \(0.77\). Use absolute score difference and do not reuse controls.
For score \(0.22\), the distances are \(|0.22-0.25|=0.03\) and \(|0.22-0.77|=0.55\), so the control at \(0.25\) is selected and removed. For score \(0.49\), the only remaining control is at \(0.77\), at distance \(|0.49-0.77|=0.28\), so that control is selected and removed. The third treated unit, at \(0.81\), has no eligible control left and is unmatched.
The output contains two pairs, not three. The unmatched treated unit is not assigned an invented or unavailable control. If the design instead retained selected controls, the control at \(0.77\) would remain available for the third unit, whose distance to it would be \(|0.81-0.77|=0.04\). That would produce a different output under a different policy.
Diagnostics and limits of interpretation
A list of pairs is not enough to judge whether matching has produced a useful comparison. Inspect the covariates used to estimate the score, especially important prognostic covariates, before and after matching. Standardized differences can summarize covariate imbalance, while plots of score distributions can reveal areas with few plausible counterparts. Examine the matched distances as well: a large distance flags a pair that may be a poor match on the chosen scale. These checks describe the design; they do not by themselves prove exchangeability or eliminate unmeasured confounding.
Also report how many treated units were matched and how many were not, and make clear whether controls were available for reuse. If controls are reused, report their reuse counts because a small number of controls may contribute repeatedly. If some treated units are excluded, the resulting comparison concerns the matched treated units, not automatically every treated unit in the original sample. The target population and effect summary must match the actual design and analysis.
Greedy matching is easy to understand and implement, but it makes each choice using the current step's distance criterion. A global matching approach instead considers assignments jointly, while propensity-score weighting and regression adjustment use different strategies to construct a comparison. These alternatives do not remove the need for design diagnostics or causal assumptions. The appropriate method depends on the estimand, overlap, sample structure, and the quality of the resulting comparisons.
Common mistakes
- Searching the original control set at every step while claiming no reuse. Once a control is selected under a no-reuse rule, remove it before the next search.
- Leaving the reuse policy unstated. State whether a selected control is removed or retained; otherwise the assignments cannot be reproduced from the same distances.
- Calling the algorithm a causal estimator. Matching constructs comparisons. Causal interpretation requires the relevant design assumptions, and an effect estimate requires a separate analysis.
- Treating a small propensity-score gap as proof of covariate balance. Check balance in the measured covariates directly; similar scores do not guarantee exact finite-sample balance.
- Reporting only matched units. State which treated units were unmatched and describe the population to which the matched comparison applies.
Check Your Understanding
Answer each question, then compare your reasoning with the brief solutions.
- A treated unit has distance \(0.06\) to control A and \(0.03\) to control B. Which control is selected if both are eligible?
- Under a no-reuse policy, what happens to a selected control before the next treated unit is processed?
- There are four treated units and two controls. Under one-to-one matching without reuse, can all four treated units receive a control? Explain.
- Why does a small matched propensity-score distance not establish that the matched units are balanced on every covariate?
Solutions. (1) Control B is selected because \(0.03<0.06\). (2) It is removed from the eligible control set, so it cannot be assigned again. (3) No. At most two treated units can be paired because each of the two controls can be used only once; the other treated units must remain unmatched unless the design changes. (4) The score summarizes measured covariates through a model, and close scores do not force exact equality of covariates in a finite sample. Balance must be assessed directly, and unmeasured confounding is not ruled out by score proximity.