One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences

DOI10.1016/j.dam.2020.12.020OpenAlexW3118304757MaRDI QIDQ2223683

Boris G. Pittel

Publication date: 1 February 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

asymptoticsrandom preferencesstable permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The ``stable roommates problem with random preferences
• On likely solutions of a stable marriage problem
• A generalization of the stable matching problem
• On random stable partitions
• A necessary and sufficient condition for the existence of a complete stable matching
• The Average Number of Stable Matchings
• On the Likely Number of Solutions for the Stable Marriage Problem
• An efficient algorithm for the “stable roommates” problem
• Stable matchings and stable partitions^∗
• On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
• An upper bound for the solvability probability of a random stable roommates instance
• Balls and bins: A study in negative dependence
• Random stable matchings
• On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women
• Algorithmics of Matching Under Preferences
• An analysis of the stable marriage assignment algorithm
• Stable husbands
• College Admissions and the Stability of Marriage

This page was built for publication: One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences