Email this article 
STABLE MATCHINGS, CHOICE FUNCTIONS, AND LINEAR ORDERS
- Authors: Karzanov A.V.1
-
Affiliations:
- The Central Economic Mathematical Institute of the Russian Academy of Sciences
- Issue: Vol 65, No 1 (2025)
- Pages: 120-138
- Section: Computer science
- URL: https://journals.rcsi.science/0044-4669/article/view/287390
- DOI: https://doi.org/10.31857/S0044466925010114
- EDN: https://elibrary.ru/CCGHHA
- ID: 287390
Cite item
Abstract
A model of stable edge subsets (“matchings”) in a bipartite graph G = (V, E) is considered, in which preferences for vertices of one side (“firms”) are given by choice functions with standard properties of consistency, substitutability, and cardinal monotonicity, and preferences for vertices of the other side (“workers”) are given by linear orders. For such a model,we give a combinatorial description of the structure of rotations and propose an algorithm for constructing a rotation poset with a time complexity estimate O(|E|2) (including calls to oracles associated with choice functions). As a consequence, a “compact” affine representation of stable matchings can be obtained and related problems can be solved efficiently.
About the authors
A. V. Karzanov
The Central Economic Mathematical Institute of the Russian Academy of Sciences
Email: akarzanov7@gmail.com
Moscow, Russia
References
- Gale D. and Shapley L.S. College admissions and the stability of marriage // Amer. Math. Monthly 69 (1) (1962) 9–15.
- Gusfield D. and Irving R.W. The stable marriage problem: structure and algorithms, MIT press, 1989.
- Manlove D. Algorithmics of matching under preferences, Vol. 2, World Scientific, 2013.
- Kelso A.S. and Crawford V.P. Job matching, coalition formation and gross substitutes // Econometrica 50 (1982) 1483–1504.
- Roth A.E. Stability and polarization of interests in job matching // Econometrica 52 (1984) 47–57.
- Blair C. The lattice structure of the set of stable matchings with multiple partners // Math. Oper. Res. 13 (1988) 619–628.
- Plott C.R. Path independence, rationality, and social choice // Econometrica 41 (6) (1973) 1075–1091.
- Alkan A. On preferences over subsets and the lattice structure of stable matchings // Review of Economic Design 6 (1) (2001) 99–111.
- Alkan A. A class of multipartner matching models with a strong lattice structure // Econom. Theory 19 (2002) 737–746.
- Birkhoff G. Rings of sets // Duke Mathematical Journal 3 (3) (1937) 443–454.
- Irving R.W. and Leather P. The complexity of counting stable marriages. SIAM J. Comput. 15 (1986) 655–667.
- Irving R.W., Leather P. and Gusfield D. An efficient algorithm for the optimal stable marriage problem // J. ACM 34 (1987) 532–543.
- Picard J. Maximum closure of a graph and applications to combinatorial problems // Manage. Sci. 22 (1976) 1268–1272.
- Faenza Yu. and Zhang X. Affinely representable lattices, stable matchings, and choice functions. ArXiv:2011.06763v2[math.CO], 2021.
- Stanley R.P. Two poset polytopes. Discrete and Computational Geometry 1 (1) (1986) 9–23.
- Danilov V.I. Sequential choice functions and stability problems. ArXiv:2401.00748v2 [math.CO], 2024.
- Alkan A. and Gale D. Stable schedule matching under revealed preference. J. Economic Theory 112 (2003) 289–306.
- Aizerman M. and Malishevski A. General theory of best variants choice: Some aspects // IEEE Transactions on Automatic Control 26 (5) (1981) 1030–1040.
- Cechlarova K. and Fleiner T. On a generalization of a stable roommates problem. EGREST Technical Report No. 2003–03, 2003.
- Mourtos I. and Samaris M. Stable allocations and partially ordered sets // Discrete Optimization 46 (2022) 100731.
- Karzanov A.V. On stable assignments generated by choice functions of mixed type // Discrete Applied Math. 358 (2024) 112–135, https://doi.org/10.1016/j.dam.2024.06.037.
Supplementary files
