The ``stable roommates problem with random preferences

DOI10.1214/AOP/1176989126zbMATH Open0778.60005OpenAlexW1990302986MaRDI QIDQ688057FDOQ688057

Authors: Boris Pittel 

Publication date: 5 January 1994

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

Full work available at URL: https://doi.org/10.1214/aop/1176989126

Recommendations

• Stable roommates problem with random preferences
• On a generalization of the stable roommates problem
• Approximation and Online Algorithms
• On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
• ``Almost stable matchings in the roommates problem with bounded preference lists
• The strongly stable roommates problem
• Random paths to \(P\)-stability in the roommate problem
• The Stable Roommates Problem with Choice Functions
• The stable roommates problem with choice functions

zbMATH Keywords

ranksorderstable matchingconditional probabilityasymptotic meanrandom preferences

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Random graphs (graph-theoretic aspects) (05C80) 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)

Cited In (32)

• A maximum stable matching for the roommates problem
• Random stable matchings
• On the probabilities of the mutual agreement match
• One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences
• Matching with externalities: the role of prudence and social connectedness in stability
• On the likely number of solutions for the stable marriage problem
• Exchange-stability in roommate problems
• The stable roommates problem with choice functions
• On the Number of Fixed Pairs in a Random Instance of the Stable Marriage Problem
• The Stable Roommates Problem with Globally Ranked Pairs
• Distribution of the total happiness level under a random matching
• On random exchange-stable matchings
• Stable husbands
• A Note on the Room-Mates Problem and a Related Revenue Allocation Problem
• Coalitional stability in matching problems with externalities and random preferences
• The Stable Roommates Problem with Short Lists
• An efficient algorithm for the “stable roommates” problem
• On random stable partitions
• Stable roommates problem with random preferences
• Title not available (Why is that?)
• Small random instances of the stable roommates problem
• Mallows permutations as stable matchings
• Sequences of the stable matching problem
• On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
• The stable marriage problem: an interdisciplinary review from the physicist's perspective
• On random stable matchings: cyclic ones with strict preferences and two-sided ones with partially ordered preferences
• On likely solutions of a stable marriage problem
• The core of roommate problems: size and rank-fairness within matched pairs
• Large roommate problem with non-transferable random utility
• Analysis of stochastic matching markets
• Coalescence on the real line
• Review of the theory of stable matchings and contract systems

This page was built for publication: The ``stable roommates problem with random preferences

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