March & April  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.   Google Scholar

[2]

A. Abdulkadiroǧlu and T. Sönmez, School choice: A mechanism design approach,, The American Economic Review, 93 (2003), 729.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

B. Chen, S. Fujishige and Z. Yang, Decentralized Market Processes to Stable Job Matchings with Competitive Salaries,, Working paper, (2012).   Google Scholar

[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.  Google Scholar

[7]

V. P. Crawford and E. M. Knoer, Job matching with heterogeneous firms and workers,, Econometrica, 49 (1981), 437.  doi: 10.2307/1913320.  Google Scholar

[8]

G. Demange and D. Gale, The strategy structure of two-sided matching markets,, Econometrica, 53 (1985), 873.  doi: 10.2307/1912658.  Google Scholar

[9]

G. Demange, D. Gale and M. Sotomayor, Multi-item auctions,, The Journal of Political Economy, 94 (1986), 863.  doi: 10.1086/261411.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

A. S. Kelso Jr. and V. P. Crawford, Job matching, coalition formation, and gross substitutes,, Econometrica, 50 (1982), 1483.   Google Scholar

[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.  Google Scholar

[16]

D. E. Knuth, Mariages Stables,, Les Presses de l'Université de Montréal, (1976).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

F. Payot, Three Essays in Economics of Innovation and Matching Theory,, Ph.D thesis, (2011).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[24]

L. S. Shapley and M. Shubik, The assignment game I: The core,, International Journal of Game Theory, 1 (1972), 111.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.   Google Scholar

[2]

A. Abdulkadiroǧlu and T. Sönmez, School choice: A mechanism design approach,, The American Economic Review, 93 (2003), 729.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

B. Chen, S. Fujishige and Z. Yang, Decentralized Market Processes to Stable Job Matchings with Competitive Salaries,, Working paper, (2012).   Google Scholar

[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.  Google Scholar

[7]

V. P. Crawford and E. M. Knoer, Job matching with heterogeneous firms and workers,, Econometrica, 49 (1981), 437.  doi: 10.2307/1913320.  Google Scholar

[8]

G. Demange and D. Gale, The strategy structure of two-sided matching markets,, Econometrica, 53 (1985), 873.  doi: 10.2307/1912658.  Google Scholar

[9]

G. Demange, D. Gale and M. Sotomayor, Multi-item auctions,, The Journal of Political Economy, 94 (1986), 863.  doi: 10.1086/261411.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

A. S. Kelso Jr. and V. P. Crawford, Job matching, coalition formation, and gross substitutes,, Econometrica, 50 (1982), 1483.   Google Scholar

[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.  Google Scholar

[16]

D. E. Knuth, Mariages Stables,, Les Presses de l'Université de Montréal, (1976).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

F. Payot, Three Essays in Economics of Innovation and Matching Theory,, Ph.D thesis, (2011).   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[24]

L. S. Shapley and M. Shubik, The assignment game I: The core,, International Journal of Game Theory, 1 (1972), 111.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

Shiqi Ma. On recent progress of single-realization recoveries of random schrödinger systems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020121

[2]

Scipio Cuccagna, Masaya Maeda. A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020450

[3]

Reza Chaharpashlou, Abdon Atangana, Reza Saadati. On the fuzzy stability results for fractional stochastic Volterra integral equation. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020432

[4]

Yangrong Li, Shuang Yang, Qiangheng Zhang. Odd random attractors for stochastic non-autonomous Kuramoto-Sivashinsky equations without dissipation. Electronic Research Archive, 2020, 28 (4) : 1529-1544. doi: 10.3934/era.2020080

[5]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[6]

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[7]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253

[8]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384

[9]

Xin-Guang Yang, Lu Li, Xingjie Yan, Ling Ding. The structure and stability of pullback attractors for 3D Brinkman-Forchheimer equation with delay. Electronic Research Archive, 2020, 28 (4) : 1395-1418. doi: 10.3934/era.2020074

[10]

Chao Xing, Jiaojiao Pan, Hong Luo. Stability and dynamic transition of a toxin-producing phytoplankton-zooplankton model with additional food. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020275

[11]

A. M. Elaiw, N. H. AlShamrani, A. Abdel-Aty, H. Dutta. Stability analysis of a general HIV dynamics model with multi-stages of infected cells and two routes of infection. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020441

[12]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453

[13]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[14]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

[15]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[16]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[17]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[18]

Zhilei Liang, Jiangyu Shuai. Existence of strong solution for the Cauchy problem of fully compressible Navier-Stokes equations in two dimensions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020348

[19]

Mehdi Badsi. Collisional sheath solutions of a bi-species Vlasov-Poisson-Boltzmann boundary value problem. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020052

[20]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

 Impact Factor: 

Metrics

  • PDF downloads (59)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]