Stephan Mertens - Research Home | Research | Publications | Teaching | Smorgasbord

Stable Matchings

The stable matching problem is a prototype model in economics and social sciences where agents act selfishly to optimize their own satisfaction, subject to mutually conflicting constraints. A paradigmatic example is the stable roommates problem. Consider an even number n of participants. Each of the participants ranks all the others in strict order of preference. A matching is a set of n/2 disjoint pairs of participants. A matching is stable if there is no pair of unmatched participants who both prefer each other to their partner in the matching. Such a pair is said to block the matching. The stable roommates problem is to find a stable matching. The name originates from the problem to assign students to the double bedroomes of a dormitory. Another application is the formation of cockpit crews from a pool of pilots.

It is well known that not all instances of the stable roommates problem admit a solution. My research focuses on computing the probability p_n that a random instance with n participants admits a solution. For that I developped a sublinear algorithm to solve large random instances of the stable roommates problem. I also used a computer algebra system to compute p_n exactly for small instances.

Publications

• Small Random Instances of the Stable Roommates Problem
  J. Stat. Mech. P06034 (2015) PDF BibTeX
• Stable Roommates Problem with Random Preferences
  J. Stat. Mech. P01020 (2015) PDF BibTeX
• Random Stable Matchings
  J. Stat. Mech. P10008 (2005) PDF BibTeX

Data

• roommates.dat: numerical probabilities p_n for n ≤ 458752
• small.dat: exact probabilities p_n for n ≤ 12

Source Code

• small-roommates.sh: Mathematica script that computes exact values for p_n. n is given as a command line parameter.