The stable marriage problem: an interdisciplinary review from the physicist's perspective

DOI10.1016/j.physrep.2021.03.001OpenAlexW3136687487MaRDI QIDQ2231919

Jianyang Zhao, Izat B. Baybusinov, Enrico Maria Fenoaltea, Lei Zhou, Yi-Cheng Zhang

Publication date: 30 September 2021

Published in: Physics Reports (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2103.11458

zbMATH Keywords

optimizationNash equilibriumreplica methodpartial informationtwo-sided marketsGale-Shapley algorithm

Mathematics Subject Classification ID

Applications of statistics to economics (62P20) Sensitivity, stability, parametric optimization (90C31) 2-person games (91A05) Quantum computation (81P68)

Related Items (5)

A local interaction dynamic for the matching problem ⋮ Negotiation problem ⋮ Review of the theory of stable matchings and contract systems ⋮ Market failure in a new model of platform design with partially informed consumers ⋮ Bipartite choices

Cites Work

• Matching With Complementary Contracts
• Reducibility among Combinatorial Problems
• On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women
• A simply exponential upper bound on the maximum number of stable matchings
• Algorithmics of Matching Under Preferences
• Algorithm Theory - SWAT 2004
• The Traveling-Salesman Problem
• Algorithms – ESA 2004
• A Randomized Rounding Approach to the Traveling Salesman Problem
• An analysis of the stable marriage assignment algorithm
• Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
• Approximation and Online Algorithms
• College Admissions and the Stability of Marriage
• Beauty and distance in the stable marriage problem
• Happier world with more information
• Sex-oriented stable matchings of the marriage problem with correlated and incomplete information
• Statistical mechanics methods and phase transitions in optimization problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• The ``stable roommates problem with random preferences
• Complexity of the sex-equal stable marriage problem
• Pairwise kidney exchange
• Entropy, large deviations, and statistical mechanics.
• The dynamics of law clerk matching: an experimental and computational investigation of proposals for reform of the market
• The role of a matchmaker in buyer-vendor interactions
• Emergence of product differentiation from consumer heterogeneity and asymmetric information
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• Notes on introductory combinatorics
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• Some remarks on the stable matching problem
• Improving the Hungarian assignment algorithm
• Generalized travelling salesman problem through n sets of nodes: The asymmetrical case
• Nonexistence of stable threesome matchings
• A new fixed point approach for stable networks and stable marriages
• Three remarks on the many-to-many stable matching problem
• Who solved the secretary problem
• Existence of stable matchings in some three-sided systems.
• On the stable \(b\)-matching polytope.
• An algorithm to compute the full set of many-to-many stable matchings.
• A proof of Parisi's conjecture on the random assignment problem
• Concerning the maximum number of stable matchings in the stable marriage problem
• Hard variants of stable marriage.
• Analysis of ground state in random bipartite matching
• Instability in stable marriage problem: matching unequally numbered men and women
• Stable matchings in three-sided systems with cyclic preferences
• Firm competition in a probabilistic framework of consumer choice
• The stable \(b\)-matching polytope revisited
• On randomized matching mechanisms
• Refined inequalities for stable marriage
• Speeding up the Hungarian algorithm
• Buyer feedback as a filtering mechanism for reputable sellers
• Replica bounds for optimization problems and diluted spin systems
• The cavity method at zero temperature
• Matching games with partial information
• Core many-to-one matchings by fixed-point methods
• Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry)
• Mathematical foundations of complex networked information systems. Lectures of the CIME course. Politecnico di Torino, Verrès, Italy 2009
• The cycle roommates problem: a hard case of kidney exchange
• A number of stable matchings in models of the Gale-Shapley type
• Replica symmetry breaking and the nature of the spin glass phase
• The ?(2) limit in the random assignment problem
• Stability and Polarization of Interests in Job Matching
• The Bargaining Problem
• Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications
• The Stable Roommates Problem with Ties
• Kidney Exchange
• Approximation algorithms for the sex-equal stable marriage problem
• Random-energy model: An exactly solvable model of disordered systems
• Algorithms for the Assignment and Transportation Problems
• Three-Dimensional Stabl Matching Problems
• The Average Number of Stable Matchings
• Random Paths to Stability in Two-Sided Matching
• NP-complete stable matching problems
• Two’s Company, Three’s a Crowd: Stable Family and Threesome Roommates Problems
• Non-Euclidean Traveling Salesman Problem
• A 3/2-Approximation Algorithm for General Stable Marriage
• The Secretary Problem and Its Extensions: A Review
• An efficient algorithm for the “stable roommates” problem
• Ms. Machiavelli and the Stable Matching Problem
• The Complexity of Counting Stable Marriages
• Three Fast Algorithms for Four Problems in Stable Marriage
• Machiavelli and the Gale-Shapley Algorithm
• Perfect Equilibrium in a Bargaining Model
• The Economics of Matching: Stability and Incentives
• Job Matching, Coalition Formation, and Gross Substitutes
• Some Simple Applications of the Travelling Salesman Problem
• A New Approach to Stable Matching Problems
• Fully Distributed Optimal Channel Assignment for Open Spectrum Access
• Student Portfolios and the College Admissions Problem
• Game Theory in Wireless and Communication Networks
• On Kuhn's Hungarian Method?A tribute from Hungary
• Statistical Physics of Spin Glasses and Information Processing
• The Monge-Kantorovich problem: achievements, connections, and perspectives
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Spin-glass theory for pedestrians
• Random multi-index matching problems

This page was built for publication: The stable marriage problem: an interdisciplinary review from the physicist's perspective