A new randomized-design lets researchers compare rival matching algorithms by randomizing only over the disagreement graph, delivering unbiased estimates and an inferential CLT; for long alternating paths the minimax-optimal randomization probability approaches √2−1.

Main Finding

The paper develops a principled, design-based randomized-experiment method to compare two predetermined matching plans on the same finite population. Key contributions are (i) a graph-theoretic characterization of where randomization is needed (the disagreement set) and its unique decomposition into disjoint alternating paths and cycles, (ii) the Alternating Path Randomized (AP) Design that sequentially randomizes along those components to respect matching feasibility, (iii) a minimax optimization of the conditional randomization probability that for long paths converges to √2 − 1 ≈ 0.4142, and (iv) design-based inference results (Horvitz–Thompson unbiasedness and a new finite-population CLT) that accommodate highly heterogeneous and unstable path/cycle structures. The paper also extends the design and inference to many-to-one matchings by constructing admissible alternating decompositions via augmenting-path and Euler-tour / flow-network constructions on an auxiliary directed graph.

Key Points

• Problem setup
  • Two fixed matchings on the same 2N agents: treatment matching Mt and control matching Mc.
  • Estimand: average treatment effect τ = Ȳt − Ȳc where Ȳt, Ȳc are average realized pair outcomes under Mt and Mc.
  • Matching interference: an agent cannot realize both partners, and selecting one match can preclude other matches, coupling randomization decisions across units.
• Disagreement set and decomposition
  • Disagreement set ΔM(t,c) = (Mt ∪ Mc) \ (Mt ∩ Mc) contains exactly the pairs that differ between matchings.
  • For one-to-one matchings, ΔM(t,c) uniquely decomposes into vertex-disjoint alternating paths and cycles (edges alternate between Mt-only and Mc-only).
  • Alternating cycles have even length ≥ 4.
• Alternating Path Randomized (AP) Design (one-to-one case)
  • Randomize independently across alternating components.
  • Along a path: sequentially decide whether to realize each edge; adjacent edges cannot both be realized. Initial edge has selection probability p/(1+p); for later edges, conditional selection probability is p given the predecessor was not selected, and zero if predecessor was selected.
  • For cycles: similar sequential rules, with a deterministic rule for the final edge conditional on neighbors to preserve feasibility.
• Optimization and variance
  • Using a minimax criterion, the paper chooses the conditional selection probability p to minimize worst-case variance. For long paths, the minimax-optimal p → √2 − 1 (≈ 0.4142), strictly below 0.5.
  • AP design reduces variance relative to naive “flip between full matchings” designs which have non-vanishing variance and only two possible outcomes.
• Estimation and inference
  • Uses a Horvitz–Thompson estimator adapted to the randomization probabilities; estimator is unbiased under the design.
  • Proves a finite-population central limit theorem for the estimator under AP design. The CLT handles heterogeneous and unstable component structures (many short components, a few long components, or mixtures), via a blend of Lindeberg–Feller and α-mixing arguments plus subsequence/Bolzano–Weierstrass reasoning.
• Many-to-one extension
  • In many-to-one matchings (capacity constraints), the alternating decomposition is not unique and many decompositions violate feasibility.
  • The paper provides sufficient conditions for admissible decompositions and a constructive reduction to graph problems: find augmenting paths and Euler-tour decompositions on an auxiliary unbalanced directed graph and associated flow network. This yields feasible alternating path/cycle decompositions so AP design and inference carry over.

Data & Methods

• Framework: finite-population, design-based causal inference — potential outcomes Y_{i,j} are fixed and randomness comes only from experimenter-controlled randomization.
• Graph-theoretic modeling: disagreement set as an undirected graph; use connected-component analysis to obtain unique alternating path/cycle decomposition in the one-to-one case.
• Randomization protocol: sequential, conditional Bernoulli rules along components (AP design); explicit probability rules for path vs cycle endpoints.
• Optimization: minimax variance analysis to pick conditional probability p; analytical asymptotics show convergence p → √2 − 1 for long components.
• Estimation: Horvitz–Thompson-style unbiased estimator that accounts for selection probabilities.
• Asymptotics/proofs: a novel finite-population CLT tailored to dependent, structured randomization. Proof techniques mix classical Lindeberg–Feller CLT ideas with α-mixing controls, and use subsequence compactness (Bolzano–Weierstrass) to accommodate sequences with unstable component structure.
• Many-to-one technical tools: augmenting path algorithms, Euler-tour decompositions, and flow-network constructions on auxiliary directed graphs to find admissible alternating decompositions consistent with capacities.

Implications for AI Economics

• Robust, model-free evaluation of algorithmic matchers: The design-based AP approach enables A/B testing of ML-driven matching algorithms (e.g., recommendation-to-match systems, matching with new feature sets, policy changes to matching rules) without relying on behavioral or outcome models that may be misspecified when testing the matching mechanism itself.
• Practical guidance for platform experiments: The structural decomposition (disagreement set → alternating components) gives a recipe — compute the symmetric difference between old and new matchings, decompose, and randomize along components using the AP rules with p calibrated near √2 − 1 when components are long — that reduces worst-case variance and allows valid inference.
• Better statistical power than naive switches: Compared with flipping the entire platform between two matchings (high, non-vanishing variance), AP design concentrates randomization on differing pairs and limits interference, yielding more informative experiments as population size grows.
• Applicability across market types: The method handles one-to-one settings (dating, pairwise games, bilaterally matched marketplaces) and extends to many-to-one settings (school seats, job slots) via graph/flow constructions, making it broadly relevant to platform decision-making and welfare evaluations.
• Decision-making under uncertainty: Because the paper gives an unbiased estimator and an asymptotic normal distribution under realistic and nonrestrictive structural conditions, platform operators and policy analysts can form confidence intervals and hypothesis tests for the average effect of adopting a new matching rule — useful for cost–benefit assessments of deploying new ML features.
• Operational considerations and limitations
  • Requires computing both matchings and the disagreement graph before experimentation; implementation needs graph decomposition and (for many-to-one) some flow/augmenting-path computations.
  • The framework compares two fixed matchings (not the space of all possible randomized matchers or adaptive mechanisms). It is design-based and hence intentionally agnostic to behavioral response models; if strategic behavior or equilibrium feedback is a concern, further modeling would be needed.
  • The minimax-optimal p is derived for worst-case variance; practitioners may adjust p if they have prior knowledge about outcomes or component lengths.

Overall, the paper supplies a principled, implementable experimental design and inference toolbox for evaluating competing matching algorithms under realistic feasibility constraints and interference — a directly applicable contribution for economists and platform designers testing ML-driven matching changes.