2-sided and multi-sided stable matchings: structures, algorithms, and applications

Abstract

This 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.

Η διατριβή αυτή εξετάζει το πρόβλημα του Ευσταθούς Ταιριάσματος (ET), της Ευσταθούς Εισαγωγής (ΕΕ), του πολλά-προς-πολλά Ευσταθούς Ταιριάσματος (ΊΊΠ) και της Ευσταθούς Εφοδιαστικής Αλυσίδας (ΕΕΑ). Στα πλαίσια του ET, παρέχεται ένας χρονικά βέλτιστος αλγόριθμος που αναγνωρίζει ποια από τα μη ευσταθή ζεύγη μπορούν να αφαιρεθούν από τις λίστες προτίμησης χωρίς να προκαλέσουν αλλαγές στο σύνολο των λύσεων. Επιπλέον, χρησιμοποιώντας ένα κατευθυνόμενο γραμμογράφημα και το μειωμένο γράφημα περιστροφών, δίνεται η ελάχιστη περιγραφή του πολυτόπου του ET. Επιπλέον, η διάσταση του αποδεικνύεται ότι είναι ίση με τον αριθμό των περιστροφών, ενώ υπολογίζεται και η διάμετρος του. Ακόμα, εξετάζεται και η εναλλακτική αναπαράσταση του πολυτόπου αυτού που βασίζεται στις περιστροφές. Επίσης, οι περιστροφές ορίζονται στα πλαίσια του ΕΕ, όπου δίνεται ένας χρονικά βέλτιστος αλγόριθμος για την αναγνώριση όλων των περιστροφών και των μη ευσταθών ζευγών. Ο αλγόριθμος αυτός επεκτείνεται και στην περίπτωση του ΠΠ υπό ζευγωτή ευστάθεια, ατομικές προτιμήσεις και το κριτήριο max-min. Μάλιστα, η χρήση μιας διπλής στοίβας προτείνεται για την διατήρηση της βελτιστότητας του αλγορίθμου αυτού. Στη συνέχεια, επανεξετάζονται οι κανόνες κατασκευής του γραφήματος περιστροφών και παρέχεται ένας χρονικά και χωρικά βέλτιστος αλγόριθμος για την απαρίθμηση όλων των λύσεων. Επιπλέον, παρέχεται ένας πολυωνυμικός αλγόριθμος για την εύρεση της λύσης ελαχίστου βάρους, ο οποίος αποδεικνύεται ότι μπορεί να εφαρμοστεί ακόμα και σε περιπτώσεις με πιο περίπλοκες συνθήκες προτιμήσεων και ευστάθειας. Στα πλαίσια του προγραμματισμού περιορισμών (ΉΕ), αποδεικνύεται ότι η αναγνώριση όλων των ευσταθών ζευγών στην περίπτωση του ΕΕ και του ΠΠ ισοδυναμεί με την επίτευξη συνέπειας υπερακμής. Επίσης, παρουσιάζεται ένας περιορισμός ο οποίος μοντελοποιεί το ΠΠ καθώς και η κωδικοποίηση του ως πρόβλημα ικανοποίησης περιορισμών. Επιπλέον, προτείνεται η χρήση του αλγορίθμου που επιτυγχάνει συνέπεια υπερακμής ως ένα προ-επεξεργαστικό βήμα σε μια πλατφόρμα ΠΕ. Η μέθοδος αυτή καταδεικνύεται ότι είναι ιδιαίτερα αποτελεσματική, ιδίως υπό την παρουσία επιπλέον περιορισμών. Τέλος, μελετάται μια εξειδικευμένη εκδοχή του ΕΕΑ. Αποδεικνύεται ότι μία εφοδιαστική αλυσίδα με k σύνολα μπορεί να διαιρεθεί σε k-1 ανεξάρτητες αγορές ET, ενώ η κλίμακα που δημιουργείται από το σύνολο των λύσεων είναι κατανεμημένη. Επιπλέον, ορίζεται η έννοια της περιστροφής συμβολαίων, και παρέχεται μια σειρά από σχετικούς εξειδικευμένους αλγορίθμους.