Solution concepts and algorithms for fair division under constraints

Abstract

Το πρόβλημα της δίκαιης ανάθεσης πόρων—πώς να διαμοιραστούν οι πόροι μεταξύ ατόμων με διαφορετικές προτιμήσεις με δίκαιο τρόπο—έχει απασχολήσει τους μαθηματικούς και τους οικονομολόγους από την αρχαιότητα, με το πρόβλημα κατανομής της γης, έως τα προβλήματα που ανακύπτουν σε σύγχρονα περιβάλλοντα, όπως η ανάθεση πόρων στο cloud ή ο διαμοιρασμός της κληρονομιάς. Ενώ, όμως, τα διαιρετά αγαθά μπορούν να κατανεμηθούν χρησιμοποιώντας γνωστά πρωτόκολλα, τα αδιαίρετα αγαθά παρουσιάζουν προκλήσεις. Ένα καθιερωμένο κριτήριο δικαιοσύνης είναι η απουσία φθόνου (EF), η οποία απαιτεί κανένας συμμετέχοντας (στο εξής πράκτορας) να μην προτιμά το μερίδιο (στο εξής πακέτο) ενός άλλου από το δικό του. Ωστόσο, όσον αφορά τα αδιαίρετα αγαθά, η απουσία φθόνου είναι συχνά ανέφικτη, γεγονός που οδηγεί στη μελέτη χαλαρώσεων, όπως η απουσία φθόνου έως ένα αγαθό (envy-freeness up to one good, EF1) και η απουσία φθόνου έως οποιοδήποτε αγαθό (envy-freeness up to any good, EFX). Η παρούσα διπλωματική εργασία επικεντρώνεται στην περίπτωση όπου ισχύουν πρόσθετοι περιορισμοί σχετικά με τις εφικτές αναθέσεις. Ένα πραγματικό σενάριο είναι όταν οι πράκτορες πρέπει να λάβουν τον ίδιο αριθμό αγαθών. Για να αντιμετωπιστούν τέτοιες καταστάσεις, πρόσφατες εργασίες έχουν εισαγάγει έννοιες δικαιοσύνης βασισμένες στην ανταλλαγή, όπως οι EFF1 και EFFX, όπου ο φθόνος μπορεί να εξαλειφθεί με την ανταλλαγή ενός (ή, αντίστοιχα, οποιουδήποτε) αγαθού μεταξύ των πακέτων. Αυτοί οι ορισμοί ευθυγραμμίζονται φυσικά με τον περιορισμό που περιγράψαμε, αλλά οι ιδιότητές τους παραμένουν σε μεγάλο βαθμό ανεξερεύνητες. Η συμβολή της διπλωματικής εργασίας εκτείνεται σε δύο άξονες. Πρώτον, παρέχει μια ολοκληρωμένη επισκόπηση της βιβλιογραφίας σχετικά με τη δίκαιη κατανομή αδιαίρετων αγαθών, με έμφαση σε μοντέλα με περιορισμούς (πληθικότητας, συνδεσιμότητας, προϋπολογισμού και μητροειδών). Δεύτερον, παρουσιάζει νέα αποτελέσματα σχετικά με τα κριτήρια δικαιοσύνης βάσει ανταλλαγής, διερευνώντας την ύπαρξή τους και την επίδοση γνωστών αλγορίθμων όπως ο Envy Cycle Elimination. Επιπλέον, μελετάμε σε ποιο βαθμό μπορούν να συνυπάρξουν η δικαιοσύνη και η αποδοτικότητα.The problem of fair division—allocating resources fairly among agents with different preferences—has been relevant from ancient land distribution to modern settings such as cloud resource allocation and inheritance disputes. Divisible goods can be split using established protocols, but indivisible goods pose much harder challenges. A central fairness notion is envy-freeness (EF), requiring that no agent prefers another’s bundle. For indivisible goods though, exact EF is often impossible. Thus, relaxed notions have been proposed, such as envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX). This thesis focuses on models of fair division with additional constraints on the allocation space. Motivated by real-world scenarios, we study a model where all agents need to be allocated bundles of equal size. To address this, flip-based analogs of fairness notions have been introduced, such as EFF1 and EFFX, where the envy can be eliminated by swapping one (or respectively, any) item between bundles.These notions fit naturally in this constrained setting, but their properties remain unexplored. This thesis contributes in two directions. First, it surveys discrete fair division both with and without constraints (cardinality, connectivity, budget, matroids). Second, it develops new results on flip-based fairness, analyzing existence, approximation guarantees, and the performance of well-known procedures such as Envy Cycle Elimination. Finally, it explores trade-offs between fairness and efficiency.