On likely solutions of a stable marriage problem

DOI10.1214/AOAP/1177005708MaRDI QIDQ1198579zbMATH OpenOpenAlexFDO

Authors Boris 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 marriage problemstable matchingscombinatorial algorithmsrandom preferencesextreme matchings

Mathematics Subject Classification ID

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

Recommendations

• The Average Number of Stable Matchings
• The ``stable roommates problem with random preferences
• On the likely number of solutions for the stable marriage problem
• On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
• Stable husbands

Cited in

(37)

• Lower Bounds for the Stable Marriage Problem and Its Variants
• Beauty and distance in the stable marriage problem
• Instability in stable marriage problem: matching unequally numbered men and women
• Descending the stable matching lattice: how many strategic agents are required to turn pessimality to optimality?
• On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
• On the likely number of solutions for the stable marriage problem
• On the Number of Fixed Pairs in a Random Instance of the Stable Marriage Problem
• Two-sided matching markets with strongly correlated preferences
• What matters in school choice tie-breaking? How competition guides design
• Matching games with partial information
• Marriage matching and gender satisfaction
• Network flow and 2-satisfiability
• Matching of like rank and the size of the core in the marriage problem
• Stability in repeated matching markets
• On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women
• Stable husbands
• Distribution of the total happiness level under a random matching
• One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences
• scientific article; zbMATH DE number 2038736 (Why is no real title available?)
• 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
• A mechanism implementing the stable rule in marriage problems
• The cost of strategy-proofness in school choice
• Sex-oriented stable matchings of the marriage problem with correlated and incomplete information
• On the probabilities of the mutual agreement match
• scientific article; zbMATH DE number 742942 (Why is no real title available?)
• The structure of stable marriage with indifference
• A note on cohabitation and marriage
• Misrepresentation and stability in the marriage problem
• From One Stable Marriage to the Next: How Long Is the Way?
• Sequences of the stable matching problem
• On random exchange-stable matchings
• Mallows permutations as stable matchings
• Coalitional stability in matching problems with externalities and random preferences
• Optimal truncation in matching markets
• Measuring the instability in two-sided matching procedures
• Matching with externalities: the role of prudence and social connectedness in stability

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

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