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

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

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.

Citation: Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & 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.  Google Scholar

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

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

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

[5]

A. E. RothU. 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.  Google Scholar

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

U. G. Rothblum, Characterization of stable matchings as extreme points of a polytope, Math. Programming, 54 (1992), 57-67.  doi: 10.1007/BF01586041.  Google Scholar

[8]

A. Schrijver, Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986.  Google Scholar

[9]

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

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

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

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

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

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

[5]

A. E. RothU. 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.  Google Scholar

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

U. G. Rothblum, Characterization of stable matchings as extreme points of a polytope, Math. Programming, 54 (1992), 57-67.  doi: 10.1007/BF01586041.  Google Scholar

[8]

A. Schrijver, Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986.  Google Scholar

[9]

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

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

[1]

Fuhito Kojima. Finding all stable matchings with couples. Journal of Dynamics & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems, 2017, 37 (12) : 6139-6152. doi: 10.3934/dcds.2017264

[14]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283

[15]

Tran Ninh Hoa, Ta Duy Phuong, Nguyen Dong Yen. Linear fractional vector optimization problems with many components in the solution sets. Journal of Industrial & Management Optimization, 2005, 1 (4) : 477-486. doi: 10.3934/jimo.2005.1.477

[16]

Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397

[17]

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

[18]

Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003

[19]

Ruotian Gao, Wenxun Xing. Robust sensitivity analysis for linear programming with ellipsoidal perturbation. Journal of Industrial & Management Optimization, 2020, 16 (4) : 2029-2044. doi: 10.3934/jimo.2019041

[20]

Sishu Shankar Muni, Robert I. McLachlan, David J. W. Simpson. Homoclinic tangencies with infinitely many asymptotically stable single-round periodic solutions. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3629-3650. doi: 10.3934/dcds.2021010

 Impact Factor: 

Metrics

  • PDF downloads (83)
  • HTML views (231)
  • Cited by (0)

Other articles
by authors

[Back to Top]