On a many-sided matching problem with mixed preferences

• Autorzy: Anholcer Marcin , Bartkowiak Maciej

Identyfikatory

DOI

10.37190/ord240301

• Języki publikacji: EN

Abstrakty

EN

Motivated by recent results on lexicographic and cyclic preferences, we present new sufficient conditions for the existence of stable matching in many-sided matching problems. Here, our focus shifted towards integrating the two-sided matching problem, characterized by reciprocal preferences, with the many-sided matching problem, which involves cyclic preferences. In particular, we show that one of the configurations presented recently by Zhang and Zhong for three-sided matching problems can be generalized to more dimensions. In our setting, the preferences are cyclic and, in the case of all but two pairs of consecutive sets of agents, also reciprocal, which generalizes the three-set setting of Zhang and Zhong. Our approach can be also applied to generalize the problems with any system of cyclic preferences for which the existence of a stable matching is guaranteed.

Słowa kluczowe

EN

many-sided matching problem; stable matching; cyclic preferences; lexicographic preferences; mixed preferences; deferred acceptance algorithm

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Operations Research and Decisions
• Rocznik: 2024
• Tom: Vol. 34, No. 3
• Strony: 1--13
• Opis fizyczny: Bibliogr. 32 poz., tab.

Twórcy

autor

Anholcer Marcin

• Institute of Informatics and Quantitative Economics, Poznań University of Economics and Business, Poznań, Poland

• https://orcid.org/0000-0001-7322-7095

autor

Bartkowiak Maciej

• Doctoral School, Poznań University of Economics and Business, Poznań, Poland

• https://orcid.org/0000-0002-9377-9927

Bibliografia

• [1] Abraham, D. J., Irving, R. W., and Manlove, D. F. Two algorithms for the Student-Project Allocation problem. Journal of Discrete Algorithms 5, 1 (2007), 73–90.
• [2] Alkan, A. Nonexistence of stable threesome matchings. Mathematical Social Sciences 16, 2 (1988), 207–209.
• [3] Arenas, J., and Torres-Martínez, J. P. Reconsidering the existence of stable solutions in three-sided matching problems with mixed preferences. Journal of Combinatorial Optimization 45, 2 (2023), 62.
• [4] Biró, P., and McDermid, E. Three-sided stable matchings with cyclic preferences. Algorithmica 58, 1 (2010), 5–18.
• [5] Biró, P., van de Klundert, J., Manlove, D., Pettersson, W., Andersson, T., Burnapp, L., Chromy, P., Delgado, P., Dworczak, P., Haase, B., Hemke, A., Johnson, R., Klimentova, X., Kuypers, D., Nanni Costa, A., Smeulders, B., Spieksma, F., Valentín, M. O., and Viana, A. Modelling and optimisation in European kidney exchange programmes. European Journal of Operational Research 291, 2 (2021), 447–456.
• [6] Boros, E., Gurvich, V., Jaslar, S., and Krasner, D. Stable matchings in three-sided systems with cyclic preferences. Discrete Mathematics 289, 1 (2004), 1–10.
• [7] Cseh, Á., Escamocher, G., Genç, B., and Quesada, L. A collection of constraint programming models for the threedimensional stable matching problem with cyclic preferences. Constraints 27, 3 (2022), 249–283.
• [8] Cui, L., and Jia, W. Cyclic stable matching for three-sided networking services. Computer Networks 57, 1 (2013), 351–363.
• [9] Danilov, V. I. Existence of stable matchings in some three-sided systems. Mathematical Social Sciences 46, 2 (2003), 145–148.
• [10] Eriksson, K., Sjöstrand, J., and Strimling, P. Three-dimensional stable matching with cyclic preferences. Mathematical Social Sciences 52, 1 (2006), 77–87.
• [11] Fajardo-Delgado, D., Hernández-Bernal, C., Sánchez-Cervantes, M. G., Trejo-Sánchez, J. A., EspinosaCuriel, I. E., and Molinar-Solis, J. E. Stable matching of users in a ridesharing model. Applied Sciences 12, 15 (2022), 7797.
• [12] Gale, D., and Shapley, L. S. College admissions and the stability of marriage. The American Mathematical Monthly 69, 1 (1962), 9–15.
• [13] Hitsch, G. J., Hortaçsu, A., and Ariely, D. Matching and sorting in online dating. American Economic Review 100, 1 (2010), 130–163.
• [14] Hofbauer, J. d-dimensional stable matching with cyclic preferences. Mathematical Social Sciences 82, (2016), 72–76.
• [15] Huang, C.-C. Circular stable matching and 3-way kidney transplant. Algorithmica 58, 1 (2010), 137–150.
• [16] Irving, R. W. An efficient algorithm for the “stable roommates” problem. Journal of Algorithms 6, 4 (1985), 577–595.
• [17] Irving, R. W. Stable marriage and indifference. Discrete Applied Mathematics 48, 3 (1994), 261–272.
• [18] Irving, R. W., and Leather, P. The complexity of counting stable marriages. SIAM Journal on Computing 15, 3 (1986), 655–667.
• [19] Kamiyama, N. A new approach to the Pareto stable matching problem. Mathematics of Operations Research 39, 3 (2014), 851–862.
• [20] Kato, A. Complexity of the sex-equal stable marriage problem. Japan Journal of Industrial and Applied Mathematics 10, 1 (1993), 1–19.
• [21] Klimentova, X., Biró, P., Viana, A., Costa, V., and Pedroso, J. P. Novel integer programming models for the stable kidney exchange problem. European Journal of Operational Research 307, 3 (2023), 1391–1407.
• [22] Knuth, D. E. Stable marriages and their relations to other combinatorial problems: An introduction to the mathematical analysis of algorithms (Aisenstadt Chair Collection). Presses de l’Université de Montréal, 1976 (in French).
• [23] Lahiri, S. Three-sided matchings and separable preferences. In Contributions to Game Theory and Management, Vol. 2. Collected papers presented on the Second International Conference Game Theory and Management, June 26-27, 2008 (St. Petersburg, Russia, 2009), L. A. Petrosjan and N. A. Zenkevich, Eds., Graduate School of Management SPbU, pp. 251–259.
• [24] Lam, C.-K., and Plaxton, C. G. On the existence of three-dimensional stable matchings with cyclic preferences. Theory of Computing Systems 66, 3 (2022), 679–695.
• [25] Lerner, E. A counterexample of size 20 for the problem of finding a 3-dimensional stable matching with cyclic preferences. Discrete Applied Mathematics 333 (2023), 1–12.
• [26] Manlove, D. F. The structure of stable marriage with indifference. Discrete Applied Mathematics 122, 1 (2002), 167–181.
• [27] Pashkovich, K., and Poirrier, L. Three-dimensional stable matching with cyclic preferences, 2018. Working paper version available from arXiv: https://doi.org/10.48550/arXiv.1807.05638.
• [28] Perach, N., and Anily, S. Stable matching of student-groups to dormitories. European Journal of Operational Research 302, 1 (2022), 50–61.
• [29] Ren, M., Yang, L., Jiang, H., Chen, J., and Zhou, Y. Energy-delay tradeoff in helper-assisted NOMA-MEC systems: A four-sided matching algorithm, 2023. Working paper version available from arXiv: https://doi.org/10.48550/arXiv.2301.10624.
• [30] Roth, A. E., Sönmez, T., and Ünver, M. U. Pairwise kidney exchange. Journal of Economic Theory 125, 2 (2005), 151–188.
• [31] Ünver, M. U. On the survival of some unstable two-sided matching mechanisms. International Journal of Game Theory 33, 2 (2005), 239–254.
• [32] Zhang, F., and Zhong, L. Three-sided matching problem with mixed preferences. Journal of Combinatorial Optimization 42 (2021), 928–936.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).