Why Processing Order Matters
Greedy nearest-neighbor matching makes one assignment at a time: take the next treated unit, match it to the closest eligible control, and remove that control from the pool if matching is without replacement. This rule is straightforward to apply, but it can make the final set of pairs depend on which treated unit is processed first. The effect can occur even when every nearest control is unique, so it is different from the tie-breaking issue.
The issue matters because two analysts can use the same estimated propensity scores, the same distance measure, and the same no-replacement rule, yet obtain different pairs solely because they used different treated-unit orders. Order dependence is a property of the assignment procedure. By itself, it does not show that one assignment is causally valid or invalid; causal interpretation still depends on the study design and assumptions, as well as on the quality of the resulting matches.
The Sequential Rule and an Algebraic Condition
Write the processing order as \(\pi=(t_1,\ldots,t_K)\), where \(K\) is the number of treated units. Let \(\mathcal{C}_k\) be the controls not used before step \(k\). If at least one control remains, the match at that step is
A fixed rule must be specified if two available controls are equally close. That rule makes the procedure reproducible, but it does not remove order dependence when all relevant distances are unequal. The central mechanism is that an early treated unit can consume a control that a later treated unit would also choose as its nearest available match.
A simple sufficient condition makes this mechanism explicit. Suppose there are two treated units \(a,b\) and two controls \(x,y\), and both treated units strictly prefer \(x\):
If \(a\) is processed first, it takes \(x\), leaving \(b\) with \(y\). If \(b\) is processed first, it takes \(x\), leaving \(a\) with \(y\). Thus reversing the order reverses which treated unit receives each control. The inequalities are strict, so no tie-breaking rule is involved.
Worked Example: Reversing Two Treated Units Changes Both Pairs
Consider hypothetical estimated propensity scores for two treated units and two controls. Matching is 1:1, without replacement, with absolute propensity-score distance and no caliper.
| Unit | Group | Estimated propensity score |
|---|---|---|
| A | Treated | 0.40 |
| B | Treated | 0.50 |
| X | Control | 0.41 |
| Y | Control | 0.60 |
The distances from A are \(d(A,X)=|0.40-0.41|=0.01\) and \(d(A,Y)=|0.40-0.60|=0.20\). The distances from B are \(d(B,X)=|0.50-0.41|=0.09\) and \(d(B,Y)=|0.50-0.60|=0.10\). Each treated unit strictly prefers X when both controls are available.
Order A, then B. A takes X because \(0.01<0.20\). X is removed, so B takes Y, at distance \(0.10\). The pairs are A–X and B–Y, with total pair distance \(0.01+0.10=0.11\).
Order B, then A. B takes X because \(0.09<0.10\). A must then take Y, at distance \(0.20\). The pairs are B–X and A–Y, with total pair distance \(0.09+0.20=0.29\).
Both runs use the same scores, distance, and matching rule. The assignments differ because the first treated unit claims X. The different total distances are a useful description of these two outputs, but the key conclusion here is simply that the assignment depends on the processing order.
Order Dependence Is Possible, Not Inevitable
A competition for a control is not enough by itself to guarantee that the final assignments change. The distance pattern may give each treated unit a distinct preferred control, in which case either order produces the same pairs. Comparing the nearest and next-nearest distances for treated units is a practical way to see whether such competition is plausible.
Worked Example: Different Orders Give the Same Pairs
Suppose the hypothetical scores are A \(=0.20\), B \(=0.80\), X \(=0.19\), and Y \(=0.79\), where A and B are treated and X and Y are controls. Again, use absolute score distance and match without replacement.
For A, \(d(A,X)=|0.20-0.19|=0.01\), whereas \(d(A,Y)=|0.20-0.79|=0.59\). For B, \(d(B,Y)=|0.80-0.79|=0.01\), whereas \(d(B,X)=|0.80-0.19|=0.61\).
If A is first, A takes X and B takes Y. If B is first, B takes Y and A takes X. In either order, the pairs are A–X and B–Y, with total distance \(0.01+0.01=0.02\). Each treated unit's preferred control is different, so neither unit's first choice is removed before its turn.
These examples also clarify the distinction between order dependence and exact ties. A tie occurs when a treated unit has equal distance to at least two currently available controls, such as \(d(t,x)=d(t,y)\). Order dependence can instead arise from strict inequalities, as in the first example. Resolving ties consistently is necessary for reproducibility, but it cannot prevent a previously assigned control from changing a later unit's available choices.
Replacement Changes the Role of Order
With replacement, a matched control remains available for subsequent treated units. When every treated unit is matched independently to its closest control in the same fixed control set, the match for a treated unit does not depend on which other treated units have already been processed. The same deterministic tie rule must still be used if there are equal nearest distances.
Worked Example: Reuse Makes These Matches Order-Invariant
Use the scores from the first example: A \(=0.40\), B \(=0.50\), X \(=0.41\), and Y \(=0.60\). Now allow matching with replacement.
A chooses X because \(|0.40-0.41|=0.01\), less than \(|0.40-0.60|=0.20\). B also chooses X because \(|0.50-0.41|=0.09\), less than \(|0.50-0.60|=0.10\). Since X remains available, processing A before B or B before A gives the same matches: A–X and B–X.
This result follows from the stated procedure: each treated unit chooses from the unchanged control set. It does not mean that replacement is always preferable. Reusing a control changes the structure and interpretation of the matched sample, and a separate design decision is needed about whether reuse is appropriate.
How to Check and Report Order Sensitivity
When matching without replacement, the processing order should be stated rather than left implicit. A practical sensitivity check is to rerun the same matching procedure under a small set of clearly specified orders—for example, the observed data order and an order determined by a stated rule—and compare the resulting assignments. This is a diagnostic, not a way to select the order that produces the most appealing result.
For each run, inspect which treated units are paired to which controls, whether any treated units remain unmatched, and the distances within pairs. Also inspect the balance of pre-treatment covariates in the matched sample. A change in pair identities may have little effect on aggregate balance, or it may materially change it; neither outcome should be assumed in advance. The estimated propensity score itself is not evidence that the realized matched sample has adequate balance.
The procedure's assumptions and limits should be kept clear. The score-distance rule presumes that estimated scores are available and comparable on the same scale, and the assignment is defined only among eligible controls. With no caliper, the nearest available control is selected even if its score distance is large. If there are fewer controls than treated units, a no-replacement run cannot match every treated unit. Moreover, an order-stable result does not establish exchangeability, adequate overlap, or balance on all relevant covariates. Those are distinct concerns from the mechanics of the assignment.
State the score distance, matching ratio, whether controls may be reused, and any eligibility rules. State how ties are handled.
Use a reproducible ordering rule and retain the order as part of the analysis record.
Repeat the same no-replacement algorithm under alternative prespecified orders; compare pair identities, distances, unmatched units, and covariate balance.
Describe order-dependent changes transparently. Do not interpret a preferred assignment as proof that confounding has been removed.
Common Pitfall and Practical Interpretation
Wrong reasoning: “Every treated unit was matched to its nearest control, so the assignment must be unique and independent of order.” This overlooks the word “available.” A control that is nearest for two treated units is available to whichever unit is processed first, but unavailable to the second under matching without replacement.
Correction: Nearest-neighbor describes each local choice at its turn; it does not specify a unique set of pairs. State the processing order and evaluate whether plausible alternative orders change the output. If all treated units have distinct preferred controls, the assignments may be unchanged, but that must be checked rather than presumed.
Matching with replacement avoids this particular competition because a control can be reused. A joint assignment procedure is another broad alternative because it considers assignments together rather than making only sequential local choices. These approaches have different design implications; order sensitivity alone does not determine which should be used. The essential lesson is that greedy no-replacement matching is an algorithm whose output can be sensitive to an implementation choice, so that choice belongs in the analysis report.
Check Your Understanding
Answer each question, then compare with the solutions below.
- With treated scores 0.30 and 0.50 and control scores 0.31 and 0.52, does reversing the treated order change the no-replacement pairs? Show the relevant distances.
- Explain why an order-dependent assignment can occur when there are no exact ties.
- For the first worked example, what pairs result if matching is with replacement?
- Name two diagnostics to compare across alternative treated-unit orders, and explain why order stability alone does not prove a causal effect is unbiased.
Solutions. (1) Let the treated units be A \(=0.30\), B \(=0.50\), and controls X \(=0.31\), Y \(=0.52\). The distances are \(d(A,X)=0.01\), \(d(A,Y)=0.22\), \(d(B,X)=0.19\), and \(d(B,Y)=0.02\). A prefers X and B prefers Y, so either order produces A–X and B–Y. (2) Strictly unequal distances can still give two treated units the same nearest control. The first consumes it, leaving the second to take another control. (3) A chooses X at distance \(0.01\), and B also chooses X at distance \(0.09\), because X remains available; the pairs are A–X and B–X. (4) Compare pair identities and within-pair score distances; also compare unmatched treated units or pre-treatment covariate balance. Stability describes the algorithm's output, not whether the causal assumptions hold or whether unmeasured confounding is absent.