On likely solutions of a stable marriage problem

DOI10.1214/aoap/1177005708zbMath0753.60016OpenAlexW2060445186MaRDI QIDQ1198579

Boris G. Pittel

Publication date: 16 January 1993

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1177005708

zbMATH Keywords

rankslimit theoremsstable matchingsstable marriage problemcombinatorial algorithmsrandom preferencesextreme matchings

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Asymptotic approximations, asymptotic expansions (steepest descent, etc.) (41A60) Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Multidimensional problems (41A63) Limit theorems in probability theory (60F99)

Related Items (17)

Matching games with partial information ⋮ Measuring the instability in two-sided matching procedures ⋮ Two-sided matching markets with strongly correlated preferences ⋮ On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm ⋮ Descending the stable matching lattice: how many strategic agents are required to turn pessimality to optimality? ⋮ Assigning more students to their top choices: a comparison of tie-breaking rules ⋮ On random stable matchings: cyclic ones with strict preferences and two-sided ones with partially ordered preferences ⋮ The cost of strategy-proofness in school choice ⋮ Stability in repeated matching markets ⋮ Coalitional stability in matching problems with externalities and random preferences ⋮ What matters in school choice tie-breaking? How competition guides design ⋮ One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences ⋮ Optimal truncation in matching markets ⋮ On the Likely Number of Solutions for the Stable Marriage Problem ⋮ Matching with externalities: the role of prudence and social connectedness in stability ⋮ On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women ⋮ Network flow and 2-satisfiability

This page was built for publication: On likely solutions of a stable marriage problem