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:
- Greedy: Matches the highest-weight pairs first until no more matches can be made.
- Max-Weight: Finds the set of matches that maximizes the total utility for the current round.
- 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.
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.
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