2015, 2(3&4): 257-287. doi: 10.3934/jdg.2015004

Paths to stability in the assignment problem

1. 

Faculty of Business and Economics, University of Lausanne, Internef 538, CH-1015 Lausanne, Switzerland

2. 

Federal Department of Economic A airs, Education and Research, SECO, CH-3003 Bern, Switzerland

Received  February 2015 Revised  May 2015 Published  November 2015

We study a labor market with finitely many heterogeneous workers and firms to illustrate the decentralized (myopic) blocking dynamics in two-sided one-to-one matching markets with continuous side payments (assignment problems, Shapley and Shubik [24]).
   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, one-to-one 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.
Citation: Bettina Klaus, Frédéric Payot. Paths to stability in the assignment problem. Journal of Dynamics & Games, 2015, 2 (3&4) : 257-287. doi: 10.3934/jdg.2015004
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 Graph-Theoretic Concepts in Computer Science (Lecture Notes in Computer Science), 7551 (2012), 69. doi: 10.1007/978-3-642-34611-8_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 flexible-salary 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 two-sided matching markets,, Econometrica, 53 (1985), 873. doi: 10.2307/1912658.

[9]

G. Demange, D. Gale and M. Sotomayor, Multi-item 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/1813-9450-1986.

[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, Two-sided Matching: A Study in Game-Theoretic 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 two-sided 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/S0165-4896(03)00067-2.

[26]

N. Sun and Z. Yang, A double-track 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/s00199-005-0003-4.

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 Graph-Theoretic Concepts in Computer Science (Lecture Notes in Computer Science), 7551 (2012), 69. doi: 10.1007/978-3-642-34611-8_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 flexible-salary 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 two-sided matching markets,, Econometrica, 53 (1985), 873. doi: 10.2307/1912658.

[9]

G. Demange, D. Gale and M. Sotomayor, Multi-item 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/1813-9450-1986.

[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, Two-sided Matching: A Study in Game-Theoretic 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 two-sided 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/S0165-4896(03)00067-2.

[26]

N. Sun and Z. Yang, A double-track 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/s00199-005-0003-4.

[1]

Martin Frank, Armin Fügenschuh, Michael Herty, Lars Schewe. The coolest path problem. Networks & Heterogeneous Media, 2010, 5 (1) : 143-162. 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) : 745-753. 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) : 95-105. 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) : 369-381. doi: 10.3934/dcdsb.2017017

[5]

Patricia Bauman, Daniel Phillips. Analysis and stability of bent-core liquid crystal fibers. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1707-1728. doi: 10.3934/dcdsb.2012.17.1707

[6]

Frederic Laurent-Polz, James Montaldi, Mark Roberts. Point vortices on the sphere: Stability of symmetric relative equilibria. Journal of Geometric Mechanics, 2011, 3 (4) : 439-486. 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) : 101-118. 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) : 1019-1030. doi: 10.3934/jimo.2014.10.1019

[9]

Chia-Chun Hsu, Hsun-Jung Cho, Shu-Cherng Fang. Solving routing and wavelength assignment problem with maximum edge-disjoint paths. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1065-1084. doi: 10.3934/jimo.2016062

[10]

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, 2018, 13 (5) : 1-25. doi: 10.3934/jimo.2018041

[11]

R. N. Gasimov, O. Ustun. Solving the quadratic assignment problem using F-MSG algorithm. Journal of Industrial & Management Optimization, 2007, 3 (2) : 173-191. doi: 10.3934/jimo.2007.3.173

[12]

Yi-Kuei Lin, Cheng-Ta Yeh. Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts. Journal of Industrial & Management Optimization, 2011, 7 (1) : 211-227. doi: 10.3934/jimo.2011.7.211

[13]

Lili Ding, Xinmin Liu, Yinfeng Xu. Competitive risk management for online Bahncard problem. Journal of Industrial & Management Optimization, 2010, 6 (1) : 1-14. 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) : 425-434. 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) : 701-721. doi: 10.3934/dcds.2013.33.701

[16]

Sílvia Cuadrado. Stability of equilibria of a predator-prey model of phenotype evolution. Mathematical Biosciences & Engineering, 2009, 6 (4) : 701-718. doi: 10.3934/mbe.2009.6.701

[17]

Lyudmila Grigoryeva, Juan-Pablo Ortega, Stanislav S. Zub. Stability of Hamiltonian relative equilibria in symmetric magnetically confined rigid bodies. Journal of Geometric Mechanics, 2014, 6 (3) : 373-415. doi: 10.3934/jgm.2014.6.373

[18]

Shangbing Ai. Global stability of equilibria in a tick-borne disease model. Mathematical Biosciences & Engineering, 2007, 4 (4) : 567-572. 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) : 1047-1054. 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) : 485-495. doi: 10.3934/jdg.2014.1.485

 Impact Factor: 

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]