Κατανομή αγαθών σε πολυγραφήματα με περιορισμένο φθόνο

Η διπλωματική μελετά το πρόβλημα της «δίκαιης» κατανομής αγαθών σε πράκτορες. Η μελέτη του προβλήματος ξεκίνησε στα τέλη της δεκαετίας του 1940 για αγαθά που μπορούν να διαχωριστούν με το πρόβλημα «cake cutting». Υπάρχουν πολλές έννοιες δίκαιου διαμοιρασμού αγαθών όταν αναφερόμαστε στον τομέα της Δίκαιης Κατανομής (Fair Division). Μία έννοια είναι οι κατανομές χωρίς φθόνο (envy-free allocations), όπου κανείς δεν ζηλεύει ό,τι έχει κατανεμηθεί σε οποιονδήποτε άλλο πράκτορα. Η απουσία φθόνου έχει μελετηθεί εκτενώς σε περιβάλλοντα με πόρους που μπορούν να διαχωριστούν. Η διπλωματική επικεντρώνεται σε διαμοιρασμούς αγαθών που δεν μπορούν να διαχωριστούν, όπου η απουσία φθόνου δεν μπορεί να εγγυηθεί. Αντίθετα, εστιάζουμε γύρω από ένα κριτήριο δικαιοσύνης που προσεγγίζει τις κατανομές χωρίς φθόνο: τους διαμοιρασμούς envy-free up to any good (EFX), δηλαδή, κανένας πράκτορας δεν ζηλεύει κανένα γνήσιο υποσύνολο των αγαθών που δίνονται σε οποιονδήποτε άλλο πράκτορα. Η ύπαρξη ή μη των διαμοιρασμών EFX αποτελεί ένα σημαντικό ανοικτό πρόβλημα στη Δίκαιη Κατανομή, και υπάρχουν μόνο θετικά αποτελέσματα για ειδικές συνθήκες. Οι Christodoulou et al. 2023 εισήγαγαν μία συνθήκη με περιορισμό στις αποτιμήσεις των πρακτόρων σύμφωνα με μια δομή γραφήματος: οι κορυφές αντιστοιχούν σε πράκτορες και οι ακμές σε αγαθά, και κάθε κορυφή/πράκτορας έχει μηδενική αξία (ή αλλιώς είναι αδιάφορος) για τις ακμές/αγαθά που δεν είναι γειτονικές με αυτήν. Η ύπαρξη των κατανομών EFX έχει αποδειχθεί για γραφήματα όταν οι πράκτορες έχουν γενικές μονότονες αποτιμήσεις από τους Christodoulou et al. 2023 και για πολυγραφήματα για περιορισμένες προσθετικές αποτιμήσεις από τους Kaviani et al. 2024. Στην παρούσα διατριβή, δείχνουμε ότι οι κατανομές EFX υπάρχουν πάντα σε πολυγραφήματα και για γενικές μονότονες αποτιμήσεις αν ισχύει τουλάχιστον μία από τις παρακάτω τρεις συνθήκες: είτε (α) το πολυγράφημα είναι διμερές, είτε (β) κάθε πράκτορας έχει το πολύ ⌈n/ 4⌉ − 1 γείτονες, όπου n είναι ο συνολικός αριθμός των πρακτόρων, είτε (γ) ο συντομότερος κύκλος με μη παράλληλες ακμές έχει μήκος τουλάχιστον 6.