We study stable and strongly stable matchings in the marriage market with indifference in their preferences. We characterize the stable matchings as integer extreme points of a convex polytope. We give an alternative proof for the integrity of the strongly stable matching polytope. Also, we compute men-optimal (women-optimal) stable and strongly stable matchings using linear programming. When preferences are strict, we find the men-optimal (women-optimal) stable matching.
Noelia Juarez, Pablo A. Neme, Jorge Oviedo
. Marriage Market with Indifferences: A Linear Programming Approach[J]. Journal of the Operations Research Society of China, 2023
, 11(1)
: 219
-242
.
DOI: 10.1007/s40305-021-00360-x
[1] Roth, A.E., Sotomayor, M.A.O.:Two-Sided Matching:A Study in Game-Theoretic Modeling and Analysis.Cambidge University Press, Cambridge (1990)
[2] Irving, R.W.:Stable marriage and indifference.Discrete Appl.Math.48(3), 261-272(1994)
[3] Gale, D., Shapley, L.:College admissions and the stability of marriage.Am.Math.Mon.69(1), 9-15(1962)
[4] Erdil, A., Ergin, H.:Two-Sided Matching with Indifferences.J.Econ.Theory 171(C), 268-292(2017)
[5] Abdulkadiroǧlu, A., Pathak, P., Roth, A.:Strategy-proofness versus efficiency in matching with indifferences:Redesigning the NYC high school match.Am.Econ.Rev.99(5), 1954-1978(2009)
[6] Manlove, D., Irving, R., Iwama, K., Miyazaki, S., Morita, Y.:Hard variants of stable marriage.Theoret.Comput.Sci.276(1-2), 261-279(2002)
[7] Ghosal, P., Kunysz, A., Paluch, K.:Characterisation of strongly stable matchings.In:Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp.107-119.SIAM (2016)
[8] Rothblum, U.:Characterization of stable matchings as extreme points of a polytope.Math.Program.54(1-3), 57-67(1992)
[9] Vande Vate, J.:Linear programming brings marital bliss.Oper.Res.Lett.8(3), 147-153(1989)
[10] Roth, A., Rothblum, U., Vande Vate, J.:Stable matchings, optimal assignments, and linear programming.Math.Oper.Res.18(4), 803-828(1993)
[11] Kwanashie, A., Manlove, D.F.:An integer programming approach to the hospitals/residents problem with ties.In:Operations Research Proceedings 2013, pp.263-269.Springer (2014)
[12] Kunysz, A.:An algorithm for the maximum weight strongly stable matching problem.In:29th International Symposium on Algorithms and Computation (ISAAC 2018), pp.1-42.Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
[13] Spieker, B.:The set of super-stable marriages forms a distributive lattice.Discrete Appl.Math.58(1), 79-84(1995)
[14] Erdil, A., Ergin, H.:What's the matter with tie-breaking? Improving efficiency in school choice.Am.Econ.Rev.98(3), 669-689(2008)
[15] Baïou, M., Balinski, M.:The stable admissions polytope.Math.Program.87(3), 427-439(2000)
[16] Király, T., Pap, J.:Total dual integrality of Rothblum's description of the stable-marriage polyhedron.Math.Oper.Res.33(2), 283-290(2008)
[17] 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)
[18] Biró, P., McBride, I.:Integer programming methods for special college admissions problems.In:International Conference on Combinatorial Optimization and Applications, pp.429-443.Springer (2014)
[19] Birkhoff, G.:Tres observaciones sobre el algebra lineal.Univ.Nac.Tucumán Rev.Ser.5(A), 147-151(1946)
[20] McVitie, D., Wilson, L.:Stable marriage assignment for unequal sets.BIT Numer.Math.10(3), 295-309(1970)
[21] Knuth, D.:Stable Marriage and its Relation to Other Combinatorial Problems:An Introduction to the Mathematical Analysis of Algorithms, vol.10.American Mathematical Soc.(1997)
