Is the set of stable matchings generically small? Ashlagi, Kanoria and Leshno on large random marriage markets

Suppose you have a matching market with two kinds of players, say each player of one kind owns a single left shoe and the other kind each owns a single right shoe, and they can earn $1 by assembling a pair of shoes.  Then if there are more left shoe owners than right shoe owners, the core of the game will give $1 to every right shoe owner and $0 to every left shoe owner. (Here's an old  experiment on such a game.)

The situation is very much less clear if the game isn't played for money, and if the players are not all identical. But in a surprising result, Itai Ashlagi, Yash Kanoria and Jacob Leshno have shown that in a two sided marriage model (in which each man has preferences over all the women and each women over all the men, so agents aren't at all identical), then even a slight imbalance in the sizes of the two sides of the market makes the set of stable matchings very small: Unbalanced random matching markets, by Itai Ashlagi, Yashodhan Kanoria, and Jacob D. Leshno.

"Abstract: We analyze large random matching markets with unequal numbers of men and women. We fi nd that being on the short side of the market confers a large advantage. 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 logn, whereas the

women's average rank of their husbands is at least n/(3 logn). If there are n men and (1 +lamda )n

women for lamda> 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 Omega(n). Simulations show that

our results hold even for small markets."

We already knew that large matching markets have small sets of stable matchings when preference lists are short. This result suggests that small sets of stable matchings may arise for quite different reasons.