Πλοήγηση ανά Συγγραφέα "Eirinakis, Pavlos"
Τώρα δείχνει 1 - 2 από 2
- Αποτελέσματα ανά σελίδα
- Επιλογές ταξινόμησης
Τεκμήριο 2-sided and multi-sided stable matchings: structures, algorithms, and applicationsEirinakis, Pavlos; Athens University of Economics and Business, Department of Management Science and Technology; Miliotis, PanagiotisThis thesis examines the Stable Matching (SM) problem and some of its most important variants, namely the Stable Admissions (SA), the many-to-many Stable Matching (MM), and the Chain Stable Network (CSN) problem. In the context of the SM problem, 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. To identify them, we utilize rotations and the transitive reduction of the rotation-poset graph. Then, using a directed line-graph to represent the SM problem, namely the marriage graph, we derive a sparse description of the SM polytope. 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, we study the alternative rotation-based representation of the SM polytope, establishing its dimension and providing its minimal description.Further, we de.ne rotations in the SA setting and propose a time-optimal algorithm for identifying all rotations and all non-stable pairs. 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, we propose the use of a double-stack, a structure which enables exposing and eliminating rotations efficiently. Next, we revisit the corresponding rotation-poset graph and illustrate a time-and space-optimal algorithm for enumerating all solutions to the MM problem. Then, a polynomial algorithm for finding the minimum-weight stable matching is provided, which can also be used to improve the known time-bounds for identifying the egalitarian and the optimal one. The above mentioned algorithms are shown to be applicable even in the case of more complex preference and stability conditions. In a Constraint Programming (CP) context, we show that identifying all stable pairs in the SA and the MM case is equivalent to establishing hyperarc consistency. Furthermore, we provide a predicate which models the MM problem and its encoding as a Constraint Satisfaction Problem. We also propose establishing hyperarc consistency as a preprocessing step in a CP platform, thus obtaining an efficient programming tool to be used especially in the case where specialized algorithms are not applicable (i.e.,in cases where side-constraints are encompassed). The efficiency of our approach is then highlighted by a series of computational results. Last, a multi-sided stable matching configuration is examined; the participating agents are considered to be part of a specialized one-to-one Supply Chain Network (SCN). Under our specialized setting, we prove that every such k-sided SCN can be decomposed into k-1 independent SM sub-markets. Moreover, extending known results on the CSN problem, we show that the set of chain stable networks forms a distributive lattice with respect to the meet and join operations, while intermediary- optimal solutions always exist. Furthermore, we define the notion of contract-rotations, i.e., an extension of rotations, and illustrate that a series of algorithms proposed for the SM problem can be easily extended in our specialized setting.Τεκμήριο Serial dictatorship and simultaneous allocations of scarce resources: theory and applications(23-03-2023) Ξεπαπαδέας, Πέτρος; Xepapadeas, Petros; Athens University of Economics and Business, Department of Management Science and Technology; Androutsopoulos, Konstantinos; Kritikos, Emmanouil; Doukidis, Georgios; Eirinakis, Pavlos; Koundouri, Phoebe; Yannacopoulos, Athanasios; Mourtos, YannisΗ έρευνα σε αυτή τη διατριβή χρησιμοποιεί μαθηματική βελτιστοποίηση για τη μελέτη προβλημάτων κατανομής πόρων. Πιο συγκεκριμένα, αναλύονται προβλήματα που αφορούν πολλαπλούς πράκτορες με αυστηρές προτιμήσεις και διαδικασίες κατανομής πολλών πεπερασμένων πόρων μεταξύ αυτών των πρακτόρων, προκειμένου να ικανοποιηθούν δεδομένες απαιτήσεις. Για την επίλυση αυτών των προβλημάτων, χρησιμοποιήθηκαν διάφορες μέθοδοι, όπως η σειριακή δικτατορία και η ταυτόχρονη κατανομή (συνεργατική ή ανταγωνιστική), και στη συνέχεια εφαρμόστηκαν σε τρία προβλήματα του πραγματικού κόσμου. Αρχικά εφαρμόζουμε αυτές τις μεθόδους προκειμένου να μελετήσουμε ένα πρόβλημα μετεγκατάστασης στο οποίο οι χώρες επιδιώκουν να ικανοποιήσουν τη ζήτηση για μετεγκατάσταση από ετερογενείς κοινωνικές ομάδες. Επομένως, αυτό το πρόβλημα συνίσταται στην κατανομή ενός δεδομένου αριθμού προσφύγων -- οι οποίοι είναι ετερογενείς ως προς τη χώρα καταγωγής και τα χαρακτηριστικά όπως το φύλο, η ηλικία ή το μορφωτικό επίπεδο -- από την Ελλάδα σε άλλες χώρες της Ευρωπαϊκής Ένωσης που έχουν δεσμευτεί να δεχτούν έναν ορισμένο αριθμό προσφύγων. Προκειμένου να μελετηθεί αυτό το πρόβλημα, αναπτύχθηκε ένα εννοιολογικό πλαίσιο που αποτελείται από τρεις μεθόδους κατανομής: διαδοχική κατανομή πόρων πολλαπλών πρακτόρων, ταυτόχρονη κατανομή και κατανομή δύο σταδίων. Οι προτιμήσεις ενσωματώνονται σε αυτές τις μεθόδους υποθέτοντας ότι οι χώρες προορισμού έχουν τις δικές τους προτιμήσεις όσον αφορά τα χαρακτηριστικά των προσφύγων, αλλά ότι προσπαθούν επίσης να λάβουν υπόψη τις προτιμήσεις των προσφύγων για τις χώρες προορισμού. Ενώ αυτές οι μέθοδοι διαφέρουν ως προς το σχεδιασμό και την εκτέλεση, και οι τρεις στοχεύουν στη δημιουργία μιας πιο δίκαιης μεθοδολογίας κατανομής τόσο για τους πρόσφυγες όσο και για τις χώρες προορισμού. Αυτές οι μέθοδοι θα μπορούσαν επίσης να εφαρμοστούν σε άλλους παρόμοιους τύπους προβλημάτων κατανομής. Στη συνέχεια, μοντελοποιούμε τις κατανομές πόρων πολλαπλών πρακτόρων που αποτελούνται από πολλούς πράκτορες και τοποθεσίες και αναλύουμε τη σειριακή δικτατορία και τις προσεγγίσεις ταυτόχρονης κατανομής. Αυτές οι προσεγγίσεις εφαρμόζονται στη συνέχεια σε μια πραγματική περίπτωση συγκομιδής μυδιών. Το μοντέλο αναπτύσσεται σε ένα σύστημα πολλαπλών αλιέων, πολλαπλών τοποθεσιών, όπου ένας αλιέας μπορεί να αναδειχθεί ως ηγέτης Stackelberg ενώ οι υπόλοιποι είναι ακόλουθοι. Ωστόσο, το γενικευμένο μοντέλο μπορεί να χρησιμοποιηθεί για τη μελέτη πολλών άλλων προβλημάτων κατανομής πόρων. Οι εξωτερικότητες του δικτύου εισάγονται ως κόστος συμφόρησης και αναλύονται συστήματα διαχείρισης που βασίζονται σε ατομικές και συλλογικές ποσοστώσεις. Η παρουσία ενός ηγέτη Stackelberg είναι μια νέα προσέγγιση που επεκτείνει τα αποτελέσματα που λαμβάνονται στην κατανομή των πόρων, υποδεικνύοντας τη δυνατότητα πλήρους εξάλειψης των ακόλουθων, με επιπτώσεις στη βιωσιμότητα των αλιευτικών κοινοτήτων. Τα αποτελέσματα της κατανομής υπό διαφορετικές παραδοχές συγκρίνονται και συζητούνται πολιτικές που θα μπορούσαν να αποτρέψουν την έξοδο των ακόλουθων από την αγορά. Τέλος, εξετάζουμε και συγκρίνουμε μηχανισμούς για την εύρεση βέλτιστων λύσεων κατά Pareto για ένα πρόβλημα κατανομής πολλά-προς-πολλά. Η ρητή εισαγωγή της σειράς προτιμήσεων και η παροχή αναπαραστάσεων γραμμικού προγραμματισμού του προβλήματος κατανομής μας δίνει τη δυνατότητα να μελετήσουμε τη σειριακή δικτατορία και την ανταγωνιστική αντιστοίχιση με ταυτόχρονες επιλογές -- που είναι βασικά ένα γενικευμένο πρόβλημα ισορροπίας κατά Nash -- και να δείξουμε ότι υπό ορισμένες συνθήκες αυτή η κατανομή ισορροπίας κατά Nash είναι επίσης βέλτιστη κατά Pareto. Η διατριβή εξετάζει την ικανότητα των μηχανισμών μας να παρέχουν βέλτιστες κατανομές κατά Pareto και συγκρίνει τις λύσεις που λαμβάνονται από τους διαφορετικούς μηχανισμούς. Στη συνέχεια, οι μέθοδοι κατανομής εφαρμόζονται σε ένα πρόβλημα κατανομής νερού πολλών πηγών και πολλών χρήσεων και συγκρίνονται τα οφέλη που σχετίζονται με τη σειριακή δικτατορία ή τις ανταγωνιστικές κατανομές. Η θεωρητική έρευνα στους τομείς που περιγράφηκαν παραπάνω συνδυάστηκε σε κάθε περίπτωση με μια εφαρμογή, προκειμένου να καταδειχθεί η χρησιμότητά της στην αντιμετώπιση προβλημάτων του πραγματικού κόσμου και να βοηθήσει στο σχεδιασμό αποτελεσματικής πολιτικής όσον αφορά την κατανομή των πόρων. Επιπλέον, τα αποτελέσματα της έρευνας πρότειναν πολλά πιθανά πεδία για περαιτέρω έρευνα.