Introduction
Matching markets, such as college admissions, labor markets, and online dating, are fundamental to modern socio-economic interactions. Historically, economic theory has analyzed these markets under the assumption that participant preferences are known a priori. Conversely, machine learning research has focused on preference learning but often ignores the physical constraints of scarcity and competition. This paper bridges these two fields by introducing a framework for decentralized matching where agents must learn preferences from data while navigating the risks of over-enrollment and competition.
The Problem: Matching Under Uncertainty
In a decentralized matching market, agents (e.g., colleges) compete for arms (e.g., students). Each agent faces a capacity constraint and a penalty for exceeding it. Because agents do not know the private preferences of the arms or the strategies of their competitors, they face a significant challenge: sending too few offers results in under-enrollment, while sending too many leads to costly over-enrollment.
The authors address this by modeling the market using a Latent Utility Model. In this model, an arm's value to an agent is composed of a public "systematic score" (objective metrics) and a private "idiosyncratic fit" (subjective quality). The goal is to develop a strategy that maximizes utility while ensuring the resulting matches are stable and fair.
Methodology: Calibrated Decentralized Matching (CDM)
To solve the decentralized matching problem, the authors propose the Calibrated Decentralized Matching (CDM) algorithm, which consists of two primary technical components:
- Preference Learning via RKHS: Agents estimate the probability that an arm will accept an offer using a penalized log-likelihood method within a Reproducing Kernel Hilbert Space (RKHS). This approach allows agents to learn from historical binary choice data (accept/reject) without needing to observe the private strategies of their competitors.
- Cutoff-Based Decision Making: Since finding the absolute optimal set of offers is NP-complete, CDM utilizes a smart cutoff strategy. The algorithm calibrates the "state of the world"—effectively the expected level of competition—by balancing the marginal utility of a successful match against the marginal penalty of exceeding the enrollment quota.
Key Theoretical and Empirical Insights
The paper provides several critical guarantees regarding the behavior of agents using CDM:
- Incentive Compatibility: The authors prove that as the amount of available data increases, CDM becomes incentive-compatible. This means that agents are best served by acting straightforwardly based on their true preferences rather than attempting to strategically "game" the system by targeting lower-tier candidates.
- Fairness and Stability: Strategic targeting in competitive markets often leads to "justified envy," where a qualified candidate is rejected while a less qualified one is accepted elsewhere. CDM eliminates this by relying on calibrated, straightforward behavior, ensuring that the final matching is both fair and stable.
- Robustness to Penalties: In simulations, CDM demonstrated superior performance compared to "greedy" or "simple cutoff" strategies. While naive baselines degrade rapidly as the penalty for over-enrollment increases, CDM successfully balances risk to maintain high payoffs.
Evaluation
The framework was evaluated using a combination of synthetic and real-world datasets:
- Simulated Markets: Testing across varying agent-to-arm ratios and penalty levels.
- Graduate Admissions Simulation: A tiered competition involving 50 colleges and up to 300 students.
- Real-World Data: Analysis of U.S. College Admissions data (2015–2017) sourced from the New York Times, focusing on admission yields for 37 institutions.
Across all experiments, CDM consistently yielded higher agent payoffs and more stable matches than traditional decentralized approaches, particularly in highly competitive environments.
Limitations and Future Directions
While CDM represents a significant step forward, the authors identify several areas for future research. The current model is limited to single-stage interactions, whereas real-world markets often involve multiple stages (e.g., waitlists). Additionally, the model assumes agents evaluate candidates independently, leaving room for future work to explore "complementary preferences," where an agent seeks a specific mix of candidates rather than just the highest-rated individuals. Finally, extending the framework to handle ties and indifference remains an open challenge.
Summary updated