From Pairwise Distances to a Matching
A distance table gives the cost of pairing each treated unit with each control unit. The optimal matching problem is to select pairs so that each treated unit and each control unit appears exactly once, while the sum of the selected distances is as small as possible. In a small problem, the central task is to enumerate every eligible allocation and compare its total cost with the others.
The distances might be absolute differences in estimated propensity scores or another chosen measure of covariate dissimilarity. Once the distance table is specified, the calculation is an assignment problem: the chosen pairs must form a complete one-to-one allocation, and the objective is the sum of their distances. This tutorial focuses on solving small examples by enumeration, not on how to construct the distance measure.
For equal-sized groups with every pair available, each assignment can be represented by a permutation \(\pi\) of the control indices: treated unit \(T_i\) is paired with \(C_{\pi(i)}\). Its cost is
There are \(n!\) such assignments: \(n\) choices for the control paired with the first treated unit, \(n-1\) remaining choices for the second, and so on. Thus a two-by-two problem has 2 assignments, and a three-by-three problem has 6. Listing them all is practical for small problems and guarantees the minimum, provided the list is complete and the costs are added correctly.
A Complete Enumeration
The method depends on a few specific conditions. The distance table must contain fixed pairwise costs, the assignment must use every treated and control unit exactly once, and the objective must be the sum of the selected distances. The examples below assume equal numbers of treated and control units and that every pair is available. If a study imposes additional restrictions, the set of feasible assignments changes; the simple enumeration here does not add such restrictions.
Keep the unit labels and distance values visible so each selected pair can be checked against the input.
Each treated unit receives one control, and no control is used twice. For \(n\) pairs, check that there are \(n!\) listed assignments.
Add the \(n\) distances selected by that assignment, showing the terms so the calculation can be audited.
Compare the totals, then verify that the selected pairs use every unit exactly once.
Worked Example: Comparing the Two Possible Assignments
Suppose a hypothetical study has two treated units, \(T_1,T_2\), and two control units, \(C_1,C_2\). The entries are absolute propensity-score distances.
| \(C_1\) | \(C_2\) | |
|---|---|---|
| \(T_1\) | 0.02 | 0.06 |
| \(T_2\) | 0.05 | 0.03 |
There are \(2!=2\) complete assignments. The first pairs \(T_1\) with \(C_1\) and \(T_2\) with \(C_2\):
The second pairs \(T_1\) with \(C_2\) and \(T_2\) with \(C_1\):
Because \(0.05<0.11\), the minimum-distance assignment is \(T_1\) with \(C_1\) and \(T_2\) with \(C_2\), with total absolute propensity-score distance 0.05. Each treated unit and each control unit appears once, so the selected allocation is feasible.
The reason exhaustive enumeration works is simple but important: every valid complete one-to-one assignment corresponds to one permutation of the controls. If all \(n!\) permutations are listed, no valid assignment is missing. Each one has a computed total \(D(\pi)\); choosing the smallest of those totals therefore minimizes the objective over the entire feasible set. This is a finite comparison, not a claim that any one selected pair is individually closest.
Three Units: Checking Every Allocation
Worked Example: Finding the Minimum Among Six Assignments
Consider a hypothetical three-treated, three-control problem. Distances are shown in the table.
| \(C_1\) | \(C_2\) | \(C_3\) | |
|---|---|---|---|
| \(T_1\) | 0.04 | 0.03 | 0.08 |
| \(T_2\) | 0.05 | 0.07 | 0.02 |
| \(T_3\) | 0.06 | 0.04 | 0.05 |
There are \(3!=6\) assignments. Represent each by the control assigned to \(T_1,T_2,T_3\), in that order:
- \((C_1,C_2,C_3)\): \(0.04+0.07+0.05=0.16\).
- \((C_1,C_3,C_2)\): \(0.04+0.02+0.04=0.10\).
- \((C_2,C_1,C_3)\): \(0.03+0.05+0.05=0.13\).
- \((C_2,C_3,C_1)\): \(0.03+0.02+0.06=0.11\).
- \((C_3,C_1,C_2)\): \(0.08+0.05+0.04=0.17\).
- \((C_3,C_2,C_1)\): \(0.08+0.07+0.06=0.21\).
The smallest total is \(0.10\), attained by pairing \(T_1\) with \(C_1\), \(T_2\) with \(C_3\), and \(T_3\) with \(C_2\). The total absolute propensity-score distance for this allocation is 0.10. The list includes all six permutations, and the selected allocation uses each control once.
A useful audit is to check the assignment list independently from the cost arithmetic. In a three-by-three problem, every line must contain three different controls. The set of lines must cover each of the six possible permutations once. These checks catch common errors such as repeating a control within an allocation or accidentally omitting an allocation that could have had the smallest total.
Why the Smallest Total May Not Use Each Unit’s Nearest Partner
A tempting shortcut is to give every treated unit its nearest control. But several treated units may have the same nearest control, and a one-to-one allocation cannot reuse that control. The global objective balances the distances across all pairs; it is not the separate minimization of each row.
Worked Example: The Best Allocation Is a Joint Decision
In this hypothetical distance table, \(T_1\) and \(T_2\) both have their smallest row distance to \(C_1\). \(T_3\)'s smallest distance is also to \(C_1\).
| \(C_1\) | \(C_2\) | \(C_3\) | |
|---|---|---|---|
| \(T_1\) | 0.010 | 0.020 | 0.090 |
| \(T_2\) | 0.020 | 0.080 | 0.100 |
| \(T_3\) | 0.035 | 0.046 | 0.110 |
If one first assigns \(T_1\) to its nearest control \(C_1\), that control is unavailable to the other treated units. More generally, independently selecting each row minimum would assign several treated units to \(C_1\), which is not a valid one-to-one allocation. Enumerating gives:
- \((C_1,C_2,C_3)\): \(0.010+0.080+0.110=0.200\).
- \((C_1,C_3,C_2)\): \(0.010+0.100+0.046=0.156\).
- \((C_2,C_1,C_3)\): \(0.020+0.020+0.110=0.150\).
- \((C_2,C_3,C_1)\): \(0.020+0.100+0.035=0.155\).
- \((C_3,C_1,C_2)\): \(0.090+0.020+0.046=0.156\).
- \((C_3,C_2,C_1)\): \(0.090+0.080+0.035=0.205\).
The minimum is \(0.150\), attained by pairing \(T_1\) with \(C_2\), \(T_2\) with \(C_1\), and \(T_3\) with \(C_3\). In particular, \(T_3\) is paired with a control whose distance is 0.110, even though its row minimum is 0.035. That larger pair distance is part of the assignment with the smallest total because the other two selected distances are both 0.020. The result illustrates why the assignment must be optimized jointly.
Interpreting the Result and Checking for Problems
The minimum total is meaningful only relative to the specified distance measure and the chosen set of units. Absolute propensity-score distances are measured on the propensity-score scale; Mahalanobis distances use a different scale. Costs should be summed and compared within the same problem using one consistent definition. A smaller total under one distance definition does not automatically mean a better match under another.
A minimum-distance allocation is a design calculation. It identifies the allocation that minimizes the stated sum among the assignments considered. It does not by itself establish covariate balance, remove unmeasured confounding, or show that a treatment effect has been identified. The resulting matched data still require appropriate diagnostic assessment and causal assumptions.
For a small problem, exhaustive enumeration is transparent and easy to verify. Its limitation is that the number of assignments grows as \(n!\), so listing them all quickly becomes impractical. Assignment algorithms address larger problems without requiring a person to write down every permutation; the objective they solve is still the total-cost objective used here. In contrast, a greedy nearest-neighbor procedure makes local choices as it proceeds and need not find the global minimum.
Common errors include adding distances from different assignments together, using a control more than once, omitting a permutation, and reporting the smallest individual distance instead of the smallest assignment total. A practical check is to verify that every candidate line uses each unit once, count the candidate lines, recompute the winning sum from the table, and compare it with all other totals. If two assignments have the same smallest total, both are optimal for this objective; the distance calculation alone does not distinguish them.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions below.
- For a complete one-to-one problem with four treated and four control units, how many assignments must be checked by exhaustive enumeration?
- For two treated units and two controls, the distances are \(d_{11}=0.03\), \(d_{12}=0.04\), \(d_{21}=0.02\), and \(d_{22}=0.08\). Which assignment has the smaller total, and what is that total?
- Why is assigning every treated unit its individually nearest control not necessarily a valid one-to-one allocation?
- What does a minimum total distance establish, and name one conclusion it does not establish.
Solutions. (1) There are \(4!=4\cdot3\cdot2\cdot1=24\) assignments. (2) The diagonal assignment costs \(d_{11}+d_{22}=0.03+0.08=0.11\). The other costs \(d_{12}+d_{21}=0.04+0.02=0.06\), so the cross-assignment is optimal, with total distance 0.06. (3) Different treated units may have the same nearest control, but a complete one-to-one allocation can use each control only once. (4) It establishes that the selected feasible allocation minimizes the specified sum of distances among the assignments considered. It does not, by itself, establish covariate balance or identify a causal effect.