Article Contents
Article Contents

# A deferred acceptance algorithm with contracts

• 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.
Mathematics Subject Classification: 91B40, 91B68.

 Citation:

•  [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.