Test of Time Award 2023 to Immorlica & Mahdian, and Ashlagi, Kanoria & Leshno

 Matching theory is recognized this year for bringing theory and observation into harmony...

The SigEcom Test of Time Award for 2023, "… for explaining an apparent gap between the theory and practice of matching markets and helping us understand why small cores are so common." goes to two papers, by five authors.

The first of the two papers is

Marriage, honesty, and stability by Nicole Immorlica and Mohammad Mahdian, Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 53–62.

ABSTRACT: Many centralized two-sided markets form a matching between participants by running a stable marriage algorithm. It is a well-known fact that no matching mechanism based on a stable marriage algorithm can guarantee truthfulness as a dominant strategy for participants. However, as we will show in this paper, in a probabilistic setting where the preference lists of one side of the market are composed of only a constant (independent of the the size of the market) number of entries, each drawn from an arbitrary distribution, the number of participants that have more than one stable partner is vanishingly small. This proves (and generalizes) a conjecture of Roth and Peranson [23]. As a corollary of this result, we show that, with high probability, the truthful strategy is the best response for a given player when the other players are truthful. We also analyze equilibria of the deferred acceptance stable marriage game. We show that the game with complete information has an equilibrium in which a (1 - o(1)) fraction of the strategies are truthful in expectation. In the more realistic setting of a game of incomplete information, we will show that the set of truthful strategies form a (1 + o(1))-approximate Bayesian-Nash equilibrium. Our results have implications in many practical settings and were inspired by the work of Roth and Peranson [23] on the National Residency Matching Program.

**

And the second of the two papers is

Unbalanced random matching markets, by Itai Ashlagi, Yashodhan Kanoria, Jacob D. Leshno, Proceedings of the 14th ACM Conference on Electronic Commerce (EC), 2013, pp. 27–28.

ABSTRACT: We analyze large random matching markets with unequal numbers of men and women. Agents have complete preference lists that are uniformly random and independent, and we consider stable matchings under the realized preferences. We find that being on the short side of the market confers a large advantage.

"We characterize the men's average rank of their wives. For each agent, assign a rank of 1 to the agent's most preferred partner, a rank of 2 to the next most preferred partner and so forth. If there are n men and n+1 women then, we show that with high probability, in any stable matching, the men's average rank of their wives is no more than 3 log n, whereas the women's average rank of their husbands is at least n(3 log n). If there are n men and (1+λ)n women for λ0 then, with high probability, in any stable matching the men's average rank of wives is O(1), whereas the women's average rank of husbands is λ (n).

"Moreover, we find that in each case, whp, the number of agents who have multiple stable partners is o(n). Thus our results imply a limited scope for manipulation in unbalanced random matching markets for mechanisms that implement a stable match.

"These results are in stark contrast with previously known results for random matching markets with an equal number of men and women. In such balanced random matching markets, the lattice of stable matches is large, with the two extreme points of the lattice, the men optimal stable match (MOSM) and the women optimal stable match (WOSM) possessing contrasting properties. The men's average rank of their wives is just log n under the MOSM, but as large as n/log n under the WOSM, and the opposite holds for the women's average rank of their husbands. Thus, the proposing side in the Gale-Shapley deferred acceptance algorithm is greatly advantaged in a balanced market, whereas we prove that in markets with even a slight imbalance, the MOSM and WOSM are almost identical. This reveals the balanced case to be a knife edge.

"Our proof uses an algorithm which calculates the WOSM from the MOSM through a sequence of proposals by men. A woman improves if, by divorcing her husband, she triggers a rejection chain that results in a proposal back to her from a more preferred man. The algorithm lends itself to a stochastic analysis, in which we show that most rejection chains are likely to end in a proposal to an unmatched woman. Simulations show that our results hold even for small markets."

***

see also the longer version of Ashlagi, Kanoria and Leshno (with shorter abstract) in the JPE in 2017 (too recent for the test of time award itself:)

Ashlagi, Itai, Yash Kanoria, and Jacob D. Leshno. "Unbalanced random matching markets: The stark effect of competition." Journal of Political Economy 125, no. 1 (2017): 69-98.

Abstract: We study competition in matching markets with random heterogeneous preferences and an unequal number of agents on either side. First, we show that even the slightest imbalance yields an essentially unique stable matching. Second, we give a tight description of stable outcomes, showing that matching markets are extremely competitive. Each agent on the short side of the market is matched with one of his top choices, and each agent on the long side either is unmatched or does almost no better than being matched with a random partner. Our results suggest that any matching market is likely to have a small core, explaining why small cores are empirically ubiquitous.