Random stable matchings

DOI10.1088/1742-5468/2005/10/P10008MaRDI QIDQ4968805zbMATH OpenFDO

Authors S. Mertens

Publication date 9 July 2019

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0509221

zbMATH Keywords

applications to game theory and mathematical economicsinteracting agent modelsnetworksrandom graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Matching models (91B68)

Abstract: 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.

Recommendations

• The ``stable roommates problem with random preferences
• On random stable matchings: cyclic ones with strict preferences and two-sided ones with partially ordered preferences
• On random stable partitions
• On random exchange-stable matchings
• Stable roommates problem with random preferences

Cites work

• A characterization of graphs that ensure the existence of stable matchings
• A necessary and sufficient condition for the existence of a complete stable matching
• An efficient algorithm for the “stable roommates” problem
• An upper bound for the solvability probability of a random stable roommates instance
• Beauty and distance in the stable marriage problem
• College Admissions and the Stability of Marriage
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 48303 (Why is no real title available?)
• scientific article; zbMATH DE number 958014 (Why is no real title available?)
• On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
• The ``stable roommates problem with random preferences

Cited in

(22)

• Analysis of ground state in random bipartite matching
• On random exchange-stable matchings
• On randomized matching mechanisms
• On random stable partitions
• On random stable matchings: cyclic ones with strict preferences and two-sided ones with partially ordered preferences
• One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences
• The stable marriage problem: an interdisciplinary review from the physicist's perspective
• Jointly stable matchings
• Statistical mechanics of a simplified bipartite matching problem: An analytical treatment
• Existence of independent random matching
• Procedurally fair and stable matching
• Stable roommates problem with random preferences
• Small random instances of the stable roommates problem
• Analysis of stochastic matching markets
• Coalescence on the real line
• An extendable stable matching algorithm of a kind of bipartite graph
• A General Framework for Stable Roommates Problems using Answer Set Programming
• Random Matching Under Dichotomous Preferences
• Unique stable matchings
• Coalitional stability in matching problems with externalities and random preferences
• Unsolvability and beyond in many-to-many non-bipartite stable matching
• Structural and algorithmic results for stable cycles and partitions in the roommates problem

This page was built for publication: Random stable matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4968805)