The Stable Marriage Problem: an Interdisciplinary Review from the Physicist's Perspective

Abstract

We present a fascinating model that has lately caught attention among physicists working in complexity related fields. Though it originated from mathematics and later from economics, the model is very enlightening in many aspects that we shall highlight in this review. It is called The Stable Marriage Problem (though the marriage metaphor can be generalized to many other contexts), and it consists of matching men and women, considering preference-lists where individuals express their preference over the members of the opposite gender. This problem appeared for the first time in 1962 in the seminal paper of Gale and Shapley and has aroused interest in many fields of science, including economics, game theory, computer science, etc. Recently it has also attracted many physicists who, using the powerful tools of statistical mechanics, have also approached it as an optimization problem. Here we present a complete overview of the Stable Marriage Problem emphasizing its multidisciplinary aspect, and reviewing the key results in the disciplines that it has influenced most. We focus, in particular, in the old and recent results achieved by physicists, finally introducing two new promising models inspired by the philosophy of the Stable Marriage Problem. Moreover, we present an innovative reinterpretation of the problem, useful to highlight the revolutionary role of information in the contemporary economy.

arXiv commentPaper accepted for publication in Physics Reports

References in corpus (30)

• The Web of Human Sexual Contacts
• Recommender Systems
• Emergence of Cooperation and Organization in an Evolutionary Game
• Avalanche Dynamics in Evolution, Growth, and Depinning Models
• Spin-Glass Theory for Pedestrians
• Multiple stable states in microbial communities explained by the stable marriage problem
• Modeling Market Mechanism with Evolutionary Games
• A Conjecture on random bipartite matching
• The cavity method at zero temperature
• Random multi-index matching problems
• Matching games with partial information
• Beauty and Distance in the Stable Marriage Problem
• Happier World with More Information
• Infinite Hierarchy of Exact Equations in the Bak-Sneppen Model
• On Using Matching Theory to Understand P2P Network Design
• A frozen glass phase in the multi-index matching problem
• Statistics of stable marriages
• Scaling Behavior in the Stable Marriage Problem
• Replica bounds for optimization problems and diluted spin systems
• The marriage problem: from the bar of appointments to the agency
• Market Model with Heterogeneous Buyers
• The role of a matchmaker in buyer-vendor interactions
• The Marriage Problem and the Fate of Bachelors
• Sex-Oriented stable matchings of the Marriage Problem with correlated and incomplete information
• Emergence of product differentiation from consumer heterogeneity and asymmetric information
• Firm competition in a probabilistic framework of consumer choice
• It's Not Easy Being Three: The Approximability of Three-Dimensional Stable Matching Problems
• Competition May Increase Social Happiness in Bipartite Matching Problem
• Stable marriage problem under Monte Carlo simulations, influence of preferrence corelation on relaxation time
• Analysis of ground state in random bipartite matching

Cited by in corpus (4)

• Negotiation problem
• Optimal coordination of resources: A solution from reinforcement learning
• Disagreement and fragmentation in growing groups
• A Grand-Canonical Solution to a Class of Random Optimization Problems