EconPapers    
Economics at your fingertips  
 

Polyhedral Aspects of Stable Marriage

Pavlos Eirinakis (), Dimitrios Magos (), Ioannis Mourtos () and Panayiotis Miliotis ()
Additional contact information
Pavlos Eirinakis: Department of Management Science and Technology, Athens University of Economics and Business, 104 34 Athens, Greece
Dimitrios Magos: Department of Informatics, Technological Educational Institute of Athens, 122 10 Egaleo, Greece
Ioannis Mourtos: Department of Management Science and Technology, Athens University of Economics and Business, 104 34 Athens, Greece
Panayiotis Miliotis: Department of Management Science and Technology, Athens University of Economics and Business, 104 34 Athens, Greece

Mathematics of Operations Research, 2014, vol. 39, issue 3, 656-671

Abstract: In the setting of the stable matching (SM) problem, it has been observed that some of the man-woman pairs cannot be removed although they participate in no stable matching, since such a removal would alter the set of solutions. These pairs are yet to be identified. Likewise (and despite the sizeable literature), some of the fundamental characteristics of the SM polytope (e.g., its dimension, its facets, etc.) have not been established. In the current work, we show that these two seemingly distant open issues are closely related. More specifically, we identify the pairs with the above-mentioned property and present a polynomial algorithm for producing a set of minimal preference lists. We utilize this result in the context of two different representations of the SM structure (rotation-poset graph and algebraic formulation) and derive the dimension of the SM polytope to obtain all alternative minimal linear descriptions.

Keywords: stable matching; stable marriage; rotation poset; polytope; facet (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: Track citations by RSS feed

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2013.0616 (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: https://EconPapers.repec.org/RePEc:inm:ormoor:v:39:y:2014:i:3:p:656-671

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:39:y:2014:i:3:p:656-671