Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
2005-09-08
J. Stat. Mech. (2005) P100008
Physics
Condensed Matter
Disordered Systems and Neural Networks
11 pages, 9 figures (v2: minor changes, published version)
Scientific paper
10.1088/1742-5468/2005/10/P10008
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 stable matching is a pairing of adjacent vertices in a graph such that no unpaired vertices prefer each other to their partners under the matching. The problem of finding stable matchings is known as stable marriage problem (on bipartite graphs) or as stable roommates problem (on the complete graph). It is well-known that not all instances on non-bipartite graphs admit a stable matching. Here we present numerical results for the probability that a graph with $n$ vertices and random preference relations admits a stable matching. In particular we find that this probability decays algebraically on graphs with connectivity $\Theta(n)$ and exponentially on regular grids. On finite connectivity Erd\"os-R\'enyi graphs the probability converges to a value larger than zero. Based on the numerical results and some heuristic reasoning we formulate five conjectures on the asymptotic properties of random stable matchings.
No associations
LandOfFree
Random Stable Matchings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Random Stable Matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random Stable Matchings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-2845