Why an Objective Function Is Needed
In pair matching without replacement, each matched pair uses one treated unit and one control unit, and neither unit can be used in a second pair. When several assignments satisfy those rules, a matching procedure needs a criterion for comparing them. Optimal pair matching makes that comparison by minimizing the total distance across the selected treated-control pairs, subject to the assignment and eligibility requirements.
The word “optimal” is relative to the specified distance, eligible pairs, and number of pairs. It does not mean that the resulting matched sample is best according to every possible measure of covariate balance, nor does minimizing distance by itself establish a causal effect. The design choices that define the objective therefore matter as much as the act of minimizing it.
Formalizing the Matching Problem
Let \(I\) denote the set of treated units and \(J\) the set of control units. For a treated unit \(i\in I\) and control unit \(j\in J\), let \(d_{ij}\) be the specified distance or cost of pairing them. This might be a propensity-score distance or a covariate distance, including a Mahalanobis distance. The distance must be defined consistently for the pairs being compared.
Not every treated-control pair must be allowed. Define \(E\subseteq I\times J\) as the eligibility set: \((i,j)\in E\) exactly when that pair is permitted by the design. A caliper or an exact-matching requirement can be represented by excluding disallowed pairs from \(E\). Distances need only be used for eligible pairs.
The first set of constraints prevents a treated unit from being matched more than once; the second does the same for controls. The total-pair constraint fixes the matching size, and the binary restriction makes each eligible pair either selected or not selected. The objective adds the cost of every selected pair exactly once. Thus, among assignments of the specified size that obey the eligibility rules, the chosen assignment has the smallest sum of pair distances.
If every treated unit is to be matched, replace the treated-unit inequalities with \(\sum_{j:(i,j)\in E}x_{ij}=1\) for each \(i\in I\), and set \(K=|I|\). That formulation is feasible only if there are enough eligible controls arranged so that all treated units can receive distinct controls. If some treated units may remain unmatched, the inequalities allow that, while \(K\) specifies how many units are to be matched. One can instead define \(K\) as the largest feasible number of pairs and then minimize total distance among assignments of that size. This prioritizes matching as many pairs as possible before comparing their total distances.
Why the Objective Has This Form
The binary variables encode a particular assignment. For any feasible assignment, \(d_{ij}x_{ij}=d_{ij}\) when pair \((i,j)\) is selected and equals zero otherwise. Summing these terms therefore gives the assignment’s total distance. The one-to-one constraints ensure that this sum describes disjoint pairs rather than repeated use of a unit.
Fixing \(K\) is essential to this interpretation. If the only goal were to minimize the sum and the number of pairs were unconstrained, setting every \(x_{ij}=0\) would give a total of zero. The optimization would select no pairs, not a useful matching. Fixing the pair count—or specifying a separate penalty or reward for leaving units unmatched—prevents that trivial solution.
Worked Example: Two Treated Units Compete for the Same Control
Suppose there are treated units \(T_1,T_2\) and controls \(C_1,C_2\). All four pairs are eligible, and the hypothetical distances are:
| \(C_1\) | \(C_2\) | |
|---|---|---|
| \(T_1\) | 1 | 4 |
| \(T_2\) | 2 | 3 |
Set \(K=2\), so both treated units must be paired and each control can be used at most once. If each treated unit independently chooses its nearest control, both choose \(C_1\): \(T_1\) has distance 1 to \(C_1\), and \(T_2\) has distance 2 to \(C_1\), compared with 3 to \(C_2\). Those individual choices conflict because they reuse the same control.
There are two feasible assignments of two pairs. The assignment \(T_1\to C_1,\ T_2\to C_2\) has total distance \(1+3=4\). The assignment \(T_1\to C_2,\ T_2\to C_1\) has total distance \(4+2=6\). The objective selects the first assignment because \(4<6\). Each treated unit receives a distinct control, and the total cost is the smaller of the two feasible totals.
Eligibility and the Matching Size
Eligibility restrictions define which assignments are allowed; they are not merely preferences in the objective. If a pair fails a design rule, it should not be selectable, even if its distance is small. Conversely, a large distance does not itself make a pair ineligible unless the design defines a rule—such as a caliper—that excludes it.
Worked Example: Excluding an Ineligible Pair
Consider three treated units and two controls. The hypothetical costs are shown below; \(T_1\)-\(C_2\) is ineligible, while every other listed pair is eligible. Require \(K=2\).
| \(C_1\) | \(C_2\) | |
|---|---|---|
| \(T_1\) | 1 | Ineligible |
| \(T_2\) | 2 | 3 |
| \(T_3\) | 4 | 1 |
Because \(T_1\)-\(C_2\) is excluded from \(E\), its decision variable does not appear in the optimization. The assignment \(T_1\to C_1,\ T_3\to C_2\) is feasible and has total distance \(1+1=2\). Another feasible assignment, \(T_2\to C_1,\ T_3\to C_2\), has total distance \(2+1=3\). An assignment using \(T_1\)-\(C_2\) is not a competitor at all, regardless of what cost one might have assigned to it. Among the feasible two-pair assignments, the minimum total distance is 2.
There are three treated units but only two controls, so \(K=2\) leaves one treated unit unmatched. The matching-size constraint does not specify in advance which treated unit is left out; the objective and eligibility constraints jointly determine that choice.
A target \(K\) must be feasible under the eligibility rules. In the example, \(K=2\) is feasible. In a different eligibility pattern, even when there are at least \(K\) controls and \(K\) treated units, some units may have too few distinct eligible partners to form \(K\) pairs. If no feasible assignment satisfies the constraints, the optimization problem has no solution. The appropriate response is to reconsider the target size or the design restrictions, not to silently include prohibited pairs.
Worked Example: Choosing Which Treated Units Remain Unmatched
Suppose three treated units are to be matched to two controls, with all pairs eligible. The hypothetical distances are:
| \(C_1\) | \(C_2\) | |
|---|---|---|
| \(T_1\) | 1 | 6 |
| \(T_2\) | 2 | 3 |
| \(T_3\) | 0.5 | 8 |
Set \(K=2\). The assignment \(T_3\to C_1,\ T_2\to C_2\) has total distance \(0.5+3=3.5\). Another promising assignment, \(T_1\to C_1,\ T_2\to C_2\), has total distance \(1+3=4\). The assignment \(T_1\to C_2,\ T_3\to C_1\) has total distance \(6+0.5=6.5\). Checking the remaining possible pairings gives totals \(8\), \(9\), and \(10\); thus the minimum is 3.5, and \(T_1\) is left unmatched.
This choice follows from the specified objective and \(K\), not from a rule that every treated unit must be retained. If the design instead required all treated units to be matched, this problem would be infeasible because there are only two controls. Matching a subset can also change which treated population is represented, so the matching objective alone does not settle the scientific consequences of excluding units.
Assumptions, Diagnostics, and Interpretation
The optimization is mathematically well-defined when the sets of units and eligible pairs, the pair costs, and the target \(K\) have been specified. Its design interpretation additionally depends on using a defensible distance and eligibility rule. Pair distances should be based on the intended pre-treatment matching variables; using outcome information to choose the assignment can bias subsequent outcome comparisons. The cost scale and any relative weighting of covariates should reflect the design goal, because minimizing one distance is not the same as minimizing another.
Before interpreting an assignment, check the following:
- Feasibility: Does at least one assignment satisfy all one-to-one, eligibility, and pair-count constraints? If not, the target \(K\) or restrictions need attention.
- Eligibility: Were prohibited pairs actually excluded, and were eligible pairs defined before examining outcomes?
- Cardinality: Is the objective comparing assignments with the same \(K\), or is the matching size being prioritized separately? A smaller total from fewer pairs is not a fair comparison of matching quality.
- Cost definition: Are the distance metric and any weights appropriate for the covariates and scale of the design? A minimum under one cost function need not be a minimum under another.
- Multiple optima: If distinct assignments have the same minimum total, the objective does not choose between them. A tie-breaking rule may be needed, and should be stated rather than treated as a substantive difference in cost.
A low minimum total distance is evidence only that the assignment has a low sum according to the specified pairwise costs among the feasible assignments. It does not guarantee that every covariate is balanced, that the maximum individual pair distance is small, or that a causal effect is identified. Inspecting covariate balance and the matched sample remains important.
How This Objective Differs From Greedy Matching
A greedy nearest-neighbor procedure makes choices sequentially, often selecting a locally nearest available control for the next treated unit. Its result can depend on the order in which treated units are processed. Optimal pair matching instead evaluates assignments jointly against the total-distance objective: a locally less-near pairing may be selected if it permits a smaller total across all \(K\) pairs. The first worked example shows why individual nearest choices can conflict; even when greedy choices do not conflict, a different joint assignment can still have a smaller total.
Optimality is not a universal endorsement over every alternative matching design. A fixed-ratio or variable-ratio design changes the allowable structure, while exact matching or calipers change which pairs are eligible. Comparing methods therefore requires attention to their constraints and target matching size, not just their reported total distances. Assignment algorithms are ways to find a solution to a specified optimization problem; they do not change the meaning of its objective.
Check Your Understanding
Answer each question using the objective and constraints defined above. Brief solutions follow the questions.
- What role does the binary restriction on \(x_{ij}\) play in the formulation?
- Why must \(K\) be fixed, or otherwise accounted for, when minimizing total distance?
- There are two treated units and two controls, all pairs are eligible, and \(K=2\). Distances are \(d_{11}=2,\ d_{12}=5,\ d_{21}=3,\ d_{22}=4\). Which assignment minimizes total distance?
- If a pair is prohibited by a caliper, should it remain in the objective with a very large cost or be excluded from \(E\)?
- Does the minimum-total-distance assignment necessarily minimize the largest distance of any selected pair? Explain.
Solutions. (1) It forces each pair to be either selected (\(x_{ij}=1\)) or not selected (\(x_{ij}=0\)); fractional assignments are not pairs. (2) Without a required pair count or another rule for unmatched units, selecting no pairs gives total distance zero. (3) The assignment \(T_1\to C_1,\ T_2\to C_2\) costs \(2+4=6\); the alternative \(T_1\to C_2,\ T_2\to C_1\) costs \(5+3=8\), so the first is optimal. (4) Exclude it from \(E\), because the caliper makes it ineligible rather than merely costly. (5) No. The objective minimizes the sum, not the largest selected distance; a separate criterion would be needed to minimize the maximum.