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

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 (stabl...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2021-03, Vol.292, p.1-18
Main Author: Pittel, Boris
Format: Article
Language:English
Subjects:
Algorithms
Asymptotics
Matching
Permutations
Random preferences
Stable permutations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 permutation satisfying a certain stability condition, similar to, but different from the one introduced by Jimmy Tan. 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 ≥3 and the total number of stable matchings are bounded in probability. W.h.p. the total number of proposals is asymptotic to 0.5n3∕2.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2020.12.020