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

Pablo Neme; Jorge Oviedo

doi:10.3934/jdg.2021001

Article Contents

2021, Volume 8, Issue 1: 61-67. Doi: 10.3934/jdg.2021001

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

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

Pablo Neme and
Jorge Oviedo

Av. Italia 1556, San Luis, Argentina

Received: May 31, 2020

Revised: October 31, 2020

Early access: December 2020

Published: January 2021

^*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

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 90C05, 91B68.

Citation:

Full Text(HTML)

Related Papers

Cited by

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.