This is a corrected version of an earlier post. A commenter (see below) spotted a mistake in the earlier post. I had thought that A (Walkup’s Theorem) implied B (perfect matchings are almost stable). A is certainly true, and B is also true but at least the way I formulated it the implication did not follow. I mark the error with an asterisk below.
A forgotten gem in matching theory is David Walkup’s theorem about perfect matchings in random regular bipartite graphs (Discrete Math, 1980). Let be the set of girl vertices, the set of boy vertices and suppose that . Have each boy vertex choose two girl vertices at random and each boy vertex choose two girl vertices at random. Then, according to Walkup, with probability this bipartite graph contains a perfect matching. Karonski and Szpankowski (1992) showed you get by without having each vertex choose two vertices on the other side but roughly of them; have each vertex choose one vertex on the other side. A vertex not chosen by a vertex on the opposite side gets another choice. Walkup’s Theorem was the first step on the road that led eventually to the proof of the Parisi conjecture by Nair, Prabhakar and Sharma (2005). I have my own little contribution in this literature that I’d like to advertise.
Now lets put Walkup’s theorem to work. Let the utility that boy assigns to girl be . Similarly, the utility that girl assigns to boy is . Assume that is large. Suppose the ‘s and ‘s are independent draws from distributions over For fixed , must have cardinality at least 2 for all with high probability for large enough. Similarly, define
Now, let each boy chooses his favorite and second favorite girl from . *Observe that this is like choosing 2 vertices uniformly at random from the opposite side. Let each girl chooses her favorite and second favorite boy from . From Walkup we know that the resulting bipartite graph has a perfect matching with high probability.*
There is a fix not using Walkup. We care only about edges such that and . The probability that such an edge exists (independently of the others) will be some fixed constant depending on and not . For example, if the distribution from which the and ‘s was uniform, it would be . From Erdos-Renyi such a random graph would have a perfect matching with high probability.
What can we say about this matching? If a boy prefers a girl not in , she clearly prefers one of the boys in that she is matched to, so the pair can’t form a blocking pair. If the matching so obtained can be blocked, no blocking pair can improve their utility by more than .
Consider now a large matching market. Tell each boy and girl to report their `top’ choices only. In other words, declare that you would rather be unmatched than be matched with someone not in the top . Pick a perfect matching with the property that no boy or girl is matched with anyone below their top (one exists with high probability). By the above, the matching will be `close’ to stable (if you accept a cardinal interpretation of utilities and that utilities of all agents are denominated on a common scale) and no agent can gain by much from misreporting their preferences. In other words, when markets are large (in this model) you don’t need to run a stable matching algorithm to get essentially a stable and incentive compatible outcome.