On the Social Welfare of Mechanisms for Repeated Batch Matching

Elliot Anshelevich, Meenal Chhabra, Sanmay Das, Matthew GerriorAAAI 2013 · DOI

Abstract

In repeated matching markets such as kidney exchanges or job boards, maximizing social welfare within a single round—a myopic approach—often degrades long-term outcomes. This paper demonstrates that a "greedy" matching mechanism can outperform "max-weight" matching over time by naturally encouraging agents with low-quality potential matches to wait for better future opportunities. We propose a threshold-based strategy that calculates an optimal "reservation value" for agents, significantly boosting overall social welfare.

Introduction

Many real-world markets operate in a hybrid online-batch mode: agents arrive continuously, but matching occurs in periodic rounds. Standard matching theory often focuses on either one-shot batches or pure online arrivals. However, a mechanism that is optimal for a single round may be suboptimal in the long run because it fails to account for the "option value" of waiting. Matching two agents with low compatibility today prevents them from finding a much better match in a subsequent round. This study seeks to understand how standard mechanisms perform over multiple rounds and how to design strategies that account for the benefits of waiting.

Methods

The researchers model the market as a dynamic graph where nodes (agents) arrive over time and edges represent match utility. They compare several mechanisms:

  1. Greedy: Matches the highest-weight pairs first until no more matches can be made.
  2. Max-Weight: Finds the set of matches that maximizes the total utility for the current round.
  3. Thresholding (The Proposal): Agents calculate a reservation value ($t^*$) using a modified Bellman equation. If a potential match's utility is below this threshold, the agent rejects it to wait for the next round.

A key theoretical contribution is the "well-mixed assumption," which posits that in a long-running system, the expected number of unmatched agents of each type remains constant, allowing for the calculation of stable optimal thresholds.

Key Results

Simulations across various utility distributions (Uniform, Exponential, Lognormal) reveal that the Max-Weight mechanism is often "too efficient" at clearing low-quality pairs, whereas Greedy naturally protects high-quality nodes.

Figure 1: Utility of Agent 1 as a function of its threshold. The vertical line represents the calculated optimal threshold, which maximizes utility regardless of other agents' strategies.

As shown in Figure 1, the calculated threshold accurately identifies the point of maximum utility. Furthermore, applying this threshold significantly improves the competitive ratio—the ratio of achieved social welfare to the offline optimal.

Figure 4: Competitive ratio vs. threshold for lognormal utility distributions. The thresholding strategy improves the ratio from approximately 0.4 to 0.75.

In lognormal simulations (Figure 4), the competitive ratio nearly doubles when the optimal threshold is applied. In a stylized kidney exchange model based on real-world medical data, this thresholding mechanism achieved a 15% increase in social welfare compared to a system with no thresholds. One of the most striking findings is that if the right threshold is set to prune low-quality edges, the specific matching algorithm used afterward matters very little; the "waiting" strategy does the heavy lifting for social welfare.

Conclusion

This research highlights that myopic optimization in dynamic matching markets is counterproductive. By implementing threshold-based strategies, markets can significantly improve long-term social welfare. Future work will explore non-stationary arrival processes and the impact of strategic agent behavior on these thresholds.

Summary updated

BibTeX
@inproceedings{anshelevich2013social,
  author = {Elliot Anshelevich and Meenal Chhabra and Sanmay Das and Matthew Gerrior},
  title = {{On the Social Welfare of Mechanisms for Repeated Batch Matching}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8666},
}
Figure