A note on the lattice structure for matching markets via linear programming

Previous Article
A dynamic for production economies with multiple equilibria
JDG Home
This Issue
Next Article
A Mean Field Games model for finite mixtures of Bernoulli and categorical distributions

January 2021, 8(1): 61-67. doi: 10.3934/jdg.2021001

A note on the lattice structure for matching markets via linear programming

Pablo Neme and Jorge Oviedo

Av. Italia 1556, San Luis, Argentina

Received June 2020 Revised November 2020 Published January 2021 Early access December 2020

Fund Project: ^*Instituto de Matemática Aplicada San Luis, Universidad Nacional de San Luis and CONICET, San Luis, Argentina. RedNIE. We are grateful to the anonymous referees for their valuable comments. We acknowledge financial support from the UNSL through grant 032016, and from the Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET) through grant PIP 112-200801-00655, from Agencia Nacional de Promoción Científica y Tecnológica through grant PICT 2017-2355

Given two stable matchings in a many-to-one matching market with $ q $-responsive preferences, by manipulating the objective function of the linear program that characterizes the stable matching set, we compute the least upper bound and greatest lower bound between them.

Keywords: Matching markets, stable matchings, many-to-one matchings, linear programming, lattice structure.

Mathematics Subject Classification: 90C05, 91B68.

Citation: Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics and Games, 2021, 8 (1) : 61-67. doi: 10.3934/jdg.2021001

References:

[1]	M. Baïou and M. Balinski, The stable admissions polytope, Math. Program., 87 (2000), 427-439. doi: 10.1007/s101070050004.
[2]	D. Gale and L. S. Shapley, College admissions and the stability of marriage, Amer. Math. Monthly, 69 (1962), 9-15. doi: 10.1080/00029890.1962.11989827.
[3]	A. E. Roth, The college admissions problem is not equivalent to the marriage problem, J. Econom. Theory, 36 (1985), 277-288. doi: 10.1016/0022-0531(85)90106-1.
[4]	A. E. Roth, The evolution of the labor market for medical interns and residents: A case study in game theory, J. Political Econom., 92 (1984), 991-1016. doi: 10.1086/261272.
[5]	A. E. Roth, U. G. Rothblum and and J. H. Vande Vate, Stable matchings, optimal assignments, and linear programming, Math. Oper. Res., 18 (1993), 803-828. doi: 10.1287/moor.18.4.803.
[6]	A. E. Roth and M. A. Sotomayor, Two-Sided Matching. A Study in Game-Theoretic Modeling and Analysis, Econometric Society Monographs, 18, Cambidge University Press, Cambridge, 1990. doi: 10.1017/CCOL052139015X.
[7]	U. G. Rothblum, Characterization of stable matchings as extreme points of a polytope, Math. Programming, 54 (1992), 57-67. doi: 10.1007/BF01586041.
[8]	A. Schrijver, Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986.
[9]	J. Sethuraman, C.-P. Teo and L. Qian, Many-to-one stable matching: Geometry and fairness, Math. Oper. Res., 31 (2006), 581-596. doi: 10.1287/moor.1060.0207.
[10]	J. H. Vande Vate, Linear programming brings marital bliss, Oper. Res. Lett., 8 (1989), 147-153. doi: 10.1016/0167-6377(89)90041-2.

show all references

References:

[1]	M. Baïou and M. Balinski, The stable admissions polytope, Math. Program., 87 (2000), 427-439. doi: 10.1007/s101070050004.
[2]	D. Gale and L. S. Shapley, College admissions and the stability of marriage, Amer. Math. Monthly, 69 (1962), 9-15. doi: 10.1080/00029890.1962.11989827.
[3]	A. E. Roth, The college admissions problem is not equivalent to the marriage problem, J. Econom. Theory, 36 (1985), 277-288. doi: 10.1016/0022-0531(85)90106-1.
[4]	A. E. Roth, The evolution of the labor market for medical interns and residents: A case study in game theory, J. Political Econom., 92 (1984), 991-1016. doi: 10.1086/261272.
[5]	A. E. Roth, U. G. Rothblum and and J. H. Vande Vate, Stable matchings, optimal assignments, and linear programming, Math. Oper. Res., 18 (1993), 803-828. doi: 10.1287/moor.18.4.803.
[6]	A. E. Roth and M. A. Sotomayor, Two-Sided Matching. A Study in Game-Theoretic Modeling and Analysis, Econometric Society Monographs, 18, Cambidge University Press, Cambridge, 1990. doi: 10.1017/CCOL052139015X.
[7]	U. G. Rothblum, Characterization of stable matchings as extreme points of a polytope, Math. Programming, 54 (1992), 57-67. doi: 10.1007/BF01586041.
[8]	A. Schrijver, Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986.
[9]	J. Sethuraman, C.-P. Teo and L. Qian, Many-to-one stable matching: Geometry and fairness, Math. Oper. Res., 31 (2006), 581-596. doi: 10.1287/moor.1060.0207.
[10]	J. H. Vande Vate, Linear programming brings marital bliss, Oper. Res. Lett., 8 (1989), 147-153. doi: 10.1016/0167-6377(89)90041-2.

[1]	Fuhito Kojima. Finding all stable matchings with couples. Journal of Dynamics and Games, 2015, 2 (3&4) : 321-330. doi: 10.3934/jdg.2015008
[2]	Alvin E. Roth. Why do stable clearinghouses work so well? - Small sets of stable matchings in typical environments, and the limits-on-manipulation theorem of Demange, Gale and Sotomayor. Journal of Dynamics and Games, 2015, 2 (3&4) : 331-340. doi: 10.3934/jdg.2015009
[3]	V. Carmona, E. Freire, E. Ponce, F. Torres. The continuous matching of two stable linear systems can be unstable. Discrete and Continuous Dynamical Systems, 2006, 16 (3) : 689-703. doi: 10.3934/dcds.2006.16.689
[4]	François Genoud. Orbitally stable standing waves for the asymptotically linear one-dimensional NLS. Evolution Equations and Control Theory, 2013, 2 (1) : 81-100. doi: 10.3934/eect.2013.2.81
[5]	Kariane Calta, Thomas A. Schmidt. Infinitely many lattice surfaces with special pseudo-Anosov maps. Journal of Modern Dynamics, 2013, 7 (2) : 239-254. doi: 10.3934/jmd.2013.7.239
[6]	Charles Fefferman. Interpolation by linear programming I. Discrete and Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477
[7]	Dinh T. Tran, John A. G. Roberts. Linear degree growth in lattice equations. Journal of Computational Dynamics, 2019, 6 (2) : 449-467. doi: 10.3934/jcd.2019023
[8]	Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323
[9]	Brendan Pass. Multi-marginal optimal transport and multi-agent matching problems: Uniqueness and structure of solutions. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1623-1639. doi: 10.3934/dcds.2014.34.1623
[10]	Christoforidou Amalia, Christian-Oliver Ewald. A lattice method for option evaluation with regime-switching asset correlation structure. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1729-1752. doi: 10.3934/jimo.2020042
[11]	Zihui Liu, Xiangyong Zeng. The geometric structure of relative one-weight codes. Advances in Mathematics of Communications, 2016, 10 (2) : 367-377. doi: 10.3934/amc.2016011
[12]	Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[13]	Leandro Cioletti, Artur O. Lopes. Interactions, specifications, DLR probabilities and the Ruelle operator in the one-dimensional lattice. Discrete and Continuous Dynamical Systems, 2017, 37 (12) : 6139-6152. doi: 10.3934/dcds.2017264
[14]	Tran Ninh Hoa, Ta Duy Phuong, Nguyen Dong Yen. Linear fractional vector optimization problems with many components in the solution sets. Journal of Industrial and Management Optimization, 2005, 1 (4) : 477-486. doi: 10.3934/jimo.2005.1.477
[15]	Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283
[16]	Sishu Shankar Muni, Robert I. McLachlan, David J. W. Simpson. Homoclinic tangencies with infinitely many asymptotically stable single-round periodic solutions. Discrete and Continuous Dynamical Systems, 2021, 41 (8) : 3629-3650. doi: 10.3934/dcds.2021010
[17]	Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397
[18]	Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2020, 14 (2) : 333-357. doi: 10.3934/amc.2020024
[19]	Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003
[20]	Ruotian Gao, Wenxun Xing. Robust sensitivity analysis for linear programming with ellipsoidal perturbation. Journal of Industrial and Management Optimization, 2020, 16 (4) : 2029-2044. doi: 10.3934/jimo.2019041

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Pablo Neme Jorge Oviedo
on Google Scholar
Pablo Neme Jorge Oviedo

Impact Factor:

Tools

Article outline

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Pablo Neme Jorge Oviedo
on Google Scholar
Pablo Neme Jorge Oviedo

[Back to Top]