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

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 - A, 2021  doi: 10.3934/dcds.2021010

[2]

Noufel Frikha, Valentin Konakov, Stéphane Menozzi. Well-posedness of some non-linear stable driven SDEs. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 849-898. doi: 10.3934/dcds.2020302

[3]

Pavel Eichler, Radek Fučík, Robert Straka. Computational study of immersed boundary - lattice Boltzmann method for fluid-structure interaction. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 819-833. doi: 10.3934/dcdss.2020349

[4]

Hyung-Chun Lee. Efficient computations for linear feedback control problems for target velocity matching of Navier-Stokes flows via POD and LSTM-ROM. Electronic Research Archive, , () : -. doi: 10.3934/era.2020128

[5]

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162

[6]

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

[7]

Maicon Sônego. Stable transition layers in an unbalanced bistable equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020370

[8]

François Dubois. Third order equivalent equation of lattice Boltzmann scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 221-248. doi: 10.3934/dcds.2009.23.221

[9]

Xiyou Cheng, Zhitao Zhang. Structure of positive solutions to a class of Schrödinger systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020461

[10]

Amira M. Boughoufala, Ahmed Y. Abdallah. Attractors for FitzHugh-Nagumo lattice systems with almost periodic nonlinear parts. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1549-1563. doi: 10.3934/dcdsb.2020172

[11]

Editorial Office. Retraction: Xiaohong Zhu, Zili Yang and Tabharit Zoubir, Research on the matching algorithm for heterologous image after deformation in the same scene. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1281-1281. doi: 10.3934/dcdss.2019088

[12]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[13]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

[14]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012

[15]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136

[16]

Toshiko Ogiwara, Danielle Hilhorst, Hiroshi Matano. Convergence and structure theorems for order-preserving dynamical systems with mass conservation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3883-3907. doi: 10.3934/dcds.2020129

[17]

Adrian Viorel, Cristian D. Alecsa, Titus O. Pinţa. Asymptotic analysis of a structure-preserving integrator for damped Hamiltonian systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020407

[18]

Leanne Dong. Random attractors for stochastic Navier-Stokes equation on a 2D rotating sphere with stable Lévy noise. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020352

[19]

Mia Jukić, Hermen Jan Hupkes. Dynamics of curved travelling fronts for the discrete Allen-Cahn equation on a two-dimensional lattice. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020402

[20]

Yohei Yamazaki. Center stable manifolds around line solitary waves of the Zakharov–Kuznetsov equation with critical speed. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021008

 Impact Factor: 

Article outline

[Back to Top]