From Pair Matching to an Assignment Problem
In pair matching, choosing a partner for one unit affects which partners remain available to the others. The task is therefore not simply to find the closest control for each treated unit independently: it is to select a joint allocation whose total cost is as small as possible, subject to the required matching structure. The earlier material on the objective function for optimal pair matching defines the total-cost criterion; here the focus is how to represent and solve that allocation problem.
Suppose there are \(m\) treated units and at least \(m\) eligible control units. Let \(c_{ij}\) be the specified cost of pairing treated unit \(i\) with control unit \(j\). For propensity-score matching, a common cost is the absolute difference between their estimated propensity scores. Other matching costs, such as a Mahalanobis distance, can be used if the design specifies them. The assignment algorithm minimizes the costs it is given; it does not determine which cost is scientifically appropriate.
The first constraint assigns every treated unit once; the second prevents control reuse. When the numbers of treated and control units are equal, the column constraints also bind as equalities: every control is used. When there are more controls, some remain unassigned. If there are fewer controls than treated units, it is impossible to match every treated unit under these constraints. Choosing which treated units to leave unmatched changes the design and cannot be settled merely by calling an assignment algorithm.
Worked Example: Building a Cost Matrix
Suppose two hypothetical treated units have estimated propensity scores 0.40 and 0.41. Three hypothetical controls have scores 0.39, 0.60, and 0.42. Use absolute propensity-score difference as the cost.
For treated unit 1, the costs are \(|0.40-0.39|=0.01\), \(|0.40-0.60|=0.20\), and \(|0.40-0.42|=0.02\). For treated unit 2, they are \(0.02\), \(0.19\), and \(0.01\), respectively. Thus the cost matrix is
If each treated unit independently chooses its nearest control, both choose control 3, which is not a permissible one-to-one allocation. Instead compare feasible joint assignments. Pairing treated unit 1 with control 1 and treated unit 2 with control 3 costs \(0.01+0.01=0.02\). Pairing them with controls 3 and 1 costs \(0.02+0.02=0.04\). Pairing them with controls 1 and 2 costs \(0.01+0.19=0.20\). The first allocation is the minimum among the six possible assignments. Its total cost is a sum over pairs, not a guarantee that every selected pair is equally close.
How the Hungarian Algorithm Finds an Assignment
The Hungarian algorithm solves the square minimum-cost assignment problem by transforming the cost matrix while preserving the information needed to find a minimum. Its central idea is to create zero reduced costs, then search for a set of zeros with no two in the same row or column. Such a set represents an assignment. If no complete zero assignment exists yet, the algorithm adjusts the matrix to create additional zeros.
For a square matrix, subtracting a constant from every entry in a row does not change which assignment minimizes the total: every valid assignment uses exactly one entry from that row. Likewise, subtracting a constant from every entry in a column leaves all assignment totals shifted by the same amount. These reductions can make entries zero without changing the minimizing allocation.
Subtract each row minimum from that row, then subtract each column minimum from that column. The resulting entries are nonnegative reduced costs, and every row and column contains a zero.
Select zeros so that each row and each column is used at most once. If a zero can be selected in every row, the selected zeros define an assignment.
Cover all zeros with the fewest horizontal and vertical lines. If fewer than \(n\) lines cover an \(n\)-by-\(n\) matrix, let \(\delta\) be the smallest uncovered entry. Subtract \(\delta\) from every uncovered entry, add \(\delta\) to entries covered twice, and leave entries covered once unchanged. Then search again.
Read off the selected row-column pairs and sum their original costs. The algorithm's zero pattern identifies a minimum-cost allocation, but the final cost should be reported using the original, unadjusted matrix.
Worked Example: Reduced Costs Reveal a Joint Allocation
Consider three hypothetical treated units and three hypothetical controls, with costs in arbitrary distance units:
The row minima are 1, 1, and 3. Subtracting them gives
The column minima of this reduced matrix are 1, 0, and 0. Subtracting these gives
The zeros cannot yet give an assignment using three distinct columns: rows 1 and 2 have zeros only in column 2. Cover all zeros with two lines, one through column 2 and one through row 3. The uncovered entries are 4, 7, 3, and 8, so \(\delta=3\). Subtract 3 from those four entries. The intersection of the two covering lines, row 3 column 2, is covered twice, so add 3 to its value, changing 2 to 5. Entries covered once stay as they are. The adjusted matrix is
Now select row 1 column 2, row 2 column 1, and row 3 column 3. These are zeros in distinct rows and columns. In the original cost matrix, this allocation costs \(1+5+3=9\) units. The reduced matrix was used to locate the allocation; the reported total comes from the original costs.
Why a Complete Zero Assignment Is Optimal
The zero test is more than a convenient stopping rule. It follows from a lower-bound argument. Associate a number \(u_i\) with each row and \(v_j\) with each column, requiring \(u_i+v_j\leq c_{ij}\) for every pair. For any feasible assignment, its total cost is at least \(\sum_i u_i+\sum_j v_j\), because each selected cost is at least the corresponding row and column values, and a square assignment uses every row and column once. If a complete assignment uses only entries where \(c_{ij}-u_i-v_j=0\), its total equals this lower bound and therefore cannot be improved.
The reduced entries are \(c_{ij}-u_i-v_j\). Row and column reductions establish such potentials with nonnegative reduced entries. During a matrix adjustment, entries uncovered by the lines decrease by \(\delta\), while doubly covered entries increase by \(\delta\). This corresponds to increasing the row potentials for uncovered rows by \(\delta\) and decreasing the column potentials for covered columns by \(\delta\). Since \(\delta\) is the smallest uncovered entry, no reduced entry becomes negative. The adjustment therefore keeps a valid lower bound while creating at least one new zero. Once a complete zero assignment is found, the lower-bound argument certifies its global optimality.
Worked Example: A Tie Between Optimal Allocations
Suppose two hypothetical treated units have propensity scores 0.50 and 0.70. Two controls both have score 0.48, and a third has score 0.68. With absolute score difference as cost, the matrix is
Assigning the first treated unit to control 1 and the second to control 3 costs \(0.02+0.02=0.04\). Assigning the first to control 2 and the second to control 3 also costs \(0.02+0.02=0.04\). These are distinct allocations with the same minimum total: the second treated unit's closest control is control 3, and either of the two identical-score controls can be paired with the first treated unit. A software implementation may return either solution depending on its tie-breaking rules. The optimum cost is well-defined here, but the optimal allocation is not unique.
Diagnostics, Alternatives, and Limits
Before interpreting a computed allocation, verify that it obeys the intended design: every required treated unit appears once, no control is reused, and the total recomputed from original costs agrees with the selected pairs. Check the cost matrix for incorrect row or column labels, missing values, and unexpected scales. A numerical optimum can be perfectly correct for a matrix that was assembled incorrectly.
The assignment method is appropriate when the design requires a globally minimum sum of pair costs under one-to-one constraints. Greedy nearest-neighbor matching instead makes sequential local choices; as the earlier material on order dependence and greedy suboptimality explains, those choices can depend on ordering and need not minimize the total cost. Exhaustive enumeration also finds the minimum in principle, but the number of possible allocations grows rapidly, while assignment algorithms solve the problem much more efficiently.
The optimization criterion has limits. Minimizing the sum of distances does not guarantee that each pair is close, that covariate balance is adequate, or that a causal effect is identified. A small number of relatively costly pairs can be hidden by many cheap ones. Changing the cost definition can change the allocation, and matching on a propensity score alone does not ensure balance on every covariate. The algorithm also does not decide whether units should be discarded or which causal estimand is appropriate. Those are design decisions, not consequences of a minimum-cost calculation.
A common mistake is to claim that each unit has been matched to its individually nearest available partner. The algorithm instead minimizes the sum over all assignments that satisfy the joint constraints; some units may receive a partner that is not their individual nearest because that choice allows a lower total cost across the sample. Another mistake is to infer that the matching is good merely because the algorithm terminated. Check pair distances and post-match covariate balance, and assess whether the design's assumptions are plausible.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions.
- In a one-to-one assignment, what does \(x_{ij}=1\) mean, and why can two treated units not both be assigned to the same control?
- A square cost matrix has a complete assignment using only zero reduced-cost entries. Why is that assignment minimum-cost?
- For costs \(\begin{pmatrix}2&5\\3&1\end{pmatrix}\), compare the two possible assignments and give the minimum total cost.
- Why does a low minimum total cost not establish that covariate balance is satisfactory?
Solutions. (1) It means treated unit \(i\) is assigned to control \(j\). The column constraint \(\sum_i x_{ij}\leq1\) allows each control to appear at most once. (2) A complete zero assignment has total cost equal to the sum of its row and column potentials, a lower bound on every feasible assignment, so no assignment can have lower cost. (3) The diagonal assignment costs \(2+1=3\); the off-diagonal assignment costs \(5+3=8\). The minimum is 3 cost units. (4) A sum can conceal a few poor pairs, and the cost may represent only one distance or score. Balance must be examined using the study's relevant covariates; the optimization criterion alone does not certify it.