A deferred acceptance algorithm with contracts

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

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

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, Argentina

Received February 2015 Revised July 2015 Published November 2015

Abstract
Related Papers

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: optimal, algorithm, Stable allocation, quasi-stable, lattice..

Mathematics Subject Classification: 91B40, 91B6.

Citation: Eliana Pepa Risma. A deferred acceptance algorithm with contracts. Journal of Dynamics and 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-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.

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

[1]	Luis Barreira, Claudia Valls. Stable manifolds with optimal regularity for difference equations. Discrete and Continuous Dynamical Systems, 2012, 32 (5) : 1537-1555. doi: 10.3934/dcds.2012.32.1537
[2]	T. J. Sullivan. Well-posed Bayesian inverse problems and heavy-tailed stable quasi-Banach space priors. Inverse Problems and Imaging, 2017, 11 (5) : 857-874. doi: 10.3934/ipi.2017040
[3]	Qinglan Xia, Shaofeng Xu. On the ramified optimal allocation problem. Networks and Heterogeneous Media, 2013, 8 (2) : 591-624. doi: 10.3934/nhm.2013.8.591
[4]	Tianyu Yang, Yang Yang. A stable non-iterative reconstruction algorithm for the acoustic inverse boundary value problem. Inverse Problems and Imaging, 2022, 16 (1) : 1-18. doi: 10.3934/ipi.2021038
[5]	Rasul Shafikov, Christian Wolf. Stable sets, hyperbolicity and dimension. Discrete and Continuous Dynamical Systems, 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 and Games, 2018, 5 (2) : 165-185. doi: 10.3934/jdg.2018010
[7]	Kenneth R. Meyer, Jesús F. Palacián, Patricia Yanguas. Normally stable hamiltonian systems. Discrete and Continuous Dynamical Systems, 2013, 33 (3) : 1201-1214. doi: 10.3934/dcds.2013.33.1201
[8]	Xiao Wen. Structurally stable homoclinic classes. Discrete and Continuous Dynamical Systems, 2016, 36 (3) : 1693-1707. doi: 10.3934/dcds.2016.36.1693
[9]	Alex Potapov, Ulrike E. Schlägel, Mark A. Lewis. Evolutionarily stable diffusive dispersal. Discrete and Continuous Dynamical Systems - B, 2014, 19 (10) : 3319-3340. doi: 10.3934/dcdsb.2014.19.3319
[10]	Fan Yuan, Dachuan Xu, Donglei Du, Min Li. An exact algorithm for stable instances of the $ k $-means problem with penalties in fixed-dimensional Euclidean space. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021122
[11]	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
[12]	Thorsten Hüls. Computing stable hierarchies of fiber bundles. Discrete and Continuous Dynamical Systems - B, 2017, 22 (9) : 3341-3367. doi: 10.3934/dcdsb.2017140
[13]	Fuhito Kojima. Finding all stable matchings with couples. Journal of Dynamics and Games, 2015, 2 (3&4) : 321-330. doi: 10.3934/jdg.2015008
[14]	Keonhee Lee, Kazumine Moriyasu, Kazuhiro Sakai. $C^1$-stable shadowing diffeomorphisms. Discrete and Continuous Dynamical Systems, 2008, 22 (3) : 683-697. doi: 10.3934/dcds.2008.22.683
[15]	Nate Bottman, Bernard Deconinck. KdV cnoidal waves are spectrally stable. Discrete and Continuous Dynamical Systems, 2009, 25 (4) : 1163-1180. doi: 10.3934/dcds.2009.25.1163
[16]	Sujit Nair, Naomi Ehrich Leonard. Stable synchronization of rigid body networks. Networks and Heterogeneous Media, 2007, 2 (4) : 597-626. doi: 10.3934/nhm.2007.2.597
[17]	M. W. Hirsch, Hal L. Smith. Asymptotically stable equilibria for monotone semiflows. Discrete and Continuous Dynamical Systems, 2006, 14 (3) : 385-398. doi: 10.3934/dcds.2006.14.385
[18]	Gabriel Núñez, Jana Rodriguez Hertz. Minimality and stable Bernoulliness in dimension 3. Discrete and Continuous Dynamical Systems, 2020, 40 (3) : 1879-1887. doi: 10.3934/dcds.2020097
[19]	Juhi Jang, Jinmyoung Seok. Kinetic description of stable white dwarfs. Kinetic and Related Models, 2022, 15 (4) : 605-620. doi: 10.3934/krm.2021033
[20]	Qiying Hu, Wuyi Yue. Optimal control for resource allocation in discrete event systems. Journal of Industrial and Management Optimization, 2006, 2 (1) : 63-80. doi: 10.3934/jimo.2006.2.63

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Eliana Pepa Risma
on Google Scholar
Eliana Pepa Risma

[Back to Top]