Why Represent Full Matching as a Network?
Full matching groups every treated unit with at least one control and every control with at least one treated unit. A matched set can therefore contain different numbers of treated and control units. The network view makes the possible links explicit: it records which cross-treatment comparisons are permitted, what they cost, and how a collection of links can assemble all units into matched sets.
The graph is a design representation, not evidence that treatment caused an outcome difference. A low-cost allocation means that the selected links have low cost under the chosen distance measure. It does not by itself establish exchangeability, adequate overlap for a causal estimand, or balance on every relevant covariate. As in other matching methods, the distance and allowable links should be based on pretreatment information and on the study's design goals.
Nodes, Edges, Capacities, and Costs
Write a potential edge as \((t,c)\), where \(t\in T\) and \(c\in C\). Its cost \(d_{tc}\) is a specified dissimilarity, such as an absolute difference in estimated propensity scores or a distance based on covariates. The cost is not necessarily a literal monetary expense. It is a numerical criterion for preferring some allowable links over others. For a given edge list, define \(x_{tc}=1\) if the edge is selected and \(x_{tc}=0\) otherwise.
A unit is one node, not a supply of interchangeable copies. In a full match, each unit belongs to exactly one subclass. Several links may touch the same node within its subclass, but this does not mean that the unit is replicated as a separate observation. The graph's connected components determine membership; the analysis must later account for the resulting subclass structure when estimating effects and uncertainty.
An allowable edge can be assigned capacity one, \(x_{tc}\leq 1\), so the same pair is not selected repeatedly. This is different from limiting a node to degree one. A node's degree is the number of selected edges incident to it; full matching permits degree greater than one, which is essential when a subclass has multiple units from one treatment group. Every node must have degree at least one so that it is not left unmatched.
One precise network-optimization formulation chooses a forest of allowable edges. Here, a forest is a graph with no cycles. For each subset \(U\) of nodes, the selected-edge variables satisfy the acyclicity constraint \(\sum_{(t,c)\in E(U)}x_{tc}\leq |U|-1\), where \(E(U)\) consists of allowable edges whose two endpoints are in \(U\). The coverage constraint is \(\sum_{e\text{ incident to }i}x_e\geq1\) for every unit \(i\). These conditions, together with binary \(x_e\), ensure that each node is included and that selected components have no cycles.
Because every selected edge joins opposite groups, every connected component with an edge contains both treated and control nodes. The coverage constraint rules out isolated nodes, so the components are all valid matched subclasses. In this formulation, the objective minimizes the total cost of selected links. It is one clear network-based objective, not a universal definition of the cost of a full match: other formulations may score a subclass differently.
Why the Forest Represents Matched Sets
The key graph fact is that any connected component on \(m\) nodes can be represented by a tree with \(m-1\) edges. Starting from any connected set of selected links, remove an edge from a cycle: the remaining links still connect the component. Repeating this operation leaves a connected, cycle-free set of links. Thus a subclass can be represented by a tree without changing which units belong together.
Conversely, the connected components of any selected forest partition the units: no node lies in two components, and every covered node belongs to one component. Since the graph is bipartite and all selected edges cross between treatment groups, each non-isolated component contains at least one treated and one control. Together with the coverage constraint, this gives the defining structure of full matching.
The objective sums the costs of the tree links used to connect a subclass. It does not sum every treated-control pairwise distance within that subclass. For instance, a subclass with three treated units and two controls can be connected by four selected edges, not by all six possible cross-group pairs. This distinction matters when interpreting an optimizer's output: it minimizes the stated link objective, not every conceivable measure of within-subclass dissimilarity.
Worked Example: Reading a Small Allowable-Edge Network
Suppose there are treated units \(T_1,T_2\) and control units \(C_1,C_2\). The allowable edges are \((T_1,C_1)\), \((T_2,C_1)\), and \((T_2,C_2)\). There is no edge between \(T_1\) and \(C_2\), and \(C_2\) is connected only to \(T_2\). Assume all three edges are selected.
The selected graph is the path \(C_1-T_1\) only if an edge \((T_1,C_1)\) is connected to \(T_2\); in this network, that connection is \((T_2,C_1)\). Including all selected links gives the connected component \(\{T_1,T_2,C_1,C_2\}\), with edges \(T_1-C_1\), \(T_2-C_1\), and \(T_2-C_2\). Each of the four units is covered, and the component contains both treatment groups, so it is one valid matched subclass.
There are four nodes and three selected edges. The component is connected and has no cycle, consistent with the tree count \(m-1=4-1=3\). If the edge \((T_2,C_1)\) were removed, the graph would split into \(\{T_1,C_1\}\) and \(\{T_2,C_2\}\), two valid subclasses. Removing \((T_1,C_1)\), by contrast, would leave \(T_1\) isolated, violating coverage.
Worked Cost Optimization
Consider three treated units \(T_1,T_2,T_3\) and two controls \(C_1,C_2\). Suppose the allowable edges and costs are as follows. These hypothetical costs are in arbitrary distance units.
| Edge | Cost \(d_{tc}\) |
|---|---|
| \((T_1,C_1)\) | 0.20 |
| \((T_2,C_1)\) | 0.40 |
| \((T_2,C_2)\) | 0.30 |
| \((T_3,C_2)\) | 0.10 |
Worked Example: Comparing Two Full-Matching Forests
One feasible forest selects all four edges. It forms the connected component \(\{T_1,T_2,T_3,C_1,C_2\}\), so every unit is covered and the component is mixed. Its total selected-link cost is
Another feasible forest selects \((T_1,C_1)\), \((T_2,C_1)\), and \((T_3,C_2)\). It gives the subclasses \(\{T_1,T_2,C_1\}\) and \(\{T_3,C_2\}\); every node still has an edge, and each component contains both groups. Its cost is
The second forest is preferred under the stated objective because \(0.70<1.00\). The comparison does not establish that it is best under every possible full-matching criterion; it establishes that it has lower total selected-link cost for these edge costs. In this example, the second forest is feasible but not optimal: \(T_1\) can only connect through \(C_1\), and \(T_3\) can only connect through \(C_2\). Those two edges are required. Covering \(T_2\) then requires either \((T_2,C_1)\), cost \(0.40\), or \((T_2,C_2)\), cost \(0.30\). Choosing the latter gives a feasible forest of cost \(0.60\), with subclasses \(\{T_1,C_1\}\) and \(\{T_2,T_3,C_2\}\), and is in fact cheaper than the proposed \(0.70\) forest. Its arithmetic is \(0.20+0.30+0.10=0.60\), so it is the minimum among these possibilities.
Where Flow Enters—and What It Does Not Guarantee
A network is a graph on which flow algorithms can be used, but a full-matching problem is not automatically the ordinary one-to-one assignment problem. In one-to-one assignment, each treated node and each control node can be used at most once, and the chosen pairs are the matched units. Imposing degree at most one on every node here would prevent subclasses with more than two units. Conversely, simply sending a fixed amount of flow from a source through treated nodes to controls can assign treated units to controls without ensuring that every control is included or that the resulting components have the intended subclass structure.
The selected-edge formulation above makes the structural requirements explicit: every unit is covered, edges are allowable, components are mixed, and the objective is stated. Flow-based algorithms or integer network-optimization routines can be used to solve related formulations, but the constraints must match the desired full-matching definition. When a software implementation uses a different cost or flow construction, inspect its documentation rather than assuming it minimizes the sum of all pairwise distances.
Capacities also need an explicit interpretation. An edge capacity of one prevents repeated selection of the same pair; it does not limit how many distinct links can touch a unit. A capacity that limits the degree of a treated or control node changes the feasible subclass sizes. Such restrictions can be useful design choices, but they are not implied by the basic network representation described here.
Worked Example: Checking Feasibility Before Optimization
Suppose the candidate network has treated nodes \(T_1,T_2\), controls \(C_1,C_2\), and only two allowable edges: \((T_1,C_1)\) and \((T_2,C_1)\). Control \(C_2\) has no allowable edge.
The coverage condition for \(C_2\) would require \(\sum_{e\text{ incident to }C_2}x_e\geq1\). But the sum contains no terms and equals zero, so the condition cannot be met. The network has no feasible full matching using these allowable edges, regardless of the edge costs.
The appropriate response is to diagnose why \(C_2\) has no permitted partner—for example, a strict design restriction may have excluded all its cross-group links. The analyst must then make and report a design decision, such as revising the allowable links if justified or changing the target set of units. Silently dropping \(C_2\) would no longer be a full match of the original set of units.
Diagnostics, Alternatives, and Limitations
Before accepting a solution, check the graph and the resulting components. Useful diagnostics include:
- Isolated nodes: any node with no allowable edge makes full coverage impossible.
- Component composition: every reported subclass must include at least one treated and one control unit.
- Edge validity: confirm that every selected pair satisfies the restrictions used to construct \(E\).
- Capacity and degree: check whether the implementation has accidentally imposed one-to-one matching or another unintended degree limit.
- Objective agreement: verify that the reported cost matches the stated definition—for example, selected-edge cost rather than all within-subclass pairwise distances.
- Substantive balance: low graph cost is not a substitute for assessing covariate balance and overlap after matching.
Nearest-neighbor matching makes sequential partner choices, while optimal pair matching searches for a globally low-cost set of pairs under its one-to-one structure. Full matching allows groups of varying sizes, so it can retain units that cannot be arranged as isolated pairs. These approaches answer different design questions; none guarantees good balance merely because its algorithm has optimized a distance. Full matching can also produce subclasses with very different sizes, and its result depends on the allowable-edge rules, chosen distance, objective, and any imposed capacities.
A further limitation is that a selected forest's total cost depends on the link representation. Two solutions that produce similar subclasses can have different tree links and therefore different costs. The total is interpretable only alongside the rule used to construct and cost those links. Matching is a design step: causal interpretation still depends on the study's assumptions and on appropriate estimation and uncertainty procedures for the matched data.
Check Your Understanding
Answer each question, then compare with the solutions below.
- Why does an edge capacity of one not mean that a unit can have only one matching partner?
- A selected component has two treated nodes and three control nodes, and is connected without cycles. How many selected edges does it have?
- In the worked cost example, what is the cost of selecting \((T_1,C_1)\), \((T_2,C_2)\), and \((T_3,C_2)\)? Is the result a valid forest full match?
- Why does a control node with no allowable edges make full coverage infeasible?
- What does minimizing the sum of selected-edge costs guarantee, and what does it not guarantee about covariate balance?
Solutions. (1) It limits repetition of a particular treated-control edge. Several different edges may still meet at the same node, allowing that unit to share a subclass with multiple opposite-group units. (2) There are five nodes, so a connected acyclic component has \(5-1=4\) edges. (3) The cost is \(0.20+0.30+0.10=0.60\). The edges form two components, \(\{T_1,C_1\}\) and \(\{T_2,T_3,C_2\}\), each mixed and connected without a cycle, so this is a valid forest full match. (4) Coverage requires at least one selected incident edge for every node, which is impossible when the node has no allowable incident edge. (5) It guarantees the minimum value of the specified objective among feasible solutions. It does not guarantee balance on all covariates or causal validity; balance and the study assumptions require separate assessment.