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.
