Experimental Design for Matching

Technical Summary: Experimental Design for Matching

Problem Statement
Matching mechanisms are critical infrastructure in operations management, spanning education, healthcare, and digital platforms. A fundamental challenge arises when practitioners seek to empirically compare a new matching algorithm (treatment) against a status quo (control) on a finite population. Standard causal inference methods face a unique obstacle in this setting: matching interference. Unlike independent experimental units, assigning a unit to a specific match in the treatment plan may preclude its assignment in the control plan due to capacity and compatibility constraints. Consequently, individual-level counterfactuals are unobservable, and randomization decisions are coupled across units. Existing literature often focuses on mitigating bias within a fixed matching mechanism or assumes specific behavioral models. This paper addresses the gap of how to experimentally compare two predetermined matching plans without imposing outcome or behavioral models, relying solely on a design-based perspective.

Methodology
The authors propose the Alternating Path Randomized Design (AP Design), a framework grounded in graph theory and design-based inference.

1. Disagreement Set and Decomposition:
   The core structural insight is the definition of the disagreement set ($\Delta M_{(t,c)}$), comprising match pairs present in exactly one of the two plans (treatment or control). The paper proves that for one-to-one matchings, this set admits a unique decomposition into disjoint alternating paths and cycles. In these structures, edges alternate between the treatment matching ($M_t$) and the control matching ($M_c$). Due to capacity constraints, adjacent edges in an alternating path or cycle cannot be simultaneously realized.

2. Randomization Scheme:
   The AP Design performs sequential randomization along these paths and cycles.

   • Path Case: For an open path, the first edge is selected with probability $p/(1+p)$. Subsequent edges are selected with conditional probability $p$ if the predecessor was not selected; otherwise, the edge is deterministically skipped (probability 0).
   • Cycle Case: Similar sequential rules apply, with the final edge determined deterministically based on the realization of the first and penultimate edges to ensure feasibility.
   • Independence: Randomization is performed independently across different paths and cycles.

3. Estimation:
   The authors utilize the Horvitz-Thompson estimator to estimate the Average Treatment Effect (ATE). They establish the unbiasedness of this estimator under the AP design.

4. Optimization (Minimax Framework):
   To optimize efficiency, the authors analyze the worst-case variance of the estimator under a bounded potential outcome assumption. They formulate a minimax problem to find the optimal conditional randomization probability $p$.

   • Asymptotic Result: For long paths and cycles, the optimal $p$ converges to $\sqrt{2} - 1 \approx 0.4142$. This value is strictly less than 0.5, reflecting a trade-off where reducing the variance contribution of the current edge requires accounting for downstream interference.

5. Many-to-One Extension:
   The framework is extended to many-to-one matchings (e.g., student-school assignments), where capacity constraints complicate the decomposition. The authors construct an auxiliary unbalanced directed graph to represent the disagreement set. They reduce the problem of finding a feasible decomposition to two graph-theoretic tasks:

   • Finding augmenting paths in a constructed flow network to handle imbalances in node degrees.
   • Performing Euler-tour decompositions on the residual balanced graph.
     This ensures the resulting alternating paths and cycles satisfy capacity constraints, allowing the AP design and inference guarantees to carry over.

Key Results

• Unbiasedness: The Horvitz-Thompson estimator under the AP design is unbiased for the ATE.
• Variance Scaling: Unlike naive designs (which select the entire treatment or control matching with probability 0.5), where variance does not vanish as population size $N \to \infty$, the variance of the AP estimator decreases at a rate of $O(1/N)$.
• Central Limit Theorem (CLT): The paper establishes a finite-population CLT for the estimator. This result is non-trivial because the decomposition of the disagreement set can exhibit complex, heterogeneous, and potentially unstable patterns (mixtures of short and long components) as the population grows. The proof combines Lindeberg-Feller arguments with $\alpha$-mixing techniques and the Bolzano-Weierstrass theorem.
• Variance Bounds: The authors derive an estimable upper bound for the variance that relies only on observable quantities, enabling the construction of asymptotic confidence intervals.
• Numerical Validation: Using a workforce dataset (Revelio Labs), numerical experiments confirm that the AP design significantly outperforms the naive design in terms of variance reduction. The empirical distribution of the estimator aligns with the standard normal distribution, validating the CLT. The empirically optimal $p$ ($\approx 0.417$) closely matches the theoretical worst-case optimum ($\sqrt{2}-1$).

Significance and Claims
The paper claims to provide a design-based, assumption-free framework for testing matching mechanisms. Its significance lies in:

1. Addressing Matching Interference: It offers a principled solution to the specific interference problem inherent in matching markets, where units are not independent.
2. Structural Innovation: The unique decomposition of the disagreement set into alternating paths and cycles provides a rigorous structural basis for managing interference.
3. Robust Inference: By establishing a CLT that accommodates unstable and heterogeneous component structures, the work enables valid asymptotic inference in complex matching environments without requiring outcome models.
4. Practical Applicability: The extension to many-to-one matchings via graph-theoretic tools (augmenting paths and Euler tours) makes the methodology applicable to real-world scenarios with capacity constraints, such as organ exchange and school choice.

The authors position this work as a complementary perspective to structural modeling, offering a direct empirical testing ground for new matching algorithms against status quos in operations management and platform design.