A deferred acceptance algorithm withcontracts

Eliana Pepa  Risma

doi:10.3934/jdg.2015005

Article Contents

2015, Volume 2, Issue 3&4: 289-302. Doi: 10.3934/jdg.2015005

This issue Previous Article Paths to stability in the assignment problem Next Article Externality effects in the formation of societies

A deferred acceptance algorithm with contracts

Eliana Pepa Risma^1,

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

Received: January 31, 2015

Revised: June 30, 2015

Published: June 2015

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 91B40, 91B68.

Citation:

Related Papers

Cited by

References

[1]	C. Blair, The lattice structure of the set of stable matchings with Multiple Partners, Mathematics of Operations Research, 13 (1988), 619-628.doi: 10.1287/moor.13.4.619.
[2]	D. Cantala, Restabilizing matching markets at senior level, Games and Economic Behavior, 48 (2004), 1-17.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-273.doi: 10.2139/ssrn.691443.
[5]	D. Gale and L. Shapley, College admissions and the stability of marriage, American Math Monthly, 69 (1962), 9-15.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-935.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-667.doi: 10.1137/0215048.
[10]	A. Kelso and V. Crawford, Coalition formation and and gross substitutes, Econometrica, 50 (1982), 1483-1504.
[11]	B. Klaus and M. Walzl, Stable many-to-many matching with contracts, Journal of Mathematical Economics, 45 (2009), 422-434.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-80.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-457.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-12.doi: 10.1016/j.mathsocsci.2014.11.001.
[16]	A. Roth, Stability and polarization of interests in job matching, Econometrica, 52 (1984), 47-58.doi: 10.2307/1911460.
[17]	A. Roth, Conflict and coincidence of interests in job matching, Operational Research, 10 (1985), 379-389.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-137.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-70.doi: 10.1016/S0165-4896(98)00048-1.