Document Open Access Logo

Pairwise Preferences in the Stable Marriage Problem

Authors Ágnes Cseh , Attila Juhos

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.21.pdf
  • Filesize: 469 kB
  • 16 pages

Document Identifiers

Author Details

Ágnes Cseh
  • Institute of Economics, Centre for Economic and Regional Studies, Hungarian Academy of Sciences, 1097 Budapest, Tóth Kálmán u. 4., Hungary
Attila Juhos
  • Department of Computer Science and Information Theory, Budapest University of Technology and Economics, 1117 Budapest, Magyar Tudósok krt. 2., Hungary

Funding

This work was supported by the Cooperation of Excellences Grant (KEP-6/2018), by the Ministry of Human Resources under its New National Excellence Programme (ÚNKP-18-4-BME-331 and ÚNKP-18-1-I-BME-309), the Hungarian Academy of Sciences under its Momentum Programme (LP2016-3/2016), its János Bolyai Research Fellowship, and OTKA grant K128611.

Acknowledgements

The authors thank Tamás Fleiner, David Manlove, and Dávid Szeszlér for fruitful discussions on the topic.

Cite As Get BibTex

Ágnes Cseh and Attila Juhos. Pairwise Preferences in the Stable Marriage Problem. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.STACS.2019.21

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • stable marriage
  • intransitivity
  • acyclic preferences
  • poset
  • weakly stable matching
  • strongly stable matching
  • super stable matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. D. J. Abraham. Algorithmics of two-sided matching problems. Master’s thesis, University of Glasgow, Department of Computing Science, 2003. Google Scholar
  2. Alberto Alesina and Howard Rosenthal. A Theory of Divided Government. Econometrica, 64(6):1311-1341, 1996. URL: http://www.jstor.org/stable/2171833.
  3. Haris Aziz, Péter Biró, Tamás Fleiner, Serge Gaspers, Ronald de Haan, Nicholas Mattei, and Baharak Rastegari. Stable Matching with Uncertain Pairwise Preferences. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pages 344-352. International Foundation for Autonomous Agents and Multiagent Systems, 2017. Google Scholar
  4. Péter Biró. Applications of Matching Models under Preferences. Trends in Computational Social Choice, page 345, 2017. Google Scholar
  5. Péter Biró and Sofya Kiselgof. College admissions with stable score-limits. Central European Journal of Operations Research, 23(4):727-741, 2015. Google Scholar
  6. P Blavatsky. Content-dependent preferences in choice under risk: heuristic of relative probability comparisons. IIASA Interim Report, IR-03-031, 2003. Google Scholar
  7. Li Chen. University admission practices - Ireland, MiP Country Profile 8. http://www.matching-in-practice.eu/higher-education-in-ireland/, 2012.
  8. M.-J.-A.-N. de C. (Marquis de) Condorcet. Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. L'Imprimerie Royale, 1785. Google Scholar
  9. Ágnes Cseh and Attila Juhos. Pairwise preferences in the stable marriage problem. CoRR, 2018. URL: http://arxiv.org/abs/1810.00392.
  10. Linda Farczadi, Konstantinos Georgiou, and Jochen Könemann. Stable marriage with general preferences. Theory of Computing Systems, 59(4):683-699, 2016. Google Scholar
  11. P. Fishburn. Preference structures and their numerical representations. Theoretical Computer Science, 217:359-383, 1999. Google Scholar
  12. T. Fleiner, R. W. Irving, and D. F. Manlove. Efficient Algorithms for Generalised Stable Marriage and Roommates Problems. Theoretical Computer Science, 381:162-176, 2007. Google Scholar
  13. D. Gale and L. S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9-15, 1962. Google Scholar
  14. D. Gale and M. Sotomayor. Some remarks on the stable matching problem. Discrete Applied Mathematics, 11:223-232, 1985. Google Scholar
  15. P. Hall. On representatives of subsets. Journal of the London Mathematical Society, 10:26-30, 1935. Google Scholar
  16. Steven Humphrey. Non-transitive Choice: Event-Splitting Effects or Framing Effects? Economica, 68(269):77-96, 2001. Google Scholar
  17. R. W. Irving. An efficient algorithm for the "stable roommates" problem. Journal of Algorithms, 6:577-595, 1985. Google Scholar
  18. R. W. Irving. Stable marriage and indifference. Discrete Applied Mathematics, 48:261-272, 1994. Google Scholar
  19. R. W. Irving and D. F. Manlove. The stable roommates problem with ties. Journal of Algorithms, 43:85-105, 2002. Google Scholar
  20. R. W. Irving, D. F. Manlove, and S. Scott. The Hospitals / Residents problem with ties. In Magnús M. Halldórsson, editor, Proceedings of SWAT '00: the 7th Scandinavian Workshop on Algorithm Theory, volume 1851 of Lecture Notes in Computer Science, pages 259-271. Springer, 2000. Google Scholar
  21. R. W. Irving, D. F. Manlove, and S. Scott. Strong stability in the Hospitals / Residents problem. Technical Report TR-2002-123, University of Glasgow, Department of Computing Science, 2002. Revised May 2005. Google Scholar
  22. R. W. Irving, D. F. Manlove, and S. Scott. Strong stability in the Hospitals / Residents problem. In Proceedings of STACS '03: the 20th Annual Symposium on Theoretical Aspects of Computer Science, volume 2607 of Lecture Notes in Computer Science, pages 439-450. Springer, 2003. Full version available as [21]. Google Scholar
  23. Tobias Kalenscher, Philippe N Tobler, Willem Huijbers, Sander M Daselaar, and Cyriel MA Pennartz. Neural signatures of intransitive preferences. Frontiers in Human Neuroscience, 4:49, 2010. Google Scholar
  24. Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, and Katarzyna E Paluch. Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem. ACM Transactions on Algorithms, 3(2):15, 2007. Google Scholar
  25. Adam Kunysz, Katarzyna Paluch, and Pratik Ghosal. Characterisation of strongly stable matchings. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 107-119. Society for Industrial and Applied Mathematics, 2016. Google Scholar
  26. László Lovász and Michael D Plummer. Matching theory, volume 367. American Mathematical Soc., 2009. Google Scholar
  27. D. F. Manlove. The structure of stable marriage with indifference. Discrete Applied Mathematics, 122(1-3):167-181, 2002. Google Scholar
  28. D. F. Manlove. Algorithmics of Matching Under Preferences. World Scientific, 2013. Google Scholar
  29. Kenneth O. May. Intransitivity, Utility, and the Aggregation of Preference Patterns. Econometrica, 22(1):1-13, 1954. Google Scholar
  30. Ignacio Ríos, Tomás Larroucau, Giorgiogiulio Parra, and Roberto Cominetti. College Admissions Problem with Ties and Flexible Quotas. Technical report, SSRN, 2014. Google Scholar
  31. E. Ronn. On the complexity of stable matchings with and without ties. PhD thesis, Yale University, 1986. Google Scholar
  32. B. Spieker. The set of super-stable marriages forms a distributive lattice. Discrete Applied Mathematics, 58:79-84, 1995. Google Scholar
  33. Huffington Post 2016 General Election: Trump vs. Sanders. https://elections.huffingtonpost.com/pollster/2016-general-election-trump-vs-sanders. Accessed 3 September 2018.
  34. RealClearPolitics website. General Election: Trump vs. Sanders. https://www.realclearpolitics.com/epolls/2016/president/us/general_election_trump_vs_sanders-5565.html. Accessed 3 September 2018.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact