Economics at your fingertips  

A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas

Yu Yokoi ()
Additional contact information
Yu Yokoi: Department of Mathematical Informatics, University of Tokyo, Tokyo, 113-8656, Japan

Mathematics of Operations Research, 2017, vol. 42, issue 1, 238-255

Abstract: Classified stable matching, proposed by Huang, describes a matching model between academic institutes and applicants, in which each institute has upper and lower quotas on classes, i.e., subsets of applicants. Huang showed that the problem to decide whether there exists a stable matching or not is NP-hard in general. On the other hand, he showed that the problem is solvable if classes form a laminar family. For this case, Fleiner and Kamiyama gave a concise interpretation in terms of matroids and showed the lattice structure of stable matchings.In this paper we introduce stable matchings on generalized matroids, extending the model of Fleiner and Kamiyama. We design a polynomial-time algorithm which finds a stable matching or reports the nonexistence. We also show that the set of stable matchings, if nonempty, forms a lattice with several significant properties. Furthermore, we extend this structural result to the polyhedral framework, which we call stable allocations on generalized polymatroids.

Keywords: stable matching; lower quotas; matroids; generalized polymatroids; polynomial-time algorithm (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: Track citations by RSS feed

Downloads: (external link) (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link:

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Matthew Walls ().

Page updated 2019-05-29
Handle: RePEc:inm:ormoor:v:42:y:2017:i:1:p:238-255