A stable marriage requires communication

DOI10.1016/J.GEB.2018.10.013MaRDI QIDQ2278950zbMATH OpenOpenAlexFDO

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

Publication date 12 December 2019

Published in Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.7709

zbMATH Keywords

stable matchingcommunication complexitystable marriagedistance to stabilityapproximately stable

Mathematics Subject Classification ID

Signaling and communication in game theory (91A28) Matching models (91B68)

Abstract: The Gale-Shapley algorithm for the Stable Marriage Problem is known to take $Theta(n^2)$ steps to find a stable marriage in the worst case, but only $Theta(nlogn)$ steps in the average case (with $n$ women and $n$ men). In 1976, Knuth asked whether the worst-case running time can be improved in a model of computation that does not require sequential access to the whole input. A partial negative answer was given by Ng and Hirschberg, who showed that $Theta(n^2)$ queries are required in a model that allows certain natural random-access queries to the participants' preferences. A significantly more general - albeit slightly weaker - lower bound follows from Segal's general analysis of communication complexity, namely that $Omega(n^2)$ Boolean queries are required in order to find a stable marriage, regardless of the set of allowed Boolean queries. Using a reduction to the communication complexity of the disjointness problem, we give a far simpler, yet significantly more powerful argument showing that $Omega(n^2)$ Boolean queries of any type are indeed required for finding a stable - or even an approximately stable - marriage. Notably, unlike Segal's lower bound, our lower bound generalizes also to (A) randomized algorithms, (B) allowing arbitrary separate preprocessing of the women's preferences profile and of the men's preferences profile, (C) several variants of the basic problem, such as whether a given pair is married in every/some stable marriage, and (D) determining whether a proposed marriage is stable or far from stable. In order to analyze "approximately stable" marriages, we introduce the notion of "distance to stability" and provide an efficient algorithm for its computation.

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

Cites work

• scientific article; zbMATH DE number 5764911 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 3558960 (Why is no real title available?)
• A Stable Marriage Requires Communication
• A new-old algorithm for minimum-cut and maximum-flow in closure graphs.
• An analysis of the stable marriage assignment algorithm
• College Admissions and the Stability of Marriage
• Communication Complexity
• Communication requirements for stable marriages
• Economic efficiency requires interaction
• Euclidean preferences
• Fast distributed almost stable matchings
• Instability of matchings in decentralized markets with various preference structures
• Lower Bounds for the Stable Marriage Problem and Its Variants
• Machiavelli and the Gale-Shapley Algorithm
• Maximal Closure of a Graph and Applications to Combinatorial Problems
• On the complexity of trial and error
• On the distributional complexity of disjointness
• On the survival of some unstable two-sided matching mechanisms
• Sisterhood in the Gale-Shapley matching algorithm
• Stable matching mechanisms are not obviously strategy-proof
• The Complexity of Counting Stable Marriages
• The Probabilistic Communication Complexity of Set Intersection
• The communication requirements of social choice rules and supporting budget sets
• Three Fast Algorithms for Four Problems in Stable Marriage

Cited in

(12)

• Lower Bounds for the Stable Marriage Problem and Its Variants
• Worst-case choice for the stable marriage problem
• The necessary and sufficient condition for the worst-case male optimal stable matching
• Lazy Gale-Shapley for many-to-one matching with partial information
• The complexity of the certification of properties of stable marriage
• Lower bounds for approximating graph parameters via communication complexity
• Review of the theory of stable matchings and contract systems
• A Stable Marriage Requires Communication
• Paths to marriage stability
• Complexity of stability in trading networks
• Improved Efficiency for Private Stable Matching
• Communication requirements for stable marriages

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 Q2278950)