Popular Maximum-Utility Matchings with Matroid Constraints

References

• [1] Abdulkadiroğlu A, Sönmez T (1999) House allocation with existing tenants. J. Econom. Theory 88(2):233–260.Crossref, Google Scholar
• [2] Abraham DJ, Irving RW, Kavitha T, Mehlhorn K (2007) Popular matchings. SIAM J. Comput. 37(4):1030–1045.Crossref, Google Scholar
• [3] Biró P, Irving RW, Manlove DF (2010) Popular matchings in the marriage and roommates problems. Calamoneri T, Diaz J, eds. Algorithms Complexity, CIAC 2010, Lecture Notes in Computer Science, vol. 6078 (Springer, Berlin, Heidelberg), 97–108.Google Scholar
• [4] Brandl F, Kavitha T (2018) Popular matchings with multiple partners. 37th IARCS Annual Conf. Foundations Software Tech. Theoret. Comput. Sci. (FSTTCS), Leibniz International Proceedings in Informatics (LIPIcs), vol. 93 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 19:1–19:15.Google Scholar
• [5] Brandl F, Kavitha T (2019) Two problems in max-size popular matchings. Algorithmica 81(7):2738–2764.Crossref, Google Scholar
• [6] Condorcet N (1785) Essai sur L’application de L’analyse à la Probabilité des Décisions Rendues à la Pluralité des Voix (de l’Imprimerie Royale, Paris).Google Scholar
• [7] Csáji G (2024) Popularity and perfectness in one-sided matching markets with capacities. Preprint, submitted March 1, https://arxiv.org/abs/2403.00598.Google Scholar
• [8] Csáji G, Király T, Yokoi Y (2024) Solving the maximum popular matching problem with matroid constraints. SIAM J. Discrete. Math. 38(3):2226–2242.Crossref, Google Scholar
• [9] Cseh Á, Kavitha T (2018) Popular edges and dominant matchings. Math. Programming 172(1):209–229.Crossref, Google Scholar
• [10] Cseh Á, Huang C-C, Kavitha T (2017) Popular matchings with two-sided preferences and one-sided ties. SIAM J. Discrete. Math. 31(4):2348–2377.Crossref, Google Scholar
• [11] Ehlers L, Hafalir IE, Yenmez MB, Yildirim MA (2014) School choice with controlled choice constraints: Hard bounds versus soft bounds. J. Econom. Theory 153:648–683.Crossref, Google Scholar
• [12] El Maalouly N (2023) Exact matching: Algorithms and related problems. 40th Internat. Sympos. Theoret. Aspects Comput. Sci. (STACS), Leibniz International Proceedings in Informatics (LIPIcs), vol. 254 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 29:1–29:17.Google Scholar
• [13] Faenza Y, Kavitha T, Powers V, Zhang X (2019) Popular matchings and limits to tractability. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 2790–2809.Google Scholar
• [14] Fleiner T (2001) A matroid generalization of the stable matching polytope. Aardal K, Gerards B, eds. Integer Programming Combin. Optim. IPCO 2001, Lecture Notes in Computer Science, vol. 2081 (Springer, Berlin, Heidelberg), 105–114.Google Scholar
• [15] Fleiner T (2003) A fixed-point approach to stable matchings and some applications. Math. Oper. Res. 28(1):103–126.Link, Google Scholar
• [16] Frank A (2011) Connections in Combinatorial Optimization, Oxford Lecture Series in Mathematics and Its Applications, vol. 38 (Oxford University Press, Oxford, UK).Google Scholar
• [17] Fujishige S, Tamura A (2007) A two-sided discrete-concave market with possibly bounded side payments: An approach by discrete convex analysis. Math. Oper. Res. 32(1):136–155.Link, Google Scholar
• [18] Fujishige S, Yang Z (2003) A note on Kelso and Crawford’s gross substitutes condition. Math. Oper. Res. 28(3):463–469.Link, Google Scholar
• [19] Gärdenfors P (1975) Match making: Assignments based on bilateral preferences. Behav. Sci. 20(3):166–173.Crossref, Google Scholar
• [20] Ghouila-Houri A (1962) Characterisation des matrices totalement unimodulaires. CR Acad/Sci. Paris 254:1192–1194.Google Scholar
• [21] Gupta S, Misra P, Saurabh S, Zehavi M (2019) Popular matching in roommates setting is NP-hard. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 2810–2822.Google Scholar
• [22] Huang CC, Kavitha T (2011) Popular matchings in the stable marriage problem. Aceto L, Henzinger M, Sgall J, eds. Automata, Languages Programming, ICALP 2011, Lecture Notes in Computer Science, vol. 6755 (Springer, Berlin, Heidelberg), 666–677.Google Scholar
• [23] Kamada Y, Kojima F (2015) Efficient matching under distributional constraints: Theory and applications. Amer. Econom. Rev. 105(1):67–99.Crossref, Google Scholar
• [24] Kamiyama N (2017) Popular matchings with ties and matroid constraints. SIAM J. Discrete Math. 31(3):1801–1819.Crossref, Google Scholar
• [25] Kamiyama N (2020) Popular matchings with two-sided preference lists and matroid constraints. Theoret. Comput. Sci. 809:265–276.Crossref, Google Scholar
• [26] Kavitha T (2014) A size-popularity tradeoff in the stable marriage problem. SIAM J. Comput. 43(1):52–71.Crossref, Google Scholar
• [27] Kavitha T (2024) Maximum matchings and popularity. SIAM J. Discrete Math. 38(2):1202–1221.Google Scholar
• [28] Kavitha T (2021) Matchings, critical nodes, and popular solutions. 41st IARCS Annual Conf. Foundations Software Tech. Theoret. Comput. Sci. (FSTTCS), Leibniz International Proceedings in Informatics (LIPIcs), vol. 213 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 25:1–25:19.Google Scholar
• [29] Kavitha T (2025) Popular solutions for optimal matchings. Kráľ D, Milanič M, eds. Graph-Theoret. Concepts Comput. Sci. WG 2024, Lecture Notes in Computer Science, vol. 14760 (Springer, Cham, Switzerland), 297–311.Google Scholar
• [30] Kavitha T, Makino K, Schlotter I, Yokoi Y (2024) Arborescences, colorful forests, and popularity. Proc. 2024 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 3724–3746.Google Scholar
• [31] Kavitha T, Király T, Matuschke J, Schlotter I, Schmidt-Kraepelin U (2022) Popular branchings and their dual certificates. Math. Programming 192(1):567–595.Crossref, Google Scholar
• [32] Kavitha T, Király T, Matuschke J, Schlotter I, Schmidt-Kraepelin U (2022) The popular assignment problem: When cardinality is more important than popularity. Proc. 2022 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 103–123.Google Scholar
• [33] Kelso AS Jr, Crawford VP (1982) Job matching, coalition formation, and gross substitutes. Econometrica 50(6):1483–1504.Crossref, Google Scholar
• [34] Kojima F, Tamura A, Yokoo M (2018) Designing matching mechanisms under constraints: An approach from discrete convex analysis. J. Econom. Theory 176:803–833.Crossref, Google Scholar
• [35] Kuffner L (2023) Matroid generalizations of popular matchings. Internship report, École Normale Supérieure, Paris.Google Scholar
• [36] Lovász L, Recski A (1982) Selected topics of matroid theory and its applications. Proc. 10th Winter School Abstract Anal. (Circolo Matematico di Palermo, Palermo, Italy), 171–185.Google Scholar
• [37] Manlove DF, Sng CTS (2006) Popular matchings in the capacitated house allocation problem. Azar Y, Erlebach T, eds. Algorithms – ESA 2006, Lecture Notes in Computer Science, vol. 4168 (Springer, Berlin, Heidelberg), 492–503.Google Scholar
• [38] Merrill S, Grofman B (1999) A Unified Theory of Voting: Directional and Proximity Spatial Models (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [39] Murota K (1996) Valuated matroid intersection I: Optimality criteria. SIAM J. Discrete. Math. 9(4):545–561.Crossref, Google Scholar
• [40] Murota K (1996) Valuated matroid intersection II: Algorithms. SIAM J. Discrete. Math. 9(4):562–576.Crossref, Google Scholar
• [41] Murota K (2003) Discrete Convex Analysis (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [42] Murota K (2016) Discrete convex analysis: A tool for economics and game theory. J. Mechanism Inst. Design 1(1):149–271.Crossref, Google Scholar
• [43] Murota K, Shioura A (2018) Simpler exchange axioms for M-concave functions on generalized polymatroids. Japan J. Indust. Appl. Math. 35:235–259.Crossref, Google Scholar
• [44] Murota K, Yokoi Y (2015) On the lattice structure of stable allocations in a two-sided discrete-concave market. Math. Oper. Res. 40(2):460–473.Link, Google Scholar
• [45] Paluch K (2014) Popular and clan-popular b-matchings. Theoret. Comput. Sci. 544:3–13.Crossref, Google Scholar
• [46] Papadimitriou CH, Yannakakis M (1982) The complexity of restricted spanning tree problems. J. ACM 29(2):285–309.Crossref, Google Scholar
• [47] Robinson GC, Welsh DJA (1980) The computational complexity of matroid properties. Math. Proc. Cambridge Philos. Soc. 87(1):29–45.Google Scholar
• [48] Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, vol. 24 (Springer, Berlin, Heidelberg).Google Scholar
• [49] Tardos É (1985) Generalized matroids and supermodular colourings. Lovász L, Recski A, eds. Matroid Theory (North-Holland, Amsterdam), 359–382.Google Scholar
• [50] Zhang J, Tang B, Miao X, Yin J (2023) Reallocation mechanisms under distributional constraints in the full preference domain. Garg J, Klimm M, Kong Y, eds. Web Internet Econom. WINE 2023, Lecture Notes in Computer Science, vol. 14413 (Springer, Cham, Switzerland), 654–671.Google Scholar