Why Matching Needs Explicit Rules
A matching design is not fully specified by saying “match each treated unit to its nearest control” or “minimize total distance.” Those descriptions can leave choices unresolved. Two controls may be equally close to a treated unit; several allocations may have the same total distance; and a sequential algorithm may give different results depending on which treated unit it processes first. These differences can change which units are retained and how the matched sample is constructed.
Reproducibility means that a specified procedure, applied to the same input data, returns the same allocation. It does not mean that the allocation is uniquely dictated by the distance measure alone, nor that every reproducible allocation is a good design. The distance, eligible units, constraints, algorithm, ordering, and rules for resolving ties all need to be explicit.
For example, let \(A_i=1\) indicate a treated unit and \(A_j=0\) a control. Write \(d_{ij}\) for the distance between eligible treated unit \(i\) and control unit \(j\). The distance may be based on a propensity score or on other covariates. This tutorial concerns how to make the allocation rule reproducible, not how to choose or interpret a causal estimand.
Where Unspecified Choices Enter
A tie occurs when the rule being used cannot distinguish between two or more choices. With nearest-neighbor matching, two eligible controls may have the same minimum distance from a treated unit. With optimal matching, two different allocations may have the same objective value. A deterministic tie-breaker specifies which choice to take in such cases.
The order of processing matters particularly for greedy matching without replacement: units are processed sequentially, and a selected control is no longer available. A different processing order can therefore change the choices available to later units. By contrast, an optimization algorithm selects an allocation by optimizing a stated objective over the feasible set. Its result may still be ambiguous if several allocations attain the same optimum.
A practical specification should distinguish the substantive matching design from the computation used to implement it. Substantive design decisions include the distance, caliper, match ratio, replacement rule, and permitted match structures. Computational decisions include unit ordering, how exact ties are resolved, solver choice, and how numerical precision is handled. Changing either kind of decision can change the result.
Worked Example: A Tie in Greedy Matching Without Replacement
Suppose two treated units, \(T1\) and \(T2\), must each be matched to one control without replacement. There is no caliper, and the distance table is:
| C1 | C2 | |
|---|---|---|
| T1 | 0.10 | 0.10 |
| T2 | 0.11 | 0.20 |
Assume a greedy algorithm processes one treated unit at a time, assigning its nearest available control. If \(T1\) is processed first and ties are resolved in favor of the lower control ID, \(T1\) receives \(C1\), at distance \(0.10\). Only \(C2\) remains for \(T2\), so \(T2\) receives \(C2\), at distance \(0.20\). The total distance is \(0.10+0.20=0.30\).
If \(T2\) is processed first, it receives \(C1\), its nearest control at distance \(0.11\). Then \(T1\) receives \(C2\), at distance \(0.10\). The total is \(0.11+0.10=0.21\). Both allocations follow the stated greedy rule, but they differ because the treated-unit order differs. The second allocation happens to have a smaller total distance; that does not change what the greedy algorithm would do under the first ordering.
To reproduce one of these results, specify both the treated-unit order and the tie-break rule. If the goal is minimum total distance, a global optimization procedure is a different method from this greedy procedure; the choice should not be described as if it were merely a tie-break.
Deterministic Rules for Ties
A simple, auditable rule is to assign each unit a unique, stable identifier and use identifiers to order tied choices. For nearest-neighbor matching, one possible rule is: among controls tied at the smallest eligible distance, select the control with the lexicographically smallest identifier. “Lexicographically” means ordinary character-by-character order; for numeric identifiers, specify numeric rather than text order if that distinction matters.
For an optimization problem, a deterministic secondary objective can resolve multiple primary optima. First find the minimum possible primary cost. Then restrict attention to allocations attaining exactly that minimum and select the lexicographically first allocation under a stated ordering of treated and control IDs. This is a two-stage rule: the second stage breaks ties without sacrificing the primary optimum.
Here \(\mathcal{F}\) is the set of feasible allocations and \(C(M)\) is the primary cost of allocation \(M\). The rule works because, with a finite set of units, there are finitely many feasible allocations. The primary minimizers therefore form a finite set. If the allocation representation has a total lexicographic order and distinct allocations have distinct representations, exactly one member is lexicographically first. Thus the two-stage rule selects a unique allocation while preserving the minimum primary cost.
Do not silently add a tiny numerical perturbation to distances to break ties. A perturbation can change the primary optimum if its size is not guaranteed to be smaller than every relevant difference in primary costs. Explicit two-stage optimization, or a documented exact tie rule implemented by the matching algorithm, makes the priority of the objectives clearer.
Worked Example: Choosing Between Two Optimal Allocations
Consider two treated units, ordered \(T1,T2\), and two controls, \(C1,C2\). Each treated unit must receive one different control. The costs are:
| C1 | C2 | |
|---|---|---|
| T1 | 0.20 | 0.40 |
| T2 | 0.30 | 0.50 |
There are two feasible one-to-one allocations. Assigning \(T1\) to \(C1\) and \(T2\) to \(C2\) costs \(0.20+0.50=0.70\). Assigning \(T1\) to \(C2\) and \(T2\) to \(C1\) costs \(0.40+0.30=0.70\). Both are global minimum-cost allocations.
Specify the allocation vector in treated-unit order, listing each treated unit’s matched control. The two vectors are \([C1,C2]\) and \([C2,C1]\). Under the rule “choose the lexicographically first vector, using the stated control-ID order \(C1<C2\),” the selected allocation is \([C1,C2]\). Its total cost remains \(0.70\), the minimum. Without a secondary rule, reporting either allocation as the unique result would overstate what the primary objective determines.
Fixing the Computational Specification
A reproducible record should make clear what data and procedure were actually used. At minimum, retain the following information:
- Input data and IDs: the analytic sample, unit identifiers, treatment indicator, covariates or scores used, and any preprocessing that affects distances.
- Matching design: distance definition, eligibility rules, calipers and whether their boundaries are inclusive, match ratio, replacement policy, and any limits on matched-set composition.
- Algorithm: for a sequential method, the ordering of units and candidate selection rule; for an optimization method, the objective, constraints, solver, and tie-resolution rule.
- Numerical settings: distance precision, feasibility and optimality tolerances, and how near-equal values are treated. Do not round distances for display and then assume the displayed values were used for matching.
- Implementation: software and package versions, relevant options, and any random seed if the procedure uses randomness.
A fixed random seed can reproduce a randomized tie-break under a fixed implementation and random-number generator. It is less transparent than a deterministic rule and may not reproduce results across software versions or implementations. If random selection is part of the design, record the seed and the implementation details rather than presenting the result as a deterministic consequence of the data alone.
Worked Example: A Reproducible Nearest-Neighbor Specification
Suppose treated unit \(T4\) has three eligible controls with distances \(0.0200\), \(0.0200\), and \(0.0500\), for controls \(C03\), \(C07\), and \(C11\), respectively. The design uses one control per treated unit, no replacement, and a caliper of \(0.05\), inclusive of the boundary. Distances are computed at full stored precision.
The first two controls tie for the minimum distance; \(C11\) is farther away but still within the inclusive caliper. State that ties are resolved by the smallest numeric control ID. Since \(03<07\), \(T4\) is assigned to \(C03\) at distance \(0.0200\). If the caliper were instead strict, this particular allocation would not change, because the selected distance is below \(0.05\); a candidate exactly at \(0.05\), such as \(C11\), would be excluded under a strict rule and eligible under the stated inclusive rule.
A sufficient computational record would also state how treated units are ordered, how a control already used by an earlier match is handled, and which software implementation and settings were used. The distance table alone cannot answer those questions. With these rules fixed, the selection for \(T4\) is reproducible even if the rows in the input file are rearranged.
Diagnostics, Alternatives, and Limitations
Check the allocation rather than relying only on a written description of the algorithm. Useful checks include verifying that every matched pair satisfies the eligibility and caliper rules, that no control is reused when matching is without replacement, and that match ratios and any set-size constraints are respected. For an optimization method, recompute the objective from the reported allocation and check that it equals the claimed optimum. Also test whether changing input row order changes the allocation; if it does, row order may be acting as an undocumented tie-breaker or processing rule.
When results differ across runs, compare the input sample and IDs first, then distances and their precision, the processing order, and solver settings. Small discrepancies can arise from different numerical tolerances, especially when costs are nearly equal. If exact equality matters to the design, state how equality is defined computationally; otherwise describe the tolerance used to treat near-equal costs as tied.
| Approach | What determines the allocation? | Important limitation |
|---|---|---|
| Greedy sequential matching | Processing order, available candidates, distance rule, and tie-breaks | Different orders can produce different allocations and total costs. |
| Global optimal matching | Feasible set, objective, and rule for tied optima | A primary objective can have multiple optimal allocations. |
| Random tie-breaking | Random-number generator, seed, and implementation | A seed alone may not ensure cross-version reproducibility. |
A deterministic rule is not automatically a substantively preferable rule. Choosing the lowest ID makes the procedure auditable, but the ID usually has no statistical meaning. Greedy matching may be appropriate for a stated design, but deterministic ordering does not turn it into a global optimum. Likewise, resolving equal optima makes a result reproducible without demonstrating that the distance measure, constraints, or resulting covariate balance are appropriate. Reproducibility is a requirement for transparent computation, not a substitute for design justification.
Check Your Understanding
Answer each question, then compare with the solutions.
- In greedy matching without replacement, why can changing treated-unit order change the final allocation even when every unit uses the same nearest-available rule?
- Two global allocations both have the minimum possible total cost. What additional rule can select one reproducibly without changing that minimum?
- A matching program gives different results after input rows are rearranged. Name two possible causes to investigate.
- Why is a fixed random seed not always a complete cross-version reproducibility specification?
Solutions. (1) A control assigned early is no longer available, so changing the order changes the candidates available to later treated units. (2) Define a deterministic secondary rule, such as selecting the lexicographically first allocation by stable unit IDs among all primary optima. (3) Row order may be determining the processing order or resolving ties implicitly; also check for differences in computed distances, numerical precision, or solver settings. (4) Different software versions or implementations may use different random-number generators or consume random numbers differently, so the same seed need not produce the same choices.