Optimisation under preferences for matchings and circulations: combinatorial and polyhedral aspects

Abstract

This thesis examines different optimisation problems under preferences defined in terms of Graph Theory. We are interested in studying them from both combinatorial, polyhedral and algorithmic view. What we call preferences represent expressed options or possible decisions for an individual in an ordinal scale that answers which is better than the other. Many of the problems we study have been used to represent real life decision making situations for individuals or organizations. Firstly, the Stable Matching problem (SM), the many-to-many Stable Matching problem (MM) and the Stable Allocation (SA) are presented alongside with some important combinatorial and polyhedral results about them. A minimal polyhedral description is provided for SM, MM and the unconstrained case of SA via an affine transformation of the order polytope of their rotation-poset. For the unconstrained case of SA it is the first time that a minimal description is provided. To establish this affine transformation some necessary structure results for these problems have been proved. Then, this thesis proposes a novel setting of relaxing stability in SM, called Unstable Matching problem, where each pair has a value for participating in the matching and a cost of blocking it. Finding a matching of that maximizes the function of value minus the blocking cost is NP-hard. If the value and the cost function are identical the cases where either this function is restricted to (0, 1) or satisfies the preference-concordancy property are solved in polynomial time. In contrast, if the function is restricted to two general values (α, β) the problem remains NP-hard. Another variation that is proved to be polynomially solvable is when the set of pairs is partitioned into those that can be part of the output matching but are not allowed to block it (their cost is +∞) and those that can block at a cost, but cannot be part of it (their value is −∞). This thesis also examines a novel one-to-many generalization of House Allocation problem where there is no upper bound of how many agents can receive a specific good but there are pairs of agents who cannot receive the same good. From another perspective this variation of House Allocation problem can be viewed as a list coloring under preferences problem. Even though Serial Dictatorship mechanism still returns a Pareto optimal allocation, a simple counter example shows that there are Pareto optimal allocations not obtainable by SD. Interestingly, the problem of verifying whether a given assignment is Pareto optimal is no longer easy but becomes coNP-complete. Some special cases where the verification problem remains easy are shown. The last problem studied in this thesis is an exchange market under preferences variation with agent-specific indivisible goods where the central criterion is Pareto optimality. A solution is returned by Top Trading Cycle Mechanism and also a combinatorial characterization of the Pareto optimal solutions is provided. This characterization leads directly to an easy way of recognising whether a given exchange is Pareto optimal. Moreover, it is proved that if there is a weight function for the possible exchange finding the maximum weight exchange is NP-hard. If the weight satisfies the preference-concordancy property then the problem is solved in polynomial time.

Σε αυτή τη διδακτορική διατριβή εξετάζονται διάφορα προβλήματα βελτιστοποίησης υπό προτιμήσεις που ορίζονται με όρους Θεωρίας Γραφημάτων. Μελετάμε τα προβλήματα αυτά από συνδυαστική, πολυεδρική και αλγοριθμική άποψη. Αυτό που αναφέρουμε ως προτιμήσεις αντιπροσωπεύει εκφρασμένες επιλογές ή πιθανές αποφάσεις για ένα άτομο σε μια διάταξη που απαντά ποια είναι καλύτερη από την άλλη. Πολλά από τα προβλήματα που μελετάμε έχουν χρησιμοποιηθεί για να αναπαραστήσουν πραγματικές καταστάσεις λήψης αποφάσεων για άτομα ή οργανισμούς. Πρώτον, το πρόβλημα του Ευσταθούς Ταιριάσματος (SM), το πρόβλημα του πολλά-προς-πολλά Ευσταθούς Ταιριάσματος (MM) και το πρόβλημα της Ευσταθούς Κατανομής (SA) παρουσιάζονται μαζί με μερικά σημαντικά συνδυαστικά και πολυεδρικά αποτελέσματα σχετικά με αυτά. Δίνεται μια ελαχιστική πολυεδρική περιγραφή για τα SM, MM και την μη περιορισμένη περίπτωση του SA μέσω ενός αφινικού μετασχηματισμού του πολυτόπου διάταξης της διάταξης των περιστροφών τους. Για την μη περιορισμένη περίπτωση του SA είναι η πρώτη φορά που δίνεται μια ελάχιστική περιγραφή. Για να δειχθεί αυτός ο μετασχηματισμός αποδεικνύουμε διάφορα συνδυαστικά αποτελέσματα για τα πρoβληματα αυτά. Στη συνέχεια, αυτή η διατριβή προτείνει έναν νέο τρόπο χαλάρωσης του κριτηριού της Ευστάθειας στο SM, ορίζοντας το Πρόβλημα ασταθούς ταιριάσματος, όπου κάθε ζεύγος έχει μία τιμή κέρδους εάν συμμετέχει στο ταίριασμα και μια τιμή κόστους εάν το μπλοκάρει. Η εύρεση ενός ταιριάσματος που μεγιστοποιεί τη συνάρτηση το κέρδος από τα ζευγάρια που συμμετέχουν σε αυτό μείον το κόστος από τα ζευγάρια που το μπλοκάρουν είναι NP-δύσκολο. Αν η τιμή κέρδους και η τιμή κόστους ταυτίζονται για κάθε ζευγάρι οι περιπτώσεις όπου είτε αυτή η συνάρτηση περιορίζεται στο (0, 1) είτε είναι αύξουσα ως προς τις προτιμήσεις επιλύονται σε πολυωνυμικό χρόνο. Αντίθετα, εάν η συνάρτηση περιορίζεται σε δύο γενικές τιμές (α, β), το πρόβλημα παραμένει NP-hard. Μια άλλη περίπτωση που αποδεικνύεται ότι το πρόβλημα αυτο είναι πολυωνυμικά επιλύσιμο είναι όταν το σύνολο των ζευγαριών διαμερίζεται σε αυτά που μπορούν να αποτελούν μέρος της αντιστοίχισης εξόδου αλλά δεν επιτρέπεται να το μπλοκάρουν (η τιμή κόστους τους είναι +∞) και σε εκείνα που μπορούν να μπλοκάρουν ενα ταίριασμα με κάποιο κόστος, αλλά δεν μπορεί να είναι μέρος του (η τιμή κέρδους τους είναι −∞). Αυτή η διατριβή εξετάζει επίσης μια νέα γενίκευση ενός-προς-πολλά του Παρέτο βέλτιστου ταιριάσματος όπου δεν υπάρχει ανώτατο όριο για το πόσοι συμμετέχοντες μπορούν να λάβουν ένα συγκεκριμένο αγαθό, αλλά υπάρχουν ζεύγη συμμετεχόντων που δεν μπορούν να λάβουν το ίδιο αγαθό. Από μια άλλη οπτική γωνία, αυτή η παραλλαγή του προβλήματος μπορεί να θεωρηθεί ως πρόβλημα χρωματισμού σε ένα γράφημα μεσα απο λίστα προτιμήσεων. Παρόλο που ο μηχανισμός της Σειριακής Δικτατορίας επιστρέφει ένα Παρέτο βέλτιστο χρωματισμό, μέσω αντιπαραδείγματος δείχνουμε οτι το αντίστροφο δεν ισχύει και ότι υπάρχουν Παρέτο βέλτιστοι χρωματισμοί που δεν μπορούν να ληφθούν από την Σειριακή Δικτατορία. Πλέον το πρόβλημα του να αποφασίσουμε εάν ενας δεδομένος χρωματισμός είναι Πάρετο βέλτιστος δεν είναι πλέον εύκολο, αλλά γίνεται coNP-δύσκολο. Σε ορισμένες ειδικές περιπτώσεις παραμένει πολυωνυμικά επιλύσιμο. Το τελευταίο πρόβλημα που μελετήθηκε σε αυτή τη διατριβή είναι ένα προβλημα ανταλλακτικών αγορών με αδιαίρετα αγαθά οπου οι συμμετέχοντες εκφράζουν προτιμήσεις και το κεντρικό κριτήριο που είναι ζητούμενο σε μια ανταλλαγή είναι η Παρέτο βελτιστότητα. Επιστρέφεται μια λύση από τον μηχανισμο Top Trading Cycle και παρέχεται επίσης ένας συνδυαστικός χαρακτηρισμός των Παρέτο βέλτιστων λύσεων. Αυτός ο χαρακτηρισμός οδηγεί άμεσα σε έναν εύκολο τρόπο αναγνώρισης εάν μια δεδομένη ανταλλαγή είναι Παρέτο βέλτιστη. Επιπλέον, αποδεικνύεται ότι εάν υπάρχει συνάρτηση βάρους για την εύρεση πιθανής ανταλλαγής, η ανταλλαγή μέγιστου βάρους είναι NP-δύσκολο. Εάν το βάρος είναι συνάρτηση αύξουσα ως προς τις προτιμήσεις τότε το πρόβλημα λύνεται σε πολυωνυμικό χρόνο.