skip to main content
10.5555/1347082.1347215acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article

Sampling stable marriages: why spouse-swapping won't work

Published: 20 January 2008 Publication History

Abstract

We study the behavior of random walks along the edges of the stable marriage lattice for various restricted families of allowable preference sets. In the "k-attribute model," each man is valued in each of k attributes, and each woman's ranking of the men is determined by a linear function, representing her relative ranking of those attributes; men's rankings of the women are determined similarly. We show that sampling with a random walk on the marriage lattice can take exponential time, even when k = 2. Moreover, we show that the marriage lattices arising in the k-attribute model are more restrictive than in the general setting; previously such a restriction had only been shown for the sets of preference lists. The second model we consider is the "k-range model," where each person lies in a position in [i, i + k - 1], for some i, on every preference list of the opposite sex. When k = 1 there is a unique stable marriage. When k = 2 there already can be an exponential number of stable marriages, but we show that a random walk on the stable marriage lattice always converges quickly to equilibrium. However, when k ≥ 5, there are preference sets such that the random walk on the lattice will require exponential time to converge. Lastly, we show that in the extreme case where each gender's rankings of the other are restricted to one of just a constant k possible preference lists, there are still instances for which the Markov chain mixes exponentially slowly, even when k = 4. This oversimplification of the general model helps elucidate why Markov chains based on spouse-swapping are not good approaches to sampling, even in specialized scenarios.

References

[1]
C. Blair. Every Finite Distributive Lattice is a set of Stable Matchings. Journal of Combinatorial Theory (A), 37: 353--356, 1984.
[2]
A. Bogomolnaia and J-F. Laslier. Euclidean Preferences. Preprint: submitted to the Journal of Economic Theory, 2004.
[3]
P. Diaconis, R. L. Graham and J. A. Morrison. Asymptotic Analysis of a Random Walk on a Hypercube with Many Dimensions. Random Structures and Algorithms, 1: 51--72, 1990.
[4]
M. Dyer, L. A. Goldberg, C. Greenhill, M. Jerrum. On the Relative Complexity of Approximate Counting Problems Algorithmica 38: 471 - 500, 2003.
[5]
D. Gale and L. S. Shapley. College admissions and the Stability of Marriage. American Mathematical Monthly, 69: 9--15, 1962
[6]
D. Gusfield. Three Fast Algorithms for Four Problems in Stable Marriage. SIAM Journal on Computing, 16: 111--128, 1987.
[7]
D. Gusfield and R. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989.
[8]
D. Gusfield, R. Irving, P. Leather, and M. Saks. Every Finite Distributive Lattice is a Set of Stable Matchings for a Small Stable Marriage Instance. Journal of Combinatorial Theory (A), 44: 304--309, 1987.
[9]
R. Irving, P. Leather, D. Gusfield. An Efficient Algorithm for the "Optimal" Stable Marriage. Journal of the A.C.M., 34:532--543, 1987.
[10]
G. F. Lawler and A. D. Sokal, A. D. Bounds on the L2 spectrum for Markov chain and Markov processes: a generalization of Cheeger's inequality. Trans. Amer. Math. Soc., 309: 557--580, 1988.
[11]
D. E. Knuth. Marriages Stables. Les Presses de l'Universite de Montreal, Montreal, 1976.
[12]
A. Mehrez, Y. Yuan, A. Gafni. Stable Solutions vs. Multiplicative Utility Solutions for the Assignment Problem. Operations Research Letters, 7:131--139, 1988.
[13]
S. Menju. The Stable Marriage Assignment and Related problems. Technical Report C-83, Tokyo Institute of Technology, 1987.
[14]
A. Sinclair. Algorithms for Random Generation and Counting. Birkhauser, 1993
[15]
A. Sinclair and M. Jerrum. Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains Inf. Comput., 82: 93--133, 1989.
[16]
C-P. Teo and J. Sethuraman. The Geometry of Fractional Stable Matchings and its Applications. Mathematics of Operations Research., 23(4): 874--891, 1998.

Cited By

View all
  • (2019)Subquadratic Algorithms for Succinct Stable MatchingAlgorithmica10.1007/s00453-019-00564-x81:7(2991-3024)Online publication date: 1-Jul-2019
  • (2018)A simply exponential upper bound on the maximum number of stable matchingsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188848(920-925)Online publication date: 20-Jun-2018
  • (2016)Subquadratic Algorithms for Succinct Stable MatchingProceedings of the 11th International Computer Science Symposium on Computer Science --- Theory and Applications - Volume 969110.1007/978-3-319-34171-2_21(294-308)Online publication date: 9-Jun-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms
January 2008
1289 pages
  • Program Chair:
  • Shang-Hua Teng

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Qualifiers

  • Research-article

Conference

SODA08
Sponsor:
SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms
January 20 - 22, 2008
California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Subquadratic Algorithms for Succinct Stable MatchingAlgorithmica10.1007/s00453-019-00564-x81:7(2991-3024)Online publication date: 1-Jul-2019
  • (2018)A simply exponential upper bound on the maximum number of stable matchingsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188848(920-925)Online publication date: 20-Jun-2018
  • (2016)Subquadratic Algorithms for Succinct Stable MatchingProceedings of the 11th International Computer Science Symposium on Computer Science --- Theory and Applications - Volume 969110.1007/978-3-319-34171-2_21(294-308)Online publication date: 9-Jun-2016
  • (2013)Time hierarchies for sampling distributionsProceedings of the 4th conference on Innovations in Theoretical Computer Science10.1145/2422436.2422484(429-440)Online publication date: 9-Jan-2013
  • (2012)On Randomized Approximation for Finding a Level Ideal of a Poset and the Generalized Median Stable MatchingsMathematics of Operations Research10.1287/moor.1110.052637:2(356-371)Online publication date: 1-May-2012
  • (2011)Procedural fairness in stable marriage problemsThe 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 310.5555/2034396.2034491(1209-1210)Online publication date: 2-May-2011
  • (2011)Center stable matchings and centers of cover graphs of distributive latticesProceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I10.5555/2027127.2027199(678-689)Online publication date: 4-Jul-2011
  • (2011)An experimental comparison of single-sided preference matching algorithmsACM Journal of Experimental Algorithmics10.1145/1963190.201957916(1.1-1.16)Online publication date: 26-Aug-2011
  • (2010)The complexity of approximately counting stable matchingsProceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques10.5555/1886521.1886529(81-94)Online publication date: 1-Sep-2010
  • (2009)Longest common subsequence as private searchProceedings of the 8th ACM workshop on Privacy in the electronic society10.1145/1655188.1655200(81-90)Online publication date: 9-Nov-2009
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media