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 G be the set of girl vertices, B the set of boy vertices and suppose that |G| = |B| = n. 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 1 - o(n^{-1}) 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 1 + 1/e 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 i assigns to  girl j be b_{ij}. Similarly, the utility that girl j assigns to boy i is g_{ji} . Assume that n is large. Suppose the b‘s and g‘s are independent draws from distributions over [0,1]. For fixed \epsilon,   B_i = \{j: b_{ij} > 1-\epsilon, g_{ji} > 1- \epsilon\}  must have cardinality at least 2 for all i \in B with high probability for n large enough. Similarly, define G_j.

Now, let each boy i chooses his favorite and second favorite girl from B_i. *Observe that this is like choosing 2 vertices uniformly at random from the opposite side. Let each girl j chooses her favorite and second favorite boy from G_j. 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 (i,j) such that i \in G_j and j \in B_i. The probability that such an edge  exists (independently of the others) will be some fixed constant depending on \epsilon and not n. For example, if the distribution from which the b and g‘s was uniform, it would be \epsilon ^2. 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 i prefers a girl k not in B_i, she clearly prefers one of the boys in G_k that she is matched to, so the pair (i,k) can’t form a blocking pair. If the matching so obtained can be blocked, no blocking pair can improve their utility by more than \epsilon.

Consider now a large matching market. Tell each boy and girl to report their `top’ \epsilon choices only. In other words, declare that you would rather be unmatched than be matched with someone not in the top \epsilon. Pick a perfect matching with the property that no boy or girl is matched with anyone below their top \epsilon (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.