Athens University Economics and Business (AUEB)
2-sided and multi-sided stable matchings: structures, algorithms, and applications
Abstract
dc:descriptionThis thesis examines the Stable Matching problem (SM) and some of its most important variants, namely the Stable Admissions (SAX the many-to-many Stable Matching (MM), and the Chain Stable Network problem. In the context of the SM, a time-optimal algorithm is provided that identifies which of the non-stable pairs can be removed from the agents' preference lists without altering the set of solutions. Then, using a directed line-graph to represent the SM, a sparse description of the SM polytope is derived. This description is further reduced to obtain the minimal one by identifying the minimal equation system and the facets of the corresponding polytope. Also, the dimension of the SM polytope is proved to be equal to the number of rotations, while its diameter is also established. Moreover, the alternative rotation-based representation of the SM polytope is also examined. Further, rotations are defined in the SA setting and a time-optimal algorithm for identifying all rotations and all non-stable pairs is proposed. This algorithm is then extended to the MM case under pairwise stability, preferences over individuals, and the max-min criterion. In order to maintain the algorithms optimal complexity, the use of a double-stack is proposed. Next, the corresponding rotation-poset graph is revisited and a time- and space-optimal algorithm for enumerating all solutions to the MM is illustrated. Then, a polynomial algorithm for finding the minimum-weight stable matching is provided, which is shown to be applicable even in the case of more complex preference and stability conditions. In a Constraint Programming (CP) context, it is shown that identifying all stable pairs in the SA and the MM case is equivalent to establishing hyperarc consistency. Furthermore, a predicate which models the MM and its encoding as a Constraint Satisfaction Problem is provided. Also, establishing hyperarc consistency as a preprocessing step in a CP platform is proposed, thus obtaining an efficient programming tool, especially in the case where side-constraints are present. Last, a multi-sided Supply Chain Network (SCN) configuration is examined. Under this reduced setting, it is proved that every such £-sided SCN can be decomposed into k-1 independent SM sub-markets. Moreover, it is shown that the set of chain stable networks forms a distributive lattice. Furthermore, the notion of contract-rotations is defined and a series of specialized algorithms are proposed.
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 2010
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Eirinakis, Pavlos
- Ειρηνάκης, Παύλος
Subjects
dc:subject × 20- Ευστάθεια
- Ευσταθής γάμος
- Ευσταθής εισαγωγή
- Ευσταθής εφοδιαστική αλυσίδα
- Προγραμματισμός περιορισμών
- Αλγοριθμικη ανάλυση
- Πολυεδρική ανάλυση
- Περιστροφή
- Stability
- Stable marriage
- College admissions
- Chain stable Supply chain network
- Constraint programming
- Algorithmic analysis
- Polyhedral analysis
- Rotations
- Κοινωνικές Επιστήμες
- Οικονομικά και Επιχειρήσεις
- Social Sciences
- Economics and Business
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/22841