research-article

Open access

Pairwise Preferences in the Stable Marriage Problem

Authors:

Attila JuhosAuthors Info & Claims

ACM Transactions on Economics and Computation (TEAC), Volume 9, Issue 1

Article No.: 7, Pages 1 - 28

https://doi.org/10.1145/3434427

Published: 02 January 2021 Publication History

All formats PDF

Abstract

We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges, and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability—weak, strong, and super-stability—under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs, we determine the complexity of all cases not yet known and thus give an exact boundary in terms of preference structure between tractable and intractable cases.

References

[1]

D. J. Abraham. 2003. Algorithmics of Two-sided Matching Problems. Master’s thesis. University of Glasgow, Department of Computing Science.

[2]

Alberto Alesina and Howard Rosenthal. 1996. A theory of divided government. Econometrica 64, 6 (1996), 1311–1341.

[3]

Haris Aziz, Péter Biró, Tamás Fleiner, Serge Gaspers, Ronald de Haan, Nicholas Mattei, and Baharak Rastegari. 2017. Stable matching with uncertain pairwise preferences. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 344–352.

[4]

P. Berman, M. Karpinski, and Alexander D. Scott. 2003. Approximation Hardness of Short Symmetric Instances of MAX-3SAT. Electronic Colloquium on Computational Complexity Report, number 49.

[5]

P. Biró, D. F. Manlove, and S. Mittal. 2010. Size versus stability in the marriage problem. Theor. Comput. Sci. 411, 16--18 (2010), 1828–1841.

Digital Library

[6]

Péter Biró. 2017. Applications of matching models under preferences. Trends Comput. Soc. Choice (2017), 345.

[7]

Péter Biró and Sofya Kiselgof. 2015. College admissions with stable score-limits. Centr. Eur. J. Operat. Res. 23, 4 (2015), 727–741.

[8]

P. Blavatsky. 2003. Content-dependent Preferences in Choice under Risk: Heuristic of Relative Probability Comparisons. IIASA Interim Report IR-03-031 (2003).

[9]

Li Chen. 2012. University Admission Practices—reland, MiP Country Profile 8. Retrieved from http://www.matching-in-practice.eu/higher-education-in-ireland/.

[10]

M.-J.-A.-N. de C. (Marquis de) Condorcet. 1785. Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. L’Imprimerie Royale.

[11]

Linda Farczadi, Konstantinos Georgiou, and Jochen Könemann. 2016. Stable marriage with general preferences. Theory Comput. Syst. 59, 4 (2016), 683–699.

Digital Library

[12]

P. Fishburn. 1999. Preference structures and their numerical representations. Theor. Comput. Sci. 217, 2 (1999), 359–383.

Digital Library

[13]

T. Fleiner, R. W. Irving, and D. F. Manlove. 2007. Efficient algorithms for generalised stable marriage and roommates problems. Theor. Comput. Sci. 381, 1--3 (2007), 162–176.

Digital Library

[14]

D. Gale and L. S. Shapley. 1962. College admissions and the stability of marriage. Am. Math. Month. 69 (1962), 9–15.

[15]

D. Gale and M. Sotomayor. 1985. Some remarks on the stable matching problem. Discr. Appl. Math. 11 (1985), 223–232.

[16]

P. Hall. 1935. On representatives of subsets. J. Lond. Math. Soc. 10 (1935), 26–30.

[17]

Steven Humphrey. 2001. Non-transitive choice: Event-splitting effects or framing effects? Economica 68, 269 (2001), 77–96.

[18]

R. W. Irving. 1985. An efficient algorithm for the “stable roommates” problem. J. Algor. 6 (1985), 577–595.

[19]

R. W. Irving. 1994. Stable marriage and indifference. Discr. Appl. Math. 48 (1994), 261–272.

Digital Library

[20]

R. W. Irving and D. F. Manlove. 2002. The stable roommates problem with ties. J. Algor. 43 (2002), 85–105.

Digital Library

[21]

R. W. Irving, D. F. Manlove, and S. Scott. 2000. The hospitals / residents problem with ties. In Proceedings of the 7th Scandinavian Workshop on Algorithm Theory (SWAT’00), Lecture Notes in Computer Science, Vol. 1851, Magnús M. Halldórsson (Ed.). Springer, 259–271.

[22]

R. W. Irving, D. F. Manlove, and S. Scott. 2003. Strong stability in the hospitals / residents problem. In Proceedings of he 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS’03), Lecture Notes in Computer Science, Vol. 2607. Springer, 439–450.

[23]

A. B. Kahn. 1962. Topological sorting of large networks. Commun. ACM 5, 11 (November 1962), 558–562.

Digital Library

[24]

Tobias Kalenscher, Philippe N. Tobler, Willem Huijbers, Sander M. Daselaar, and Cyriel M. A. Pennartz. 2010. Neural signatures of intransitive preferences. Front. Hum. Neurosci. 4 (2010), 49.

[25]

Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, and Katarzyna E. Paluch. 2007. Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem. ACM Trans. Algor. 3, 2 (2007), 15.

Digital Library

[26]

Harold W. Kuhn. 1955. The Hungarian method for the assignment problem. Nav. Res. Log. Quart. 2, 1-2 (1955), 83–97.

[27]

Adam Kunysz. 2016. The strongly stable roommates problem. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA’16). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[28]

Adam Kunysz, Katarzyna Paluch, and Pratik Ghosal. 2016. Characterisation of strongly stable matchings. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 107–119.

[29]

László Lovász and Michael D. Plummer. 2009. Matching Theory. Vol. 367. American Mathematical Society.

[30]

D. F. Manlove. 1999. Stable Marriage with Ties and Unacceptable Partners. Technical Report TR-1999-29. University of Glasgow, Department of Computing Science.

[31]

D. F. Manlove. 2002. The structure of stable marriage with indifference. Discr. Appl. Math. 122, 1-3 (2002), 167–181.

Digital Library

[32]

D. F. Manlove. 2013. Algorithmics of Matching Under Preferences. World Scientific.

[33]

Kenneth O. May. 1954. Intransitivity, utility, and the aggregation of preference patterns. Econometrica 22, 1 (1954), 1–13.

[34]

Ignacio Ríos, Tomás Larroucau, Giorgiogiulio Parra, and Roberto Cominetti. 2014. College Admissions Problem with Ties and Flexible Quotas. Technical Report. SSRN.

[35]

E. Ronn. 1986. On the Complexity of Stable Matchings with and without Ties. Ph.D. Dissertation. Yale University.

[36]

S. Scott. 2005. A Study of Stable Marriage Problems with Ties. Ph.D. Dissertation. University of Glasgow, Department of Computing Science.

[37]

B. Spieker. 1995. The set of super-stable marriages forms a distributive lattice. Discr. Appl. Math. 58 (1995), 79–84.

Digital Library

[38]

WWWUSelection. 2018. Huffington Post 2016 General Election: Trump vs. Sanders. Retrieved September 3, 2018 from https://elections.huffingtonpost.com/pollster/2016-general-election-trump-vs-sanders.

[39]

WWWUSelection. 2018. RealClearPolitics website. General Election: Trump vs. Sanders. Retrieved Sptember 3, 2018 from https://www.realclearpolitics.com/epolls/2016/president/us/general_election_trump_vs_sanders-5565.html.

Cited By

Ge SItoh T(2025)Popularity on the roommate diversity problemTheoretical Computer Science10.1016/j.tcs.2024.1149031023(114903)Online publication date: Jan-2025
https://doi.org/10.1016/j.tcs.2024.114903
Schlotter IBiró PFleiner T(2024)The Core of Housing Markets from an Agent’s Perspective: Is It Worth Sprucing up Your Home?Mathematics of Operations Research10.1287/moor.2023.0092Online publication date: 28-Aug-2024
https://doi.org/10.1287/moor.2023.0092
Wolf RHeeger KNichterlein A(2024)Effective Data Reduction for Strongly Stable Matching in Very Sparse GraphsInformation Processing Letters10.1016/j.ipl.2024.106534(106534)Online publication date: Oct-2024
https://doi.org/10.1016/j.ipl.2024.106534
Show More Cited By

Index Terms

Pairwise Preferences in the Stable Marriage Problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms

Recommendations

Stable Marriage with General Preferences

We propose a generalization of the classical stable marriage problem. In our model, the preferences on one side of the partition are given in terms of arbitrary binary relations, which need not be transitive nor acyclic. This generalization is ...
On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization)

Stable Marriage is a fundamental problem to both computer science and economics. Four well-known NP-hard optimization versions of this problem are the Sex-Equal Stable Marriage (SESMI), Balanced Stable Marriage (BSMI), max-Stable Marriage with Ties (max-...
Hardness results on the man-exchange stable marriage problem with short preference lists

We present two hardness results on the man-exchange stable marriage problem, one of which settles a recent conjecture of Irving on the complexity of determining whether a given instance of the stable marriage problem with short preference lists has a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Economics and Computation

ACM Transactions on Economics and Computation Volume 9, Issue 1

Special Issue on WINE'18: Part 1, and Regular Papers

March 2021

182 pages

ISSN:2167-8375

EISSN:2167-8383

DOI:10.1145/3446654

Editors:
David Pennock
Microsoft
,
Ilya Segal
Stanford University

Issue’s Table of Contents

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 January 2021

Accepted: 01 September 2020

Revised: 01 August 2020

Received: 01 June 2019

Published in TEAC Volume 9, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Hungarian Academy of Sciences
COST Action
OTKA grant

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
462
Total Downloads

Downloads (Last 12 months)163
Downloads (Last 6 weeks)28

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ge SItoh T(2025)Popularity on the roommate diversity problemTheoretical Computer Science10.1016/j.tcs.2024.1149031023(114903)Online publication date: Jan-2025
https://doi.org/10.1016/j.tcs.2024.114903
Schlotter IBiró PFleiner T(2024)The Core of Housing Markets from an Agent’s Perspective: Is It Worth Sprucing up Your Home?Mathematics of Operations Research10.1287/moor.2023.0092Online publication date: 28-Aug-2024
https://doi.org/10.1287/moor.2023.0092
Wolf RHeeger KNichterlein A(2024)Effective Data Reduction for Strongly Stable Matching in Very Sparse GraphsInformation Processing Letters10.1016/j.ipl.2024.106534(106534)Online publication date: Oct-2024
https://doi.org/10.1016/j.ipl.2024.106534
Kamiyama N(2023)Pareto efficient matchings with pairwise preferencesTheoretical Computer Science10.1016/j.tcs.2023.113707948:COnline publication date: 9-Mar-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.113707
Ge SItoh T(2023)Popularity on the Roommate Diversity ProblemCombinatorial Optimization and Applications10.1007/978-3-031-49611-0_23(316-329)Online publication date: 15-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-49611-0_23
Aziz HBiró PFleiner TGaspers Sde Haan RMattei NRastegari B(2022)Stable matching with uncertain pairwise preferencesTheoretical Computer Science10.1016/j.tcs.2022.01.028909(1-11)Online publication date: Mar-2022
https://doi.org/10.1016/j.tcs.2022.01.028
Kamiyama N(2021)The envy-free matching problem with pairwise preferencesInformation Processing Letters10.1016/j.ipl.2021.106158(106158)Online publication date: Jun-2021
https://doi.org/10.1016/j.ipl.2021.106158

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents