A stable marriage requires communication

DOI10.1016/J.GEB.2018.10.013zbMATH Open1429.91232arXiv1405.7709OpenAlexW2965885938MaRDI QIDQ2278950FDOQ2278950

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)

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.

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

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

zbMATH Keywords

stable matchingcommunication complexitystable marriagedistance to stabilityapproximately stable

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

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

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)