A Stable Marriage Requires Communication

DOI10.1137/1.9781611973730.68MaRDI QIDQ5363098zbMATH OpenOpenAlexFDO

Authors Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, Will Rosenbaum

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973730.68

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Matching models (91B68)

Recommendations

• A stable marriage requires communication
• Communication requirements for stable marriages
• Stable marriages
• Paths to marriage stability
• scientific article; zbMATH DE number 19691
• Stable marriage and indifference
• Stable husbands
• Marriage, honesty, and stability
• Implementation of stable solutions to marriage problems

Cited in

(6)

• Stable matching mechanisms are not obviously strategy-proof
• A stable marriage requires communication
• Lower Bounds for the Stable Marriage Problem and Its Variants
• Communication requirements for stable marriages
• Improved Efficiency for Private Stable Matching
• The complexity of the certification of properties of stable marriage

This page was built for publication: A Stable Marriage Requires Communication

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