greenline
rgstripes
Otto-Bild Stephan Mertens - Research
Home | Research | Publications | Teaching | Smorgasbord
greenline

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 pn 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 pn exactly for small instances.


Publications

Data

Source Code

greenline
rgstripes
top Home | Research | Publications | Teaching | Smorgasbord
greenline

© by Stephan Mertens (Datenschutzerklärung)
updated on Monday, December 07th 2015, 00:59:01 CET;