×

On stable assignments generated by choice functions of mixed type. (English) Zbl 07919057

Summary: We consider one variant of stable assignment problems in a bipartite graph endowed with nonnegative capacities on the edges and quotas on the vertices. It can be viewed as a generalization of the stable allocation problem introduced by Baïou and Balinsky, which arises when strong linear orders of preferences on the vertices in the latter are replaced by weak ones. At the same time, our stability problem can be stated in the framework of a theory by Alkan and Gale on stable schedule matchings generated by choice functions of a wide scope. In our case, the choice functions are of a special, so-called mixed, type. The main content of this paper is devoted to a study of rotations in our mixed model, functions on the edges determining “elementary” transformations between close stable assignments. These look more sophisticated compared with rotations in the stable allocation problem (which are generated by simple cycles). We efficiently construct a poset of rotations and show that the stable assignments are in bijection with the so-called closed functions for this poset; this gives rise to a “compact” affine representation for the lattice of stable assignments and leads to an efficient method to find a stable assignment of minimum cost.

MSC:

90Cxx Mathematical programming
91Bxx Mathematical economics
05Axx Enumerative combinatorics

References:

[1] Alkan, A.; Gale, D., Stable schedule matching under revealed preference, J. Econom. Theory, 112, 289-306, 2003 · Zbl 1068.91059
[2] Baïou, M.; Balinski, M., Erratum: the stable allocation (or ordinal transportation) problem, Math. Oper. Res., 27, 4, 662-680, 2002 · Zbl 1083.90501
[3] Bansal, V.; Agrawal, A.; Malhotra, V. S., Polynomial time algorithm for an optimal stable assignment with multiple partners, Theoret. Comput. Sci., 379, 3, 317-328, 2007 · Zbl 1149.90087
[4] Birkhoff, G., Rings of sets, Duke Math. J., 3, 3, 443-454, 1937 · Zbl 0017.19403
[5] Blair, C., The lattice structure of the set of stable matchings with multiple partners, Math. Oper. Res., 13, 619-628, 1988 · Zbl 0664.90075
[6] Dean, B. C.; Munshi, S., Faster algorithms for stable allocation problems, Algorithmica, 58, 1, 59-81, 2010 · Zbl 1209.68361
[7] Faenza, Yu.; Zhang, X., Affinely representable lattices, stable matchings, and choice functions, 2021, arXiv:2011.06763v2 [math.CO] · Zbl 1482.90181
[8] Fleiner, T., A fixed-point approach to stable matchings and some applications, Math. Oper. Res., 28, 1, 103-126, 2003 · Zbl 1082.90096
[9] Gale, D.; Shapley, L. S., College admissions and the stability of marriage, Amer. Math. Monthly, 69, 1, 9-15, 1962 · Zbl 0109.24403
[10] Groetsel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization, 1988, Springer: Springer Berlin · Zbl 0634.05001
[11] Irving, R. W., An efficient algorithm for the “stable roommates” problem, J. Algorithms, 6, 577-595, 1985 · Zbl 0581.05001
[12] Irving, R. W.; Leather, P., The complexity of counting stable marriages, SIAM J. Comput., 15, 655-667, 1986 · Zbl 0611.68015
[13] Irving, R. W.; Leather, P.; Gusfield, D., An efficient algorithm for the optimal stable marriage problem, J. ACM, 34, 532-543, 1987
[14] Karzanov, A. V., Èkonomnyĭ algoritm nakhozhdeniya bikomponent grafa [Russian; an efficient algorithm for finding the bicomponents of a graph], (Trudy Tret’eĭ Zimneĭ Shkoly po Matematicheskomu Programmirovaniyu i Smezhnym Voprosam [Proc. of 3rd Winter School on Math. Programming and Related Topics], issue 2, 1970, Moscow Engineering and Construction Inst. Press: Moscow Engineering and Construction Inst. Press Moscow), 343-347
[15] Karzanov, A. V., On diversifying stable assignments, 2023, arXiv:2308.09797 [math.CO]
[16] Kelso, A. S.; Crawford, V. P., Job matching, coalition formation and gross substitutes, Econometrica, 50, 1483-1504, 1982 · Zbl 0503.90019
[17] Korte, D.; Vygen, J., Combinatorial Optimization. Theory and Algorithms, 2012, Springer · Zbl 1237.90001
[18] Mourtos, I.; Samaris, M., Stable allocations and partially ordered sets, Discrete Optim., 46, Article 100731 pp., 2022 · Zbl 1512.90199
[19] Picard, J., Maximum closure of a graph and applications to combinatorial problems, Manage. Sci., 22, 1268-1272, 1976 · Zbl 0341.05112
[20] Roth, A. E., Stability and polarization of interests in job matching, Econometrica, 52, 47-57, 1984 · Zbl 0526.90012
[21] Schrijver, A., Theory of Linear and Integer Programming, 1986, John Wiley & Sons · Zbl 0665.90063
[22] Stanley, Richard P., Two poset polytopes, Discrete Comput. Geom., 1, 1, 9-23, 1986 · Zbl 0595.52008
[23] Vande Vate, J. H., Linear programming brings marital bliss, Oper. Res. Lett., 8, 147-153, 1989 · Zbl 0675.90058
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.