2015, 2(3&4): 289-302. doi: 10.3934/jdg.2015005

A deferred acceptance algorithm with contracts

1. 

Instituto de Matemtica Aplicada San Luis, IMASL, Universidad Nacional de San Luis and CONICET, Ejercito de los Andes 950. D5700HHW San Luis, Argentina

Received  February 2015 Revised  July 2015 Published  November 2015

For a model of many-to-many matching with contracts, we develop an algorithmto obtain stable allocations from sets of contracts satisfying asignificantly less restrictive condition. Then, we build the optimal stableallocations through a simple process, which is very similar to thepioneering Gale and Shapley's one. Also, we prove that the set of stable allocations has latticestructure with respect to Blair's partial orderings.
Citation: Eliana Pepa Risma. A deferred acceptance algorithm with contracts. Journal of Dynamics & Games, 2015, 2 (3&4) : 289-302. doi: 10.3934/jdg.2015005
References:
[1]

C. Blair, The lattice structure of the set of stable matchings with Multiple Partners,, Mathematics of Operations Research, 13 (1988), 619. doi: 10.1287/moor.13.4.619.

[2]

D. Cantala, Restabilizing matching markets at senior level,, Games and Economic Behavior, 48 (2004), 1. doi: 10.1016/j.geb.2003.07.005.

[3]

C. Chambers and M. B. Yenmez, Choice and matching,, working paper, (2014).

[4]

F. Echenique and J. Oviedo, A theory of stability in many-to-many matching markets,, Theoretical Economics, 1 (2006), 233. doi: 10.2139/ssrn.691443.

[5]

D. Gale and L. Shapley, College admissions and the stability of marriage,, American Math Monthly, 69 (1962), 9. doi: 10.2307/2312726.

[6]

D. Gusfield and R. Irving, The Stable Marriage Problem: Structure and Algorithms,, Cambridge: MIT press, (1989).

[7]

J. Hatfield and P. Milgrom, Matching with contracts,, The American Economic Review, 95 (2005), 913. doi: 10.1257/0002828054825466.

[8]

J. Hatfield and S. Kominers, Contract design and stability in many to many matching,, working paper, (2012).

[9]

R. Irving and P. Leather, The complexity of counting stable marriages,, SIAM Journal of Computing, 15 (1986), 655. doi: 10.1137/0215048.

[10]

A. Kelso and V. Crawford, Coalition formation and and gross substitutes,, Econometrica, 50 (1982), 1483.

[11]

B. Klaus and M. Walzl, Stable many-to-many matching with contracts,, Journal of Mathematical Economics, 45 (2009), 422. doi: 10.1016/j.jmateco.2009.03.007.

[12]

D. Knuth, Marriages Stables,, Les Presses de l'Universite de Montr éal, (1976).

[13]

H. Konishi and M. U. Ünver, Credible group stability in many-to-many matching problems,, Journal of Economic Theory, 129 (2006), 57. doi: 10.1016/j.jet.2005.02.001.

[14]

R. Martinez, J. Massó, A. Neme and J. Oviedo, On the lattice structure of the set of stable matchings for a many-to-one model,, Optimization, 50 (2001), 439. doi: 10.1080/02331930108844574.

[15]

E. Pepa Risma, Binary operations and lattice structure for a model of matching with contracts,, Mathematical Social Sciences, 73 (2015), 6. doi: 10.1016/j.mathsocsci.2014.11.001.

[16]

A. Roth, Stability and polarization of interests in job matching,, Econometrica, 52 (1984), 47. doi: 10.2307/1911460.

[17]

A. Roth, Conflict and coincidence of interests in job matching,, Operational Research, 10 (1985), 379. doi: 10.1287/moor.10.3.379.

[18]

M. Sotomayor, A Non-constructive elementary proof of the existence of stable marriages,, Games and Economic Behavior, 3 (1996), 135. doi: 10.1006/game.1996.0029.

[19]

M. Sotomayor, Three remarks on the many-to-many stable matching problem,, Mathematical Social Sciences, 38 (1999), 55. doi: 10.1016/S0165-4896(98)00048-1.

show all references

References:
[1]

C. Blair, The lattice structure of the set of stable matchings with Multiple Partners,, Mathematics of Operations Research, 13 (1988), 619. doi: 10.1287/moor.13.4.619.

[2]

D. Cantala, Restabilizing matching markets at senior level,, Games and Economic Behavior, 48 (2004), 1. doi: 10.1016/j.geb.2003.07.005.

[3]

C. Chambers and M. B. Yenmez, Choice and matching,, working paper, (2014).

[4]

F. Echenique and J. Oviedo, A theory of stability in many-to-many matching markets,, Theoretical Economics, 1 (2006), 233. doi: 10.2139/ssrn.691443.

[5]

D. Gale and L. Shapley, College admissions and the stability of marriage,, American Math Monthly, 69 (1962), 9. doi: 10.2307/2312726.

[6]

D. Gusfield and R. Irving, The Stable Marriage Problem: Structure and Algorithms,, Cambridge: MIT press, (1989).

[7]

J. Hatfield and P. Milgrom, Matching with contracts,, The American Economic Review, 95 (2005), 913. doi: 10.1257/0002828054825466.

[8]

J. Hatfield and S. Kominers, Contract design and stability in many to many matching,, working paper, (2012).

[9]

R. Irving and P. Leather, The complexity of counting stable marriages,, SIAM Journal of Computing, 15 (1986), 655. doi: 10.1137/0215048.

[10]

A. Kelso and V. Crawford, Coalition formation and and gross substitutes,, Econometrica, 50 (1982), 1483.

[11]

B. Klaus and M. Walzl, Stable many-to-many matching with contracts,, Journal of Mathematical Economics, 45 (2009), 422. doi: 10.1016/j.jmateco.2009.03.007.

[12]

D. Knuth, Marriages Stables,, Les Presses de l'Universite de Montr éal, (1976).

[13]

H. Konishi and M. U. Ünver, Credible group stability in many-to-many matching problems,, Journal of Economic Theory, 129 (2006), 57. doi: 10.1016/j.jet.2005.02.001.

[14]

R. Martinez, J. Massó, A. Neme and J. Oviedo, On the lattice structure of the set of stable matchings for a many-to-one model,, Optimization, 50 (2001), 439. doi: 10.1080/02331930108844574.

[15]

E. Pepa Risma, Binary operations and lattice structure for a model of matching with contracts,, Mathematical Social Sciences, 73 (2015), 6. doi: 10.1016/j.mathsocsci.2014.11.001.

[16]

A. Roth, Stability and polarization of interests in job matching,, Econometrica, 52 (1984), 47. doi: 10.2307/1911460.

[17]

A. Roth, Conflict and coincidence of interests in job matching,, Operational Research, 10 (1985), 379. doi: 10.1287/moor.10.3.379.

[18]

M. Sotomayor, A Non-constructive elementary proof of the existence of stable marriages,, Games and Economic Behavior, 3 (1996), 135. doi: 10.1006/game.1996.0029.

[19]

M. Sotomayor, Three remarks on the many-to-many stable matching problem,, Mathematical Social Sciences, 38 (1999), 55. doi: 10.1016/S0165-4896(98)00048-1.

[1]

Luis Barreira, Claudia Valls. Stable manifolds with optimal regularity for difference equations. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1537-1555. doi: 10.3934/dcds.2012.32.1537

[2]

Qinglan Xia, Shaofeng Xu. On the ramified optimal allocation problem. Networks & Heterogeneous Media, 2013, 8 (2) : 591-624. doi: 10.3934/nhm.2013.8.591

[3]

T. J. Sullivan. Well-posed Bayesian inverse problems and heavy-tailed stable quasi-Banach space priors. Inverse Problems & Imaging, 2017, 11 (5) : 857-874. doi: 10.3934/ipi.2017040

[4]

Kenneth R. Meyer, Jesús F. Palacián, Patricia Yanguas. Normally stable hamiltonian systems. Discrete & Continuous Dynamical Systems - A, 2013, 33 (3) : 1201-1214. doi: 10.3934/dcds.2013.33.1201

[5]

Rasul Shafikov, Christian Wolf. Stable sets, hyperbolicity and dimension. Discrete & Continuous Dynamical Systems - A, 2005, 12 (3) : 403-412. doi: 10.3934/dcds.2005.12.403

[6]

E. Camouzis, H. Kollias, I. Leventides. Stable manifold market sequences. Journal of Dynamics & Games, 2018, 5 (2) : 165-185. doi: 10.3934/jdg.2018010

[7]

Xiao Wen. Structurally stable homoclinic classes. Discrete & Continuous Dynamical Systems - A, 2016, 36 (3) : 1693-1707. doi: 10.3934/dcds.2016.36.1693

[8]

Alex Potapov, Ulrike E. Schlägel, Mark A. Lewis. Evolutionarily stable diffusive dispersal. Discrete & Continuous Dynamical Systems - B, 2014, 19 (10) : 3319-3340. doi: 10.3934/dcdsb.2014.19.3319

[9]

Meng Fan, Bingbing Zhang, Michael Yi Li. Mechanisms for stable coexistence in an insect community. Mathematical Biosciences & Engineering, 2010, 7 (3) : 603-622. doi: 10.3934/mbe.2010.7.603

[10]

Fuhito Kojima. Finding all stable matchings with couples. Journal of Dynamics & Games, 2015, 2 (3&4) : 321-330. doi: 10.3934/jdg.2015008

[11]

Thorsten Hüls. Computing stable hierarchies of fiber bundles. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3341-3367. doi: 10.3934/dcdsb.2017140

[12]

Keonhee Lee, Kazumine Moriyasu, Kazuhiro Sakai. $C^1$-stable shadowing diffeomorphisms. Discrete & Continuous Dynamical Systems - A, 2008, 22 (3) : 683-697. doi: 10.3934/dcds.2008.22.683

[13]

Nate Bottman, Bernard Deconinck. KdV cnoidal waves are spectrally stable. Discrete & Continuous Dynamical Systems - A, 2009, 25 (4) : 1163-1180. doi: 10.3934/dcds.2009.25.1163

[14]

Sujit Nair, Naomi Ehrich Leonard. Stable synchronization of rigid body networks. Networks & Heterogeneous Media, 2007, 2 (4) : 597-626. doi: 10.3934/nhm.2007.2.597

[15]

M. W. Hirsch, Hal L. Smith. Asymptotically stable equilibria for monotone semiflows. Discrete & Continuous Dynamical Systems - A, 2006, 14 (3) : 385-398. doi: 10.3934/dcds.2006.14.385

[16]

Qiying Hu, Wuyi Yue. Optimal control for resource allocation in discrete event systems. Journal of Industrial & Management Optimization, 2006, 2 (1) : 63-80. doi: 10.3934/jimo.2006.2.63

[17]

Bong Joo Kim, Gang Uk Hwang, Yeon Hwa Chung. Traffic modelling and bandwidth allocation algorithm for video telephony service traffic. Journal of Industrial & Management Optimization, 2009, 5 (3) : 541-552. doi: 10.3934/jimo.2009.5.541

[18]

Jean Bourgain. On quasi-periodic lattice Schrödinger operators. Discrete & Continuous Dynamical Systems - A, 2004, 10 (1&2) : 75-88. doi: 10.3934/dcds.2004.10.75

[19]

Carlos Arnoldo Morales. Strong stable manifolds for sectional-hyperbolic sets. Discrete & Continuous Dynamical Systems - A, 2007, 17 (3) : 553-560. doi: 10.3934/dcds.2007.17.553

[20]

Gang Li, Lipu Zhang, Zhe Liu. The stable duality of DC programs for composite convex functions. Journal of Industrial & Management Optimization, 2017, 13 (1) : 63-79. doi: 10.3934/jimo.2016004

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]