Serial dictatorship and simultaneous allocations of scarce resources: theory and applications

Abstract

The research in this thesis uses mathematical optimization to study resource allocation problems. More specifically, problems are analyzed that involve multiple agents with strict preferences, and processes of distributing several finite resources among these agents, in order to satisfy given demands. To solve these problems, several methods were utilized, namely serial dictatorship, and simultaneous allocation (cooperative or competitive), and then applied to three real world problems. We first apply these methods in order to study a relocation problem in which countries seek to satisfy demand for reallocation from heterogenous social groups. Thus this problem consists of allocating a given number of refugees -- who are heterogeneous with respect to country of origin and characteristics such as gender, age or educational level -- from Greece to other European Union countries which have pledged to accept a certain number of refugees. In order to study this problem, a conceptual framework was developed that consists of three allocation methods: sequential multi-agent resource allocation, simultaneous allocation, and two-stage allocation. Preferences are incorporated into these methods by assuming that the destination countries have their own preferences regarding refugee characteristics, but that they also try to consider the refugees' preferences for the destination countries. While these methods vary in design and execution, all three of them aim to create a more equitable allocation methodology for both the refugees and the destination countries. These methods could also be applied to other similar types of allocation problems. Next, we model multi-agent resource allocations consisting of many agents and sites and analyze the serial dictatorship and simultaneous allocation approaches. These approaches are then applied to an actual case of mussel harvesting. For tractability, the model is developed in a multi-fisher, multi-site fishery where one fisher may emerge as a Stackelberg leader while the rest are followers; however, the generalized model can be used to study many other resource allocation problems. Network externalities are introduced as congestion costs, and management systems based on individual and collective quotas are analyzed. The presence of a Stackelberg leader is a novel approach that extends results obtained in resource allocation, indicating the possibility of full elimination of followers, with impacts on the sustainability of fishing communities. Allocation outcomes under different assumptions are compared, and policies that could prevent the followers from exiting the market are discussed. Finally, we examine and compare mechanisms for finding Pareto optimal solutions for a many-to-many allocation problem. Explicitly introducing preference ordering and providing linear programming representations of the allocation problem enables us to study serial dictatorship and competitive matching with simultaneous choices -- which is basically a generalized Nash equilibrium problem -- and to show that under certain conditions this Nash equilibrium allocation is also Pareto optimal. The paper examines the ability of our mechanisms to provide Pareto optimal allocations, and compares the solutions obtained from the different mechanisms. The allocation methods are then applied to a many-sources, many-uses water allocation problem, and the benefits associated with serial dictatorship or competitive allocations are compared. The theoretical research into the areas described above was combined in each case with an application, in order to demonstrate its usefulness in addressing real world problems and in helping to design efficient policy regarding resource allocation. Furthermore, the outcomes of the research suggested many promising areas for further research.

Η έρευνα σε αυτή τη διατριβή χρησιμοποιεί μαθηματική βελτιστοποίηση για τη μελέτη προβλημάτων κατανομής πόρων. Πιο συγκεκριμένα, αναλύονται προβλήματα που αφορούν πολλαπλούς πράκτορες με αυστηρές προτιμήσεις και διαδικασίες κατανομής πολλών πεπερασμένων πόρων μεταξύ αυτών των πρακτόρων, προκειμένου να ικανοποιηθούν δεδομένες απαιτήσεις. Για την επίλυση αυτών των προβλημάτων, χρησιμοποιήθηκαν διάφορες μέθοδοι, όπως η σειριακή δικτατορία και η ταυτόχρονη κατανομή (συνεργατική ή ανταγωνιστική), και στη συνέχεια εφαρμόστηκαν σε τρία προβλήματα του πραγματικού κόσμου. Αρχικά εφαρμόζουμε αυτές τις μεθόδους προκειμένου να μελετήσουμε ένα πρόβλημα μετεγκατάστασης στο οποίο οι χώρες επιδιώκουν να ικανοποιήσουν τη ζήτηση για μετεγκατάσταση από ετερογενείς κοινωνικές ομάδες. Επομένως, αυτό το πρόβλημα συνίσταται στην κατανομή ενός δεδομένου αριθμού προσφύγων -- οι οποίοι είναι ετερογενείς ως προς τη χώρα καταγωγής και τα χαρακτηριστικά όπως το φύλο, η ηλικία ή το μορφωτικό επίπεδο -- από την Ελλάδα σε άλλες χώρες της Ευρωπαϊκής Ένωσης που έχουν δεσμευτεί να δεχτούν έναν ορισμένο αριθμό προσφύγων. Προκειμένου να μελετηθεί αυτό το πρόβλημα, αναπτύχθηκε ένα εννοιολογικό πλαίσιο που αποτελείται από τρεις μεθόδους κατανομής: διαδοχική κατανομή πόρων πολλαπλών πρακτόρων, ταυτόχρονη κατανομή και κατανομή δύο σταδίων. Οι προτιμήσεις ενσωματώνονται σε αυτές τις μεθόδους υποθέτοντας ότι οι χώρες προορισμού έχουν τις δικές τους προτιμήσεις όσον αφορά τα χαρακτηριστικά των προσφύγων, αλλά ότι προσπαθούν επίσης να λάβουν υπόψη τις προτιμήσεις των προσφύγων για τις χώρες προορισμού. Ενώ αυτές οι μέθοδοι διαφέρουν ως προς το σχεδιασμό και την εκτέλεση, και οι τρεις στοχεύουν στη δημιουργία μιας πιο δίκαιης μεθοδολογίας κατανομής τόσο για τους πρόσφυγες όσο και για τις χώρες προορισμού. Αυτές οι μέθοδοι θα μπορούσαν επίσης να εφαρμοστούν σε άλλους παρόμοιους τύπους προβλημάτων κατανομής. Στη συνέχεια, μοντελοποιούμε τις κατανομές πόρων πολλαπλών πρακτόρων που αποτελούνται από πολλούς πράκτορες και τοποθεσίες και αναλύουμε τη σειριακή δικτατορία και τις προσεγγίσεις ταυτόχρονης κατανομής. Αυτές οι προσεγγίσεις εφαρμόζονται στη συνέχεια σε μια πραγματική περίπτωση συγκομιδής μυδιών. Το μοντέλο αναπτύσεται σε ένα σύστημα πολλαπλών αλιέων, πολλαπλών τοποθεσιών, όπου ένας αλιέας μπορεί να αναδειχθεί ως ηγέτης Stackelberg ενώ οι υπόλοιποι είναι ακόλουθοι. Ωστόσο, το γενικευμένο μοντέλο μπορεί να χρησιμοποιηθεί για τη μελέτη πολλών άλλων προβλημάτων κατανομής πόρων. Οι εξωτερικότητέςτου δικτύου εισάγονται ως κόστος συμφόρησης και αναλύονται συστήματα διαχείρισης που βασίζονται σε ατομικές και συλλογικές ποσοστώσεις. Η παρουσία ενός ηγέτη Stackelberg είναι μια νέα προσέγγιση που επεκτείνει τα αποτελέσματα που λαμβάνονται στην κατανομή των πόρων, υποδεικνύοντας τη δυνατότητα πλήρους εξάλειψης των ακόλουθων, με επιπτώσεις στη βιωσιμότητα των αλιευτικών κοινοτήτων. Τα αποτελέσματα της κατανομής υπό διαφορετικές παραδοχές συγκρίνονται και συζητούνται πολιτικές που θα μπορούσαν να αποτρέψουν την έξοδο των ακόλουθων από την αγορά. Τέλος, εξετάζουμε και συγκρίνουμε μηχανισμούς για την εύρεση βέλτιστων λύσεων κατά Pareto για ένα πρόβλημα κατανομής πολλά-προς-πολλά. Η ρητή εισαγωγή της σειράς προτιμήσεων και η παροχή αναπαραστάσεων γραμμικού προγραμματισμού του προβλήματος κατανομής μας δίνει τη δυνατότητα να μελετήσουμε τη σειριακή δικτατορία και την ανταγωνιστική αντιστοίχιση με ταυτόχρονες επιλογές -- που είναι βασικά ένα γενικευμένο πρόβλημα ισορροπίας κατά Nash -- και να δείξουμε ότι υπό ορισμένες συνθήκες αυτή η κατανομή ισορροπίας κατά Nash είναι επίσης βέλτιστη κατά Pareto. Η διατριβή εξετάζει την ικανότητα των μηχανισμών μας να παρέχουν βέλτιστες κατανομές κατά Pareto και συγκρίνει τις λύσεις που λαμβάνονται από τους διαφορετικούς μηχανισμούς. Στη συνέχεια, οι μέθοδοι κατανομής εφαρμόζονται σε ένα πρόβλημα κατανομής νερού πολλών πηγών και πολλών χρήσεων και συγκρίνονται τα οφέλη που σχετίζονται με τη σειριακή δικτατορία ή τις ανταγωνιστικές κατανομές. Η θεωρητική έρευνα στους τομείς που περιγράφηκαν παραπάνω συνδυάστηκε σε κάθε περίπτωση με μια εφαρμογή, προκειμένου να καταδειχθεί η χρησιμότητά της στην αντιμετώπιση προβλημάτων του πραγματικού κόσμου και να βοηθήσει στο σχεδιασμό αποτελεσματικής πολιτικής όσον αφορά την κατανομή των πόρων. Επιπλέον, τα αποτελέσματα της έρευνας πρότειναν πολλά πιθανά πεδία για περαιτέρω έρευνα.