Stable fractional matchings. (English) Zbl 1521.91244
Summary: We study a generalization of the classical stable matching problem that allows for cardinal preferences (as opposed to ordinal) and fractional matchings (as opposed to integral). In this cardinal setting, stable fractional matchings can have much larger social welfare than stable integral ones. Our goal is to understand the computational complexity of finding an optimal (i.e., welfare-maximizing) stable fractional matching. We consider both exact and approximate stability notions, and provide simple approximation algorithms with weak welfare guarantees. Our main result is that, somewhat surprisingly, achieving better approximations is computationally hard. To the best of our knowledge, these are the first computational complexity results for stable fractional matchings in the cardinal model. En route to these results, we provide a number of structural observations that could be of independent interest.
References:
| [1] | Gale, D.; Shapley, L. S., College admissions and the stability of marriage, Am. Math. Mon., 69, 1, 9-15 (1962) · Zbl 0109.24403 |
| [2] | Gusfield, D.; Irving, R. W., The Stable Marriage Problem: Structure and Algorithms (1989), MIT Press · Zbl 0703.68046 |
| [3] | Roth, A. E.; Sotomayor, M. A.O., Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis (1990), Cambridge University Press · Zbl 0726.90003 |
| [4] | Knuth, D. E., Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms, Vol. 10 (1997), American Mathematical Soc. |
| [5] | Manlove, D. F., Algorithmics of Matching Under Preferences, Vol. 2 (2013), World Scientific · Zbl 1283.68018 |
| [6] | Roth, A. E., The evolution of the labor market for medical interns and residents: a case study in game theory, J. Polit. Econ., 92, 6, 991-1016 (1984) |
| [7] | Roth, A. E.; Peranson, E., The redesign of the matching market for American physicians: some engineering aspects of economic design, Am. Econ. Rev., 89, 4, 748-780 (1999) |
| [8] | Abdulkadiroğlu, A.; Pathak, P. A.; Roth, A. E., The New York City High School Match, Am. Econ. Rev., 364-367 (2005) |
| [9] | Roth, A. E.; Sönmez, T.; Ünver, M. U., Kidney exchange, Q. J. Econ., 119, 2, 457-488 (2004) · Zbl 1064.92029 |
| [10] | Wang, X.; Agatz, N.; Erera, A., Stable matching for dynamic ride-sharing systems, Transp. Sci., 52, 4, 850-867 (2018) |
| [11] | Roth, A. E.; Rothblum, U. G.; Vande Vate, J. H., Stable matchings, optimal assignments, and linear programming, Math. Oper. Res., 18, 4, 803-828 (1993) · Zbl 0806.90085 |
| [12] | Bogomolnaia, A.; Moulin, H., Random matching under dichotomous preferences, Econometrica, 72, 1, 257-279 (2004) · Zbl 1142.91691 |
| [13] | Bronfman, S.; Alon, N.; Hassidim, A.; Romm, A., Redesigning the Israeli Medical Internship Match, ACM Trans. Econ. Comput., 6, 3-4, 1-18 (2018) |
| [14] | Gudmundsson, J., Compromises and rewards: stable and non-manipulable probabilistic matching, Int. J. Game Theory, 48, 2, 365-392 (2019) · Zbl 1417.91382 |
| [15] | Li, Z.; Lieberman, K.; Macke, W.; Carrillo, S.; Ho, C.-J.; Wellen, J.; Das, S., Incorporating compatible pairs in kidney exchange: a dynamic weighted matching model, (Proceedings of the 2019 ACM Conference on Economics and Computation (2019), ACM), 349-367 |
| [16] | Anshelevich, E.; Das Matching, S., Cardinal utility, and social welfare, ACM SIGecom Exch., 9, 1, 4 (2010) |
| [17] | Pini, M. S.; Rossi, F.; Venable, K. B.; Walsh, T., Stability, optimality and manipulation in matching problems with weighted preferences, Algorithms, 6, 4, 782-804 (2013) · Zbl 1461.05170 |
| [18] | Echenique, F.; Wilson, A. J.; Yariv, L., Clearinghouses for two-sided matching: an experimental study, Quant. Econ., 7, 2, 449-482 (2016) · Zbl 1396.91567 |
| [19] | Anshelevich, E.; Das, S.; Naamad, Y., Anarchy, stability, and utopia: creating better matchings, Auton. Agents Multi-Agent Syst., 26, 1, 120-140 (2013) |
| [20] | Gusfield, D., Three fast algorithms for four problems in stable marriage, SIAM J. Comput., 16, 1, 111-128 (1987) · Zbl 0635.68036 |
| [21] | Irving, R. W.; Leather, P.; Gusfield, D., An efficient algorithm for the “optimal” stable marriage, J. ACM, 34, 3, 532-543 (1987) |
| [22] | Teo, C.-P.; Sethuraman, J., The geometry of fractional stable matchings and its applications, Math. Oper. Res., 23, 4, 874-891 (1998) · Zbl 0977.90046 |
| [23] | Manlove, D. F.; Irving, R. W.; Iwama, K.; Miyazaki, S.; Morita, Y., Hard variants of stable marriage, Theor. Comput. Sci., 276, 1-2, 261-279 (2002) · Zbl 1050.68171 |
| [24] | Mai, T.; Vazirani, V. V., A natural generalization of stable matching solved via new insights into ideal cuts, preprint |
| [25] | Kato, A., Complexity of the sex-equal stable marriage problem, Jpn. J. Ind. Appl. Math., 10, 1, 1 (1993) · Zbl 0782.68060 |
| [26] | Feder, T., A new fixed point approach for stable networks and stable marriages, J. Comput. Syst. Sci., 45, 2, 233-284 (1992) · Zbl 0772.68052 |
| [27] | Iwama, K.; Miyazaki, S.; Morita, Y.; Manlove, D. F., Stable marriage with incomplete lists and ties, (International Colloquium on Automata, Languages, and Programming (1999), Springer), 443-452 · Zbl 0948.90155 |
| [28] | Irving, R. W.; Manlove, D. F.; O’Malley, G., Stable marriage with ties and bounded length preference lists, J. Discret. Algorithms, 7, 2, 213-219 (2009) · Zbl 1187.68346 |
| [29] | Drummond, J.; Boutilier, C., Elicitation and approximately stable matching with partial preferences, (Twenty-Third International Joint Conference on Artificial Intelligence (2013)), 97-105 |
| [30] | Rastegari, B.; Goldberg, P.; Manlove, D. F., Preference elicitation in matching markets via interviews: a study of offline benchmarks, (Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems (2016)), 1393-1394 |
| [31] | Goto, M.; Iwasaki, A.; Kawasaki, Y.; Kurata, R.; Yasuda, Y.; Yokoo, M., Strategyproof matching with regional minimum and maximum quotas, Artif. Intell., 235, 40-57 (2016) · Zbl 1354.91103 |
| [32] | Hamada, N.; Hsu, C.-L.; Kurata, R.; Suzuki, T.; Ueda, S.; Yokoo, M., Strategy-proof school choice mechanisms with minimum quotas and initial endowments, Artif. Intell., 249, 47-71 (2017) · Zbl 1425.91346 |
| [33] | Gent, I. P.; Prosser, P.; Smith, B.; Walsh, T., SAT encodings of the stable marriage problem with ties and incomplete lists, (Fifth International Symposium on the Theory and Applications of Satisfiability Testing (2002)), 133-140 |
| [34] | Drummond, J.; Perrault, A.; Bacchus, F., SAT is an effective and complete method for solving stable matching problems with couples, (Twenty-Fourth International Joint Conference on Artificial Intelligence (2015)), 518-525 |
| [35] | Perrault, A.; Drummond, J.; Bacchus, F., Strategy-proofness in the stable matching problem with couples, (Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems (2016)), 132-140 |
| [36] | Gent, I. P.; Irving, R. W.; Manlove, D. F.; Prosser, P.; Smith, B. M., A constraint programming approach to the stable marriage problem, (International Conference on Principles and Practice of Constraint Programming (2001), Springer), 225-239 · Zbl 1067.68639 |
| [37] | Manlove, D. F.; O’Malley, G.; Prosser, P.; Unsworth, C., A constraint programming approach to the hospitals/residents problem, (International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming (2007), Springer), 155-170 · Zbl 1214.90102 |
| [38] | Manlove, D. F.; McBride, I.; Trimble, J., “Almost-stable” matchings in the hospitals/residents problem with couples, Constraints, 22, 1, 50-72 (2017) · Zbl 1387.90143 |
| [39] | Endriss, U., Analysis of one-to-one matching mechanisms via SAT solving: impossibilities for universal axioms, (Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (2020), AAAI Press), 1918-1925 |
| [40] | Vande Vate, J. H., Linear programming brings marital bliss, Oper. Res. Lett., 8, 3, 147-153 (1989) · Zbl 0675.90058 |
| [41] | Rothblum, U. G., Characterization of stable matchings as extreme points of a polytope, Math. Program., 54, 1-3, 57-67 (1992) · Zbl 0773.90059 |
| [42] | Vohra, R. V., Stable matchings and linear programming, Curr. Sci., 105, 9, 1051-1055 (2012) |
| [43] | Chen, X.; Ding, G.; Hu, X.; Zang, W., The maximum-weight stable matching problem: duality and efficiency, SIAM J. Discrete Math., 26, 3, 1346-1360 (2012) · Zbl 1282.90105 |
| [44] | Aharoni, R.; Fleiner, T., On a lemma of Scarf, J. Comb. Theory, Ser. B, 87, 1, 72-80 (2003) · Zbl 1058.05031 |
| [45] | Biró, P.; Fleiner, T., Fractional solutions for capacitated NTU-games, with applications to stable matchings, Discrete Optim., 22, 241-254 (2016) · Zbl 1390.91027 |
| [46] | Aziz, H.; Klaus, B., Random matching under priorities: stability and no envy concepts, Soc. Choice Welf., 1-47 (2019) · Zbl 1425.91337 |
| [47] | Deligkas, A.; Mertzios, G. B.; Spirakis, P. G., The computational complexity of weighted greedy matching, (Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (2017), AAAI Press), 317-325 |
| [48] | V. Manjunath, Stability and the Core of Probabilistic Marriage Problems, Available at SSRN 1809941. |
| [49] | Hatfield, J. W.; Kominers, S. D.; Nichifor, A.; Ostrovsky, M.; Westkamp, A., Stability and competitive equilibrium in trading networks, J. Polit. Econ., 121, 5, 966-1005 (2013) |
| [50] | Hatfield, J. W.; Kominers, S. D., Multilateral matching, J. Econ. Theory, 156, 175-206 (2015) · Zbl 1314.91167 |
| [51] | Doğan, B.; Yıldız, K., Efficiency and stability of probabilistic assignments in marriage problems, Games Econ. Behav., 95, 47-58 (2016) · Zbl 1347.91203 |
| [52] | Echenique, F.; Galichon, A., Ordinal and cardinal solution concepts for two-sided matching, Games Econ. Behav., 101, 63-77 (2017) · Zbl 1393.91118 |
| [53] | Ágoston, K. C.; Biró, P.; McBride, I., Integer programming methods for special college admissions problems, J. Comb. Optim., 32, 4, 1371-1399 (2016) · Zbl 1356.90119 |
| [54] | Delorme, M.; García, S.; Gondzio, J.; Kalcsics, J.; Manlove, D.; Pettersson, W., Mathematical models for stable matching problems with ties and incomplete lists, Eur. J. Oper. Res., 277, 2, 426-441 (2019) · Zbl 1431.91252 |
| [55] | Narang, S.; Narahari, Y., A study of incentive compatibility and stability issues in fractional matchings, preprint |
| [56] | Lipton, R. J.; Markakis, E.; Mehta, A., Playing large games using simple strategies, (Proceedings of the Fourth ACM Conference on Electronic Commerce (2003), ACM), 36-41 |
| [57] | Barman, S., Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory’s theorem, SIAM J. Comput., 47, 3, 960-981 (2018) · Zbl 1416.91016 |
| [58] | Yoshinaka, R., Higher-order matching in the linear lambda calculus in the absence of constants is NP-complete, (Proceedings of the Sixteenth International Conference on Term Rewriting and Applications (2005), Springer-Verlag), 235-249 · Zbl 1078.68045 |
| [59] | Irving, R. W., An efficient algorithm for the “stable roommates” problem, J. Algorithms, 6, 4, 577-595 (1985) · Zbl 0581.05001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
