*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.

## 13 comments

December 15, 2011 at 8:02 pm

wellplacedadjectivenice.

but aren’t you introducing correlation in the arc choices by the boys and girls? that kinda seems like it might bias the bounds in the wrong direction; e.g. if the girl you point to always points back at you, then the probability of a perfect matching is roughly zero, no?

December 15, 2011 at 8:51 pm

rvohraDear wellplacedadjective:

If there was correlation between the boys and girls that would be a problem for the argument. Its ruled out here because I assumed the b’s and g’s are independent of each other. If I was not clear about that, mea culpa. The perfect correlation you posit (b’s first choice is g and g’s first choice is b) would make finding a perfect matching easy: just match everyone with their first choice.

rakesh

December 16, 2011 at 1:14 am

AnonymousGreat post of a beautiful set of theorems.

December 16, 2011 at 1:27 am

wellplacedadjectivemaybe i’m missing something, but… isn’t j in Bi iff i is in Gj? (being imprecise: even though the b’s and g’s are iid, the Bi’s and Gj’s are not, by construction.)

so if i points to j, then i is in Gj… and simply knowing that i is in Gj seems to imply that the probability of j pointing to i is 2/|Gj| >>> 1/n.

and the first-choice-matching is perfect only if each male iid selects a unique partner. this is (obviously) an incomplete story, but the correlation makes things messy in nonobvious ways.

December 16, 2011 at 2:22 pm

rvohraYou are not missing anything. I (blush) am. I think I have a fix, which I just posted. Thanks for pointing out my mistake.

Rakesh

December 16, 2011 at 1:40 pm

wellplacedadjectiveif an outside observer sees that bob points to alice, he then learns that both (i) alice is a decent mate for bob *and* (ii) bob is a decent mate for alice. since alice only points to decent mates, it’s therefore much more likely that alice points back to bob than some other schmo that didn’t point to her…

December 16, 2011 at 2:27 am

AnonymousThis paper discusses the strategic manipulation of stable matching mechanisms. Stable matching mechanisms are very successful in practice, despite theoretical concerns that they are manipulable by participants. Our key finding is that most agents in large markets are close to being indifferent among partners in all stable matchings. It is known that the utility gain by manipulating a stable matching mechanism is bounded by the difference between utilities from the best and the worst stable matching partners. Thus, the main finding implies that the proportion of agents who may obtain a signicant utility gain from manipulation vanishes in large markets. This result reconciles the success of stable mechanisms in practice with the theoretical concerns about strategic manipulation. We also introduce new techniques from the theory of random bipartite graphs for the analysis of large matching markets.

December 16, 2011 at 2:27 pm

rvohraYes, I know the paper. My observation above does not imply the result in this paper. The Lee paper is about asymptotic properties of the stable matching. This paper can be viewed as a justification for the use of stable matching mechanisms as they are robust in large markets. What I would point out from my observation is that one can achieve outcomes of the same flavor without using a stable matching mechanism.

December 18, 2011 at 12:09 pm

FedericoNice post Ricky.

Anonymous: SangMok Lee shows that the utilities in any two stable matchings are close in a large market, which has implications for the incentive compatibility of stable matching mechanisms. Ricky’s argument is instead on the existence of a “good” matching, and that this matching is close to stable. SangMok also allows for utilities that are not iid, but instead have common and private value components.

December 21, 2011 at 1:00 pm

EduardoVery interesting post.

While it is different from SangMok’s (excellent) paper, it would be interesting to try to generalize the result in the post to a setting with common and private values as in SangMok’s paper. My guess is that one would need something like a matching algorithm in that case, but maybe there is an approximate matching algorithm that does better than O(n^2).

December 21, 2011 at 2:46 pm

rvohraDear Eduardo

I think the same partitioning device that SangMok uses can be used here. Suppose the common values component is from [0,1]. Divide [0,1] up into m (large) equal sized intervals. Take all boys and girls whose common value component is in the same interval, say, [k/m, (k+1)/m] and match them as I describe above using the private values component. I’ve not thought about the complexity question, but now that you mention it……..yes, if one is serious about the large market case one should give it some thought.

December 16, 2011 at 3:07 am

Economist's View: Links for 2011-12-16[…] An Application of Walkup’s Theorem to Matchings – Leisure of the Theory Class […]

December 16, 2011 at 3:34 am

Links for 2011-12-16 | FavStocks[…] An Application of Walkup’s Theorem to Matchings – Leisure of the Theory Class […]