American Institute of Mathematical Sciences

Advanced
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  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 & 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. 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.  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. 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.  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. 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.  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. 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.  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]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[2]

Charlene Kalle, Niels Langeveld, Marta Maggioni, Sara Munday. Matching for a family of infinite measure continued fraction transformations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (11) : 6309-6330. doi: 10.3934/dcds.2020281
[3]

Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087
[4]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[5]

Emma D'Aniello, Saber Elaydi. The structure of $ \omega $-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195
[6]

Madalina Petcu, Roger Temam. The one dimensional shallow water equations with Dirichlet boundary conditions on the velocity. Discrete & Continuous Dynamical Systems - S, 2011, 4 (1) : 209-222. doi: 10.3934/dcdss.2011.4.209
[7]

Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409
[8]

Daoyuan Fang, Ting Zhang. Compressible Navier-Stokes equations with vacuum state in one dimension. Communications on Pure & Applied Analysis, 2004, 3 (4) : 675-694. doi: 10.3934/cpaa.2004.3.675
[9]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437
[10]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311
[11]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203
[12]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83
[13]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247
[14]

Mao Okada. Local rigidity of certain actions of solvable groups on the boundaries of rank-one symmetric spaces. Journal of Modern Dynamics, 2021, 17: 111-143. doi: 10.3934/jmd.2021004
[15]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
[16]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[17]

Arunima Bhattacharya, Micah Warren. $ C^{2, \alpha} $ estimates for solutions to almost Linear elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021024
[18]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81
[19]

Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055
[20]

Christophe Zhang. Internal rapid stabilization of a 1-D linear transport equation with a scalar feedback. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021006

 Impact Factor: 

Tools

Metrics

  • PDF downloads (36)
  • HTML views (108)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences