Scaling Behavior in the Stable Marriage Problem

Abstract

We study the optimization of the stable marriage problem. All individuals attempt to optimize their own satisfaction, subject to mutually conflicting constraints. We find that the stable solutions are generally not the globally best solution, but reasonably close to it. All the stable solutions form a special sub-set of the meta-stable states, obeying interesting scaling laws. Both numerical and analytical tools are used to derive our results.

6 pages, revtex, 3 figures. To appear in J. de Physique I, vol 7, No 12 (December)

Cited by in corpus (13)

• Information filtering via preferential diffusion
• Matching games with partial information
• The Stable Marriage Problem: an Interdisciplinary Review from the Physicist's Perspective
• Beauty and Distance in the Stable Marriage Problem
• Statistics of stable marriages
• The marriage problem: from the bar of appointments to the agency
• Statistical Mechanics of Competitive Resource Allocation using Agent-based Models
• Market Model with Heterogeneous Buyers
• Sex-Oriented stable matchings of the Marriage Problem with correlated and incomplete information
• The Marriage Problem and the Fate of Bachelors
• Stable Roommates Problem with Random Preferences
• Competition May Increase Social Happiness in Bipartite Matching Problem
• Affinity driven social networks