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

DOI10.1016/J.DAM.2020.12.020arXiv2005.06691MaRDI QIDQ6340653FDOQ6340653

Authors: Boris Pittel 

Publication date: 13 May 2020

Abstract: For a two-sided ($n$ men/$n$ women) stable matching problem) Gale and Shapley studied a proposal algorithm (men propose/women select, or the other way around), that determines a matching, not blocked by any unmatched pair. Irving used this algorithm as a first phase of his algorithm for one-sided (stable roommates) matching problem with $n$ agents. We analyze a fully extended version of Irving's proposal algorithm that runs all the way until either each agent holds a proposal or an agent gets rejected by everybody on the agent's preference list. It is shown that the terminal, directed, partnerships form a stable permutation with matched pairs remaining matched in any other stable permutation. A likely behavior of the proposal algorithm is studied under assumption that all $n$ rankings are independently uniform. It is proved that with high probability (w.h.p.) every agent has a partner, and that both the number of agents in cycles of length $ge3$ and the total number of stable matchings are bounded in probability. W.h.p. the total number of proposals is asymptotic to $0.5n^{3/2}$.

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05) Matching models (91B68)

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 Q6340653)