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

[2]

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

[3]

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

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

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

[12]

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

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

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

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

[16]

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

[17]

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

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

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

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

[2]

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

[3]

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

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

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

[12]

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

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

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

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

[16]

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

[17]

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

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

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

[1]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[2]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

[3]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020271

[4]

Guido Cavallaro, Roberto Garra, Carlo Marchioro. Long time localization of modified surface quasi-geostrophic equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020336

[5]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044

[6]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

[7]

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

[8]

Wenmeng Geng, Kai Tao. Large deviation theorems for dirichlet determinants of analytic quasi-periodic jacobi operators with Brjuno-Rüssmann frequency. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5305-5335. doi: 10.3934/cpaa.2020240

[9]

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

[10]

Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347

[11]

Bernard Bonnard, Jérémy Rouot. Geometric optimal techniques to control the muscular force response to functional electrical stimulation using a non-isometric force-fatigue model. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020032

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]