Opting Into Optimal Matchings

Avrim Blum, Ioannis Caragiannis, Nika Haghtalab, Ariel D. Procaccia, Eviatar B. Procaccia, Rohit Vaish

Abstract: We revisit the problem of designing optimal, individually rational matching mechanisms (in a general sense, allowing for cycles in directed graphs), where each player — who is associated with a subset of vertices — matches as many of his own vertices when he opts into the matching mechanism as when he opts out. We offer a new perspective on this problem by considering an arbitrary graph, but assuming that vertices are associated with players at random. Our main result asserts that, under certain conditions, any fixed optimal matching is likely to be individually rational up to lower-order terms. We also show that a simple and practical mechanism is (fully) individually rational, and likely to be optimal up to lower-order terms. We discuss the implications of our results for market design in general, and kidney exchange in particular.

Introduction

In kidney exchange markets, hospitals often face a strategic dilemma: joining a large national pool promises greater overall efficiency but risks reducing the number of internal matches for their own patients. This tension between global efficiency and individual rationality (IR) is a central challenge in market design. If a hospital can match ten of its own pairs internally but a global algorithm only matches eight to prioritize a larger total, the hospital is incentivized to "opt out."

Previous theoretical work suggested this conflict was significant, showing that in worst-case scenarios, a global optimum could be half as large as a matching respecting IR constraints. This paper investigates whether this theoretical hurdle manifests in practice by moving beyond worst-case analysis to a random assignment model.

Methodology and the Random Assignment Model

The authors propose a model where the compatibility graph is arbitrary, but each patient-donor pair is assigned to a hospital $i$ with a certain probability $p_i$. This reflects a reality where medical traits, rather than geography, primarily determine compatibility.

A directed compatibility graph where vertices are assigned to two players (red and blue). Cycles can involve vertices from multiple players, creating the tension between local and global optimization.

To analyze this model, the researchers utilize several mathematical frameworks:

  • Edmonds-Gallai Decomposition: This graph-theoretic tool decomposes matchings into components, facilitating the proof that a hospital's expected share of a global matching typically meets or exceeds its best internal matching.
  • Concentration Inequalities: Using self-bounding functions from probability theory, the authors demonstrate that the actual number of matches a hospital receives rarely deviates significantly from the expected average.
  • Veto Mechanism: A practical solution is proposed where a global optimum is computed, but if any hospital is disadvantaged, the system reverts to internal matchings.

The study relies on synthetic graph constructions, such as "star" graphs and layered networks, to establish tight mathematical bounds rather than empirical datasets.

Key Insights

The core finding is that randomness acts as a peacemaker. While one can construct adversarial graphs where IR fails, such configurations are highly improbable when vertices are distributed randomly. If medical characteristics determine a node's position in the graph, no single hospital is likely to "own" all high-value nodes.

Furthermore, the authors identify a "Lower-Order" Loophole. The discrepancy between a hospital's internal matching and its global share is shown to be $O(\sqrt{n})$. As the exchange size $n$ grows, this gap becomes a negligible fraction of the total matches. The paper also provides the first rigorous proof that IR holds even when complex 3-way cycles are permitted, which are more efficient than simple 2-way swaps but harder to analyze.

Results and Practical Implications

The research yields several key results:

  1. Theorem 2.2: In an arbitrary graph with random vertex assignment, any fixed maximum matching is likely to be individually rational for every player, up to a small error term of $O(\sqrt{|opt(G)| \cdot \ln(k/\delta)})$.
  2. The Veto Mechanism: This mechanism is shown to be nearly optimal while guaranteeing full individual rationality.
  3. Cycle Length Limits: The breakdown of IR when cycles are unrestricted justifies the current clinical practice of limiting exchange cycles to short lengths (e.g., 2 or 3).

Limitations and Future Work

The current proofs assume that no single hospital controls more than half of the patients ($p \le 1/2$), a condition that may not hold in regional exchanges dominated by a single large center. Additionally, the results are most robust when $1/p_i$ is an integer, requiring potential "rounding" in practical applications. Future research is needed to address "incentive compatibility"—the risk of hospitals hiding easy-to-match patients to maximize their own outcomes while offloading difficult cases to the pool.

Summary updated

Abstract

We revisit the problem of designing optimal, individually rational matching mechanisms (in a general sense, allowing for cycles in directed graphs), where each player --- who is associated with a subset of vertices --- matches as many of his own vertices when he opts into the matching mechanism as when he opts out. We offer a new perspective on this problem by considering an arbitrary graph, but assuming that vertices are associated with players at random. Our main result asserts that, under certain conditions, any fixed optimal matching is likely to be individually rational up to lower-order terms. We also show that a simple and practical mechanism is (fully) individually rational, and likely to be optimal up to lower-order terms. We discuss the implications of our results for market design in general, and kidney exchange in particular.
BibTeX
@inproceedings{blum2017opting,
  author = {Avrim Blum and Ioannis Caragiannis and Nika Haghtalab and Ariel D. Procaccia and Eviatar B. Procaccia and Rohit Vaish},
  title = {{Opting Into Optimal Matchings}},
  booktitle = {SODA},
  year = {2017},
  doi = {10.1137/1.9781611974782.155},
}
Figure