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

DOI10.1016/J.DAM.2020.12.020MaRDI QIDQ2223683zbMATH OpenOpenAlexFDO

Authors Boris 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)

Recommendations

• An efficient implementation of the Gale and Shapley ``propose-and-reject algorithm
• Preference profiles determining the proposals in the Gale-Shapley algorithm for stable matching problems
• Social welfare in one-sided matchings: random priority and beyond
• Lazy Gale-Shapley for many-to-one matching with partial information
• Cheating strategies for the Gale-Shapley algorithm with complete preference lists
• Strategy-proof probabilistic decision schemes for one-dimensional single-peaked preferences
• Nash implementation in an allocation problem with single-dipped preferences
• Binary mechanism for the allocation problem with single-dipped preferences
• The revealed preference theory of stable matchings with one-sided preferences
• Efficiency of truthful and symmetric mechanisms in one-sided matching

Cites work

• A generalization of the stable matching problem
• A necessary and sufficient condition for the existence of a complete stable matching
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• An analysis of the stable marriage assignment algorithm
• An efficient algorithm for the “stable roommates” problem
• An upper bound for the solvability probability of a random stable roommates instance
• Balls and bins: A study in negative dependence
• College Admissions and the Stability of Marriage
• scientific article; zbMATH DE number 3736679 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 3558960 (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
• On likely solutions of a stable marriage problem
• On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women
• On random stable partitions
• On the likely number of solutions for the stable marriage problem
• Random stable matchings
• Stable husbands
• Stable matchings and stable partitions^∗
• The ``stable roommates problem with random preferences
• The Average Number of Stable Matchings

Cited in

(2)

• Preference profiles determining the proposals in the Gale-Shapley algorithm for stable matching problems
• One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences

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

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