
Previous Article
A survey on assignment markets
 JDG Home
 This Issue

Next Article
A deferred acceptance algorithm with contracts
Paths to stability in the assignment problem
1.  Faculty of Business and Economics, University of Lausanne, Internef 538, CH1015 Lausanne, Switzerland 
2.  Federal Department of Economic Aairs, Education and Research, SECO, CH3003 Bern, Switzerland 
Assuming individual rationality, a labor market is unstable if there is at least one blocking pair, that is, a worker and a firm who would prefer to be matched to each other in order to obtain higher payoffs than the payoffs they obtain by being matched to their current partners. A blocking path is a sequence of outcomes (specifying matchings and payoffs) such that each outcome is obtained from the previous one by satisfying a blocking pair (i.e., by matching the two blocking agents and assigning new payoffs to them that are higher than the ones they received before).
We are interested in the question if starting from any (unstable) individually rational outcome, there always exists a blocking path that will lead to a stable outcome. In contrast to discrete versions of the model (i.e., for marriage markets, onetoone matching, or discretized assignment problems), the existence of blocking paths to stability cannot always be guaranteed. We identify a necessary and sufficient condition for an assignment problem (the existence of a stable outcome such that all matched agents receive positive payoffs) to guarantee the existence of paths to stability and show how to construct such a path whenever this is possible.
References:
[1] 
A. Abdulkadiroǧlu, P. A. Pathak and A. E. Roth, The New York City high school match,, The American Economic Review, 95 (2005), 364. 
[2] 
A. Abdulkadiroǧlu and T. Sönmez, School choice: A mechanism design approach,, The American Economic Review, 93 (2003), 729. 
[3] 
L. M. Ausubel, An efficient dynamic auction for heterogeneous commodities,, The American Economic Review, 96 (2006), 602. doi: 10.1257/aer.96.3.602. 
[4] 
P. Biró, M. Bomhoff, P. A. Golovach, W. Kern and D. Paulusma, Solutions for the stable roommates problem with payments,, in GraphTheoretic Concepts in Computer Science (Lecture Notes in Computer Science), 7551 (2012), 69. doi: 10.1007/9783642346118_10. 
[5] 
B. Chen, S. Fujishige and Z. Yang, Decentralized Market Processes to Stable Job Matchings with Competitive Salaries,, Working paper, (2012). 
[6] 
V. P. Crawford, The flexiblesalary match: A proposal to increase the salary flexibility of the national resident matching program,, Journal of Economic Behavior and Organization, 66 (2008), 149. doi: 10.1016/j.jebo.2006.09.001. 
[7] 
V. P. Crawford and E. M. Knoer, Job matching with heterogeneous firms and workers,, Econometrica, 49 (1981), 437. doi: 10.2307/1913320. 
[8] 
G. Demange and D. Gale, The strategy structure of twosided matching markets,, Econometrica, 53 (1985), 873. doi: 10.2307/1912658. 
[9] 
G. Demange, D. Gale and M. Sotomayor, Multiitem auctions,, The Journal of Political Economy, 94 (1986), 863. doi: 10.1086/261411. 
[10] 
E. Diamantoudi, E. Miyagawa and L. Xue, Random paths to stability in the roommate problem,, Games and Economic Behavior, 48 (2004), 18. doi: 10.1016/j.geb.2003.05.003. 
[11] 
D. Gale and L. S. Shapley, College admissions and the stability of marriage,, The American Mathematical Monthly, 69 (1962), 9. doi: 10.2307/2312726. 
[12] 
F. Gul and E. Stacchetti, The English auction with differentiated commodities,, Journal of Economic Theory, 92 (2000), 66. doi: 10.1006/jeth.1999.2580. 
[13] 
J. W. Hatfield, S. D. Kominers, A. Nichifor, M. Ostrovsky and A. Westkamp, Stability and competitive equilibrium in trading networks,, Journal of Political Economy, 121 (2013), 966. doi: 10.1086/673402. 
[14] 
A. S. Kelso Jr. and V. P. Crawford, Job matching, coalition formation, and gross substitutes,, Econometrica, 50 (1982), 1483. 
[15] 
B. Klaus and F. Klijn, Paths to stability for matching markets with couples,, Games and Economic Behavior, 58 (2007), 154. doi: 10.1016/j.geb.2006.03.002. 
[16] 
D. E. Knuth, Mariages Stables,, Les Presses de l'Université de Montréal, (1976). 
[17] 
P. Milgrom, Putting auction theory to work: The simultaneous ascending auction,, The Journal of Political Economy, 108 (2000), 245. doi: 10.1596/181394501986. 
[18] 
H. H. Nax, B. S. R. Pradelsky and H. P. Young, The Evolution of Core Stability in Decentralized Matching Markets,, Working paper, (2013). doi: 10.2139/ssrn.2274753. 
[19] 
F. Payot, Three Essays in Economics of Innovation and Matching Theory,, Ph.D thesis, (2011). 
[20] 
A. E. Roth, The evolution of the labor market for medical interns and residents: A case study in game theory,, The Journal of Political Economy, 92 (1984), 991. doi: 10.1086/261272. 
[21] 
A. E. Roth and M. O. Sotomayor, Twosided Matching: A Study in GameTheoretic Modeling and Analysis,, Cambridge University Press, (1990). doi: 10.1017/CCOL052139015X. 
[22] 
A. E. Roth and J. H. Vande Vate, Random paths to stability in twosided matching,, Econometrica, 58 (1990), 1475. doi: 10.2307/2938326. 
[23] 
M. Schwarz and B. Yenmez, Median stable matchings for markets with wages,, Journal of Economic Theory, 146 (2011), 619. doi: 10.1016/j.jet.2010.12.004. 
[24] 
L. S. Shapley and M. Shubik, The assignment game I: The core,, International Journal of Game Theory, 1 (1972), 111. 
[25] 
M. O. Sotomayor, Some further remark on the core structure of the assignment game,, Mathematical Social Sciences, 46 (2003), 261. doi: 10.1016/S01654896(03)000672. 
[26] 
N. Sun and Z. Yang, A doubletrack adjustment process for discrete markets with substitutes and complements,, Econometrica, 77 (2009), 933. doi: 10.3982/ECTA6514. 
[27] 
J. Wako, Another proof that assignment games have singleton cores only if multiple optimal matchings exist,, Economic Theory, 29 (2006), 213. doi: 10.1007/s0019900500034. 
show all references
References:
[1] 
A. Abdulkadiroǧlu, P. A. Pathak and A. E. Roth, The New York City high school match,, The American Economic Review, 95 (2005), 364. 
[2] 
A. Abdulkadiroǧlu and T. Sönmez, School choice: A mechanism design approach,, The American Economic Review, 93 (2003), 729. 
[3] 
L. M. Ausubel, An efficient dynamic auction for heterogeneous commodities,, The American Economic Review, 96 (2006), 602. doi: 10.1257/aer.96.3.602. 
[4] 
P. Biró, M. Bomhoff, P. A. Golovach, W. Kern and D. Paulusma, Solutions for the stable roommates problem with payments,, in GraphTheoretic Concepts in Computer Science (Lecture Notes in Computer Science), 7551 (2012), 69. doi: 10.1007/9783642346118_10. 
[5] 
B. Chen, S. Fujishige and Z. Yang, Decentralized Market Processes to Stable Job Matchings with Competitive Salaries,, Working paper, (2012). 
[6] 
V. P. Crawford, The flexiblesalary match: A proposal to increase the salary flexibility of the national resident matching program,, Journal of Economic Behavior and Organization, 66 (2008), 149. doi: 10.1016/j.jebo.2006.09.001. 
[7] 
V. P. Crawford and E. M. Knoer, Job matching with heterogeneous firms and workers,, Econometrica, 49 (1981), 437. doi: 10.2307/1913320. 
[8] 
G. Demange and D. Gale, The strategy structure of twosided matching markets,, Econometrica, 53 (1985), 873. doi: 10.2307/1912658. 
[9] 
G. Demange, D. Gale and M. Sotomayor, Multiitem auctions,, The Journal of Political Economy, 94 (1986), 863. doi: 10.1086/261411. 
[10] 
E. Diamantoudi, E. Miyagawa and L. Xue, Random paths to stability in the roommate problem,, Games and Economic Behavior, 48 (2004), 18. doi: 10.1016/j.geb.2003.05.003. 
[11] 
D. Gale and L. S. Shapley, College admissions and the stability of marriage,, The American Mathematical Monthly, 69 (1962), 9. doi: 10.2307/2312726. 
[12] 
F. Gul and E. Stacchetti, The English auction with differentiated commodities,, Journal of Economic Theory, 92 (2000), 66. doi: 10.1006/jeth.1999.2580. 
[13] 
J. W. Hatfield, S. D. Kominers, A. Nichifor, M. Ostrovsky and A. Westkamp, Stability and competitive equilibrium in trading networks,, Journal of Political Economy, 121 (2013), 966. doi: 10.1086/673402. 
[14] 
A. S. Kelso Jr. and V. P. Crawford, Job matching, coalition formation, and gross substitutes,, Econometrica, 50 (1982), 1483. 
[15] 
B. Klaus and F. Klijn, Paths to stability for matching markets with couples,, Games and Economic Behavior, 58 (2007), 154. doi: 10.1016/j.geb.2006.03.002. 
[16] 
D. E. Knuth, Mariages Stables,, Les Presses de l'Université de Montréal, (1976). 
[17] 
P. Milgrom, Putting auction theory to work: The simultaneous ascending auction,, The Journal of Political Economy, 108 (2000), 245. doi: 10.1596/181394501986. 
[18] 
H. H. Nax, B. S. R. Pradelsky and H. P. Young, The Evolution of Core Stability in Decentralized Matching Markets,, Working paper, (2013). doi: 10.2139/ssrn.2274753. 
[19] 
F. Payot, Three Essays in Economics of Innovation and Matching Theory,, Ph.D thesis, (2011). 
[20] 
A. E. Roth, The evolution of the labor market for medical interns and residents: A case study in game theory,, The Journal of Political Economy, 92 (1984), 991. doi: 10.1086/261272. 
[21] 
A. E. Roth and M. O. Sotomayor, Twosided Matching: A Study in GameTheoretic Modeling and Analysis,, Cambridge University Press, (1990). doi: 10.1017/CCOL052139015X. 
[22] 
A. E. Roth and J. H. Vande Vate, Random paths to stability in twosided matching,, Econometrica, 58 (1990), 1475. doi: 10.2307/2938326. 
[23] 
M. Schwarz and B. Yenmez, Median stable matchings for markets with wages,, Journal of Economic Theory, 146 (2011), 619. doi: 10.1016/j.jet.2010.12.004. 
[24] 
L. S. Shapley and M. Shubik, The assignment game I: The core,, International Journal of Game Theory, 1 (1972), 111. 
[25] 
M. O. Sotomayor, Some further remark on the core structure of the assignment game,, Mathematical Social Sciences, 46 (2003), 261. doi: 10.1016/S01654896(03)000672. 
[26] 
N. Sun and Z. Yang, A doubletrack adjustment process for discrete markets with substitutes and complements,, Econometrica, 77 (2009), 933. doi: 10.3982/ECTA6514. 
[27] 
J. Wako, Another proof that assignment games have singleton cores only if multiple optimal matchings exist,, Economic Theory, 29 (2006), 213. doi: 10.1007/s0019900500034. 
[1] 
Martin Frank, Armin Fügenschuh, Michael Herty, Lars Schewe. The coolest path problem. Networks & Heterogeneous Media, 2010, 5 (1) : 143162. doi: 10.3934/nhm.2010.5.143 
[2] 
Natalia Kudryashova. Strategic games in a competitive market: Feedback from the users' environment. Conference Publications, 2015, 2015 (special) : 745753. doi: 10.3934/proc.2015.0745 
[3] 
Louis Caccetta, Ian Loosen, Volker Rehbock. Computational aspects of the optimal transit path problem. Journal of Industrial & Management Optimization, 2008, 4 (1) : 95105. doi: 10.3934/jimo.2008.4.95 
[4] 
PaweŁ Hitczenko, Georgi S. Medvedev. Stability of equilibria of randomly perturbed maps. Discrete & Continuous Dynamical Systems  B, 2017, 22 (2) : 369381. doi: 10.3934/dcdsb.2017017 
[5] 
Patricia Bauman, Daniel Phillips. Analysis and stability of bentcore liquid crystal fibers. Discrete & Continuous Dynamical Systems  B, 2012, 17 (6) : 17071728. doi: 10.3934/dcdsb.2012.17.1707 
[6] 
Frederic LaurentPolz, James Montaldi, Mark Roberts. Point vortices on the sphere: Stability of symmetric relative equilibria. Journal of Geometric Mechanics, 2011, 3 (4) : 439486. doi: 10.3934/jgm.2011.3.439 
[7] 
Paul Georgescu, Hong Zhang, Daniel Maxin. The global stability of coexisting equilibria for three models of mutualism. Mathematical Biosciences & Engineering, 2016, 13 (1) : 101118. doi: 10.3934/mbe.2016.13.101 
[8] 
Ming Chen, Chongchao Huang. A power penalty method for the general traffic assignment problem with elastic demand. Journal of Industrial & Management Optimization, 2014, 10 (4) : 10191030. doi: 10.3934/jimo.2014.10.1019 
[9] 
ChiaChun Hsu, HsunJung Cho, ShuCherng Fang. Solving routing and wavelength assignment problem with maximum edgedisjoint paths. Journal of Industrial & Management Optimization, 2017, 13 (2) : 10651084. doi: 10.3934/jimo.2016062 
[10] 
R. N. Gasimov, O. Ustun. Solving the quadratic assignment problem using FMSG algorithm. Journal of Industrial & Management Optimization, 2007, 3 (2) : 173191. doi: 10.3934/jimo.2007.3.173 
[11] 
YiKuei Lin, ChengTa Yeh. Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts. Journal of Industrial & Management Optimization, 2011, 7 (1) : 211227. doi: 10.3934/jimo.2011.7.211 
[12] 
Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2019, 15 (1) : 235259. doi: 10.3934/jimo.2018041 
[13] 
Lili Ding, Xinmin Liu, Yinfeng Xu. Competitive risk management for online Bahncard problem. Journal of Industrial & Management Optimization, 2010, 6 (1) : 114. doi: 10.3934/jimo.2010.6.1 
[14] 
Jia Shu, Zhengyi Li, Weijun Zhong. A market selection and inventory ordering problem under demand uncertainty. Journal of Industrial & Management Optimization, 2011, 7 (2) : 425434. doi: 10.3934/jimo.2011.7.425 
[15] 
Xiangnan He, Wenlian Lu, Tianping Chen. On transverse stability of random dynamical system. Discrete & Continuous Dynamical Systems  A, 2013, 33 (2) : 701721. doi: 10.3934/dcds.2013.33.701 
[16] 
Sílvia Cuadrado. Stability of equilibria of a predatorprey model of phenotype evolution. Mathematical Biosciences & Engineering, 2009, 6 (4) : 701718. doi: 10.3934/mbe.2009.6.701 
[17] 
Lyudmila Grigoryeva, JuanPablo Ortega, Stanislav S. Zub. Stability of Hamiltonian relative equilibria in symmetric magnetically confined rigid bodies. Journal of Geometric Mechanics, 2014, 6 (3) : 373415. doi: 10.3934/jgm.2014.6.373 
[18] 
Shangbing Ai. Global stability of equilibria in a tickborne disease model. Mathematical Biosciences & Engineering, 2007, 4 (4) : 567572. doi: 10.3934/mbe.2007.4.567 
[19] 
Elbaz I. Abouelmagd, Juan L. G. Guirao, Aatef Hobiny, Faris Alzahrani. Stability of equilibria points for a dumbbell satellite when the central body is oblate spheroid. Discrete & Continuous Dynamical Systems  S, 2015, 8 (6) : 10471054. doi: 10.3934/dcdss.2015.8.1047 
[20] 
William H. Sandholm. Local stability of strict equilibria under evolutionary game dynamics. Journal of Dynamics & Games, 2014, 1 (3) : 485495. doi: 10.3934/jdg.2014.1.485 
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]