×

zbMATH — the first resource for mathematics

Matching with preferences over colleagues solves classical matching. (English) Zbl 1201.91144
The relatively brief note is devoted to the matching market models. Its main contribution consists in the suggestion of the first algorithm for finding of the complete set of stable matchings in any many-to-one matching. It follows from a reduction of the known matching problem to its modification with “preferences over colleagues”. The main results regard the inspirational relation between the complexities of the matching problems with and without preferences over colleagues.

MSC:
91B68 Matching models
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdulkadi‘roǧlu, A., Pathak, P., Roth, A., forthcoming. Strategyproofness versus efficiency in matching with indifferences: Redesigning the NYC high school match. Amer. Econ. Rev
[2] Adachi, H., On a characterization of stable matchings, Econ. letters, 68, 43-49, (2000) · Zbl 0953.91048
[3] Clark, S., The uniqueness of stable matchings, Contrib. theor. econ., 6, (2006), Article 8
[4] Dimitrov, D., Lazarova, E., 2008. Coalitional matchings. Fondazione Eni Enrico Mattei. Working Paper 45.2008
[5] Dutta, B.; Massó, J., Stability of matchings when individuals have preferences over colleagues, J. econ. theory, 75, 464-475, (1997) · Zbl 0892.90049
[6] Echenique, F.; Yenmez, M.B., A solution to matching with preferences over colleagues, Games econ. behav., 59, 46-71, (2007) · Zbl 1271.91084
[7] Eeckhout, J., On the uniqueness of stable marriage matchings, Econ. letters, 69, 1-8, (2000) · Zbl 0960.91052
[8] Fleiner, T., A fixed point approach to stable matchings and some applications, Math. oper. res., 28, 103-126, (2003) · Zbl 1082.90096
[9] Gale, D.; Shapley, L.S., College admissions and the stability of marriage, Amer. math. monthly, 69, 9-15, (1962) · Zbl 0109.24403
[10] Hatfield, J., Kojima, F., 2007. Substitutes and stability for matching with contracts. Mimeo. Cowles Foundation
[11] Hatfield, J.; Milgrom, P., Matching with contracts, Amer. econ. rev., 95, 913-935, (2005)
[12] Irving, R.; Leather, P., The complexity of counting stable marriages, SIAM J. comput., 15, 655-667, (1986) · Zbl 0611.68015
[13] Kelso, A.S.; Crawford, V.P., Job matching, coalition formation, and Gross substitutes, Econometrica, 50, 1483-1504, (1982) · Zbl 0503.90019
[14] Klaus, B.; Klijn, F., Median stable matching for college admissions, Int. J. game theory, 34, 1-11, (2006) · Zbl 1092.91063
[15] Kojima, F., 2007. Finding all stable matchings with couples. Mimeo. Cowles Foundation
[16] Kuo, R.T.; Tseng, S.S., On the invariance of male optimal stable matching, BIT numer. math., 40, 592-598, (2005) · Zbl 0711.68049
[17] Martínez, R.; Massó, J.; Neme, A.; Oviedo, J., An algorithm to compute the full set of many-to-many stable matchings, Math. soc. sci., 47, 187-210, (2004) · Zbl 1107.91074
[18] McVitie, D.G.; Wilson, L.B., The stable marriage problem, Comm. ACM, 14, 486-490, (1971)
[19] Pycia, M., 2007. Many-to-one matching with complementarities and peer effects. Mimeo. Pennsylvania State University
[20] Revilla, P., 2007. Many-to-one matching when colleagues matter. Fondazione Eni Enrico Mattei. Working Paper 87.2007
[21] Roth, A.E., The college admissions problem is not equivalent to the marriage problem, J. econ. theory, 36, 277-288, (1985) · Zbl 0594.90002
[22] Roth, A.E., Deferred acceptance algorithms: history, theory, practice, and open questions, Int. J. game theory, 36, 537-569, (2008) · Zbl 1142.91049
[23] Roth, A.E.; Sotomayor, M.A.O., Two-sided matching: A study in game-theoretic modeling and analysis, Econometric society monographs, (1990), Cambridge University Press Cambridge · Zbl 0726.90003
[24] Schwarz, M., Yenmez, M.B., 2008. Median stable matching. Mimeo. Stanford University
[25] Sethuraman, J.; Teo, C.; Qian, L., Many-to-one matching: geometry and fairness, Math. oper. res., 31, 581-596, (2006) · Zbl 1278.91107
[26] Teo, C.; Sethuraman, J., The geometry of fractional stable matchings and its applications, Math. oper. res., 23, 874-891, (1998) · Zbl 0977.90046
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.