Document Open Access Logo

Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties

Authors Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki , Yu Yokoi

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.31.pdf
  • Filesize: 0.84 MB
  • 20 pages

Document Identifiers

Author Details

Hiromichi Goko
  • Frontier Research Center, Toyota Motor Corporation, Aichi, Japan
Kazuhisa Makino
  • Research Institute for Mathematical Sciences, Kyoto University, Japan
Shuichi Miyazaki
  • Academic Center for Computing and Media Studies, Kyoto University, Japan
Yu Yokoi
  • Principles of Informatics Research Division, National Institute of Informatics, Tokyo, Japan

Funding

This work was partially supported by the joint project of Kyoto University and Toyota Motor Corporation, titled "Advanced Mathematical Science for Mobility Society."
  • Makino, Kazuhisa: Supported by JSPS KAKENHI Grant Numbers JP19K22841, JP20H00609, and JP20H05967.
  • Miyazaki, Shuichi: Supported by JSPS KAKENHI Grant Numbers JP20K11677 and JP16H02782.
  • Yokoi, Yu: Supported by JSPS KAKENHI Grant Number JP18K18004 and JST PRESTO Grant Number JPMJPR212B.

Acknowledgements

The authors thank the anonymous reviewers for their helpful comments.

Cite AsGet BibTex

Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki, and Yu Yokoi. Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.31

Abstract

Motivated by the serious problem that hospitals in rural areas suffer from a shortage of residents, we study the Hospitals/Residents model in which hospitals are associated with lower quotas and the objective is to satisfy them as much as possible. When preference lists are strict, the number of residents assigned to each hospital is the same in any stable matching because of the well-known rural hospitals theorem; thus there is no room for algorithmic interventions. However, when ties are introduced to preference lists, this will no longer apply because the number of residents may vary over stable matchings. In this paper, we formulate an optimization problem to find a stable matching with the maximum total satisfaction ratio for lower quotas. We first investigate how the total satisfaction ratio varies over choices of stable matchings in four natural scenarios and provide the exact values of these maximum gaps. Subsequently, we propose a strategy-proof approximation algorithm for our problem; in one scenario it solves the problem optimally, and in the other three scenarios, which are NP-hard, it yields a better approximation factor than that of a naive tie-breaking method. Finally, we show inapproximability results for the above-mentioned three NP-hard scenarios.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Algorithmic game theory
Keywords
  • Stable matching
  • Hospitals/Residents problem
  • Lower quota
  • NP-hardness
  • Approximation algorithm
  • Strategy-proofness

Metrics

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

Related Versions

References

  1. Atila Abdulkadiroğlu, Parag A. Pathak, and Alvin E. Roth. The New York city high school match. American Economic Review, 95(2):364-367, 2005. Google Scholar
  2. Atila Abdulkadiroğlu, Parag A. Pathak, Alvin E. Roth, and Tayfun Sönmez. The Boston public school match. American Economic Review, 95(2):368-371, 2005. Google Scholar
  3. Ashwin Arulselvan, Ágnes Cseh, Martin Groß, David F. Manlove, and Jannik Matuschke. Matchings with lower quotas: Algorithms and complexity. Algorithmica, 80(1):185-208, 2018. URL: https://doi.org/10.1007/s00453-016-0252-6.
  4. Itai Ashlagi, Amin Saberi, and Ali Shameli. Assignment mechanisms under distributional constraints. Oper. Res., 68(2):467-479, 2020. URL: https://doi.org/10.1287/opre.2019.1887.
  5. Péter Biró, Tamás Fleiner, Robert W. Irving, and David F. Manlove. The College Admissions problem with lower and common quotas. Theor. Comput. Sci., 411(34-36):3136-3153, 2010. URL: https://doi.org/10.1016/j.tcs.2010.05.005.
  6. Niclas Boehmer and Klaus Heeger. A fine-grained view on stable many-to-one matching problems with lower and upper quotas. In Xujin Chen, Nikolai Gravin, Martin Hoefer, and Ruta Mehta, editors, Web and Internet Economics - 16th International Conference, WINE 2020, Beijing, China, December 7-11, 2020, Proceedings, volume 12495 of Lecture Notes in Computer Science, pages 31-44. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-64946-3_3.
  7. Robert Bredereck, Klaus Heeger, Dusan Knop, and Rolf Niedermeier. Multidimensional stable roommates with master list. In Xujin Chen, Nikolai Gravin, Martin Hoefer, and Ruta Mehta, editors, Web and Internet Economics - 16th International Conference, WINE 2020, Beijing, China, December 7-11, 2020, Proceedings, volume 12495 of Lecture Notes in Computer Science, pages 59-73. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-64946-3_5.
  8. Lester E. Dubins and David A. Freedman. Machiavelli and the Gale-Shapley algorithm. The American Mathematical Monthly, 88(7):485-494, 1981. Google Scholar
  9. Tamás Fleiner and Naoyuki Kamiyama. A matroid approach to stable matchings with lower quotas. Math. Oper. Res., 41(2):734-744, 2016. URL: https://doi.org/10.1287/moor.2015.0751.
  10. Daniel Fragiadakis, Atsushi Iwasaki, Peter Troyan, Suguru Ueda, and Makoto Yokoo. Strategyproof matching with minimum quotas. ACM Trans. Economics and Comput., 4(1):6:1-6:40, 2015. URL: https://doi.org/10.1145/2841226.
  11. David Gale and Lloyd S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  12. David Gale and Marilda Sotomayor. Some remarks on the stable matching problem. Discret. Appl. Math., 11(3):223-232, 1985. URL: https://doi.org/10.1016/0166-218X(85)90074-5.
  13. Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki, and Yu Yokoi. Maximally satisfying lower quotas in the hospitals/residents problem with ties. CoRR, abs/2105.03093, 2021. URL: http://arxiv.org/abs/2105.03093.
  14. Masahiro Goto, Atsushi Iwasaki, Yujiro Kawasaki, Ryoji Kurata, Yosuke Yasuda, and Makoto Yokoo. Strategyproof matching with regional minimum and maximum quotas. Artificial Intelligence, 235:40-57, 2016. Google Scholar
  15. Dan Gusfield and Robert W. Irving. The Stable marriage problem - structure and algorithms. Foundations of computing series. MIT Press, 1989. Google Scholar
  16. Koki Hamada, Kazuo Iwama, and Shuichi Miyazaki. The Hospitals/Residents problem with lower quotas. Algorithmica, 74(1):440-465, 2016. URL: https://doi.org/10.1007/s00453-014-9951-z.
  17. Koki Hamada, Shuichi Miyazaki, and Hiroki Yanagisawa. Strategy-proof approximation algorithms for the stable marriage problem with ties and incomplete lists. In Pinyan Lu and Guochuan Zhang, editors, 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China, volume 149 of LIPIcs, pages 9:1-9:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2019.9.
  18. Joseph D. Horton and Kyriakos Kilakos. Minimum edge dominating sets. SIAM J. Discret. Math., 6(3):375-387, August 1993. Google Scholar
  19. Chien-Chung Huang. Classified stable matching. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1235-1253. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.99.
  20. Robert W. Irving. Stable marriage and indifference. Discret. Appl. Math., 48(3):261-272, 1994. URL: https://doi.org/10.1016/0166-218X(92)00179-P.
  21. Robert W. Irving, David F. Manlove, and Sandy Scott. The stable marriage problem with master preference lists. Discret. Appl. Math., 156(15):2959-2977, 2008. URL: https://doi.org/10.1016/j.dam.2008.01.002.
  22. Naoyuki Kamiyama. Stable matchings with ties, master preference lists, and matroid constraints. In Martin Hoefer, editor, Algorithmic Game Theory - 8th International Symposium, SAGT 2015, Saarbrücken, Germany, September 28-30, 2015, Proceedings, volume 9347 of Lecture Notes in Computer Science, pages 3-14. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48433-3_1.
  23. Naoyuki Kamiyama. Many-to-many stable matchings with ties, master preference lists, and matroid constraints. In Edith Elkind, Manuela Veloso, Noa Agmon, and Matthew E. Taylor, editors, Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '19, Montreal, QC, Canada, May 13-17, 2019, pages 583-591. International Foundation for Autonomous Agents and Multiagent Systems, 2019. URL: http://dl.acm.org/citation.cfm?id=3331743.
  24. Dénes Kőnig. Über graphen und ihre anwendung auf determinantentheorie und mengenlehre. Mathematische, 77(4):453-465, 1916. Google Scholar
  25. Zoltán Király. Linear time local approximation algorithm for maximum stable marriage. Algorithms, 6(3):471-484, 2013. URL: https://doi.org/10.3390/a6030471.
  26. Prem Krishnaa, Girija Limaye, Meghana Nasre, and Prajakta Nimbhorkar. Envy-freeness and relaxed stability: Hardness and approximation algorithms. In Tobias Harks and Max Klimm, editors, Algorithmic Game Theory - 13th International Symposium, SAGT 2020, Augsburg, Germany, September 16-18, 2020, Proceedings, volume 12283 of Lecture Notes in Computer Science, pages 193-208. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-57980-7_13.
  27. Krishnapriya A. M., Meghana Nasre, Prajakta Nimbhorkar, and Amit Rawat. How good are popular matchings? In Gianlorenzo D'Angelo, editor, 17th International Symposium on Experimental Algorithms, SEA 2018, June 27-29, 2018, L'Aquila, Italy, volume 103 of LIPIcs, pages 9:1-9:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.SEA.2018.9.
  28. David F. Manlove. Algorithmics of Matching Under Preferences, volume 2 of Series on Theoretical Computer Science. WorldScientific, 2013. URL: https://doi.org/10.1142/8591.
  29. David F. Manlove, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki, and Yasufumi Morita. Hard variants of stable marriage. Theor. Comput. Sci., 276(1-2):261-279, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00206-7.
  30. Alvin Roth. The evolution of the labor market for medical interns and residents: A case study in game theory. Journal of Political Economy, 92(6):991-1016, 1984. Google Scholar
  31. Alvin Roth. On the allocation of residents to rural hospitals: A general property of two-sided matching markets. Econometrica, 54(2):425-27, 1986. Google Scholar
  32. Alvin E. Roth. The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4):617-628, 1982. Google Scholar
  33. Yu Yokoi. Envy-free matchings with lower quotas. Algorithmica, 82(2):188-211, 2020. URL: https://doi.org/10.1007/s00453-018-0493-7.
  34. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput., 3(1):103-128, 2007. URL: https://doi.org/10.4086/toc.2007.v003a006.
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 Imprint Privacy Contact