Fair and Truthful Allocations under Leveled Valuations
Creators: name: Χριστοφορίδης, Βασίλειος Γεωργίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2024
Subjects: Δίκαιη ανάθεση πόρων
Αλγοριθμική Θεωρία Παιγνίων
Υπολογιστική Θεωρία Κοινωνικής Επιλογής
Fair Division
Algorithmic Game Theory
Computational Social Choice

description: Σκοπός της παρούσας διατριβής είναι η μελέτη του θεμελιώδους προβλήματος της δίκαιας ανάθεσης πόρων. Η σχετική θεωρία, γνωστή σήμερα ως Δίκαιες Αναθέσεις, συναντάται για πρώτη φορά την δεκαετία του ‘50 και αποκτά μεγάλη ερευνητική άνθιση έκτοτε. Επικεντρωνόμαστε στην περίπτωση των αδιαίρετων αγαθών, στην οποία τα αντικείμενα δεν μπορούν να χωριστούν σε επιμέρους κομμάτια. Στην παρούσα διπλωματική, μελετάμε το πρόβλημα της ανάθεσης αγαθών σε παίκτες με επίπεδες συναρτήσεις αποτίμησης (leveled valuation functions). Το συγκεκριμένο είδος συναρτήσεων, το οποίο έχει μελετηθεί προηγουμένως στη βιβλιογραφία της μικροοικονομίας και των δίκαιων αναθέσεων, καλύπτει μία απλή και διαισθητική οικονομική συμπεριφορά: ένα υποσύνολο αντικειμένων προτιμάται πάντα από ένα άλλο με μικρότερο πλήθος αντικειμένων, ανεξαρτήτως του ποια αντικείμενα περιλαμβάνονται στα υποσύνολα αυτά. Συνεπώς, μπορεί να ιδωθεί ως προτίμηση της ποσότητας έναντι της ποιότητας των αγαθών. Παρουσιάζουμε μια λεπτομερή ανάλυση για διάφορες υποκλάσεις των επίπεδων συναρτήσεων, εστιάζοντας σε δύο γνωστές έννοιες δικαιοσύνης: τις έννοιες EFX και MMS. Δίνουμε μια σειρά θεωρητικών αποτελεσμάτων που δείχνουν την ύπαρξη προσεγγιστικών λύσεων για το MMS για όλες τις γνωστές κλάσεις των επίπεδων υποπροσθετικών συναρτήσεων αποτίμησης (subadditive leveled valuation functions). Ακόμα, δείχνουμε πώς οι ιδέες μας μπορούν να χρησιμοποιηθούν πέρα από τον τομέα των επίπεδων συναρτήσεων για την έννοια του MMS. Στην περίπτωση του EFX δείχνουμε ένα θετικό αποτέλεσμα για γενικές μονότονες συναρτήσεις. Τέλος, μελετάμε τις παιγνιοθεωρητικές ιδιότητες του προβλήματος και δείχνουμε ότι ευρέως μελετημένοι μηχανισμοί της βιβλιογραφίας είναι φιλαλήθεις (truthful) και προσεγγιστικά δίκαιοι στην περίπτωση των επίπεδων συναρτήσεων.
description: We study the fundamental problem of allocating resources to a group of people in a fair manner. The associated theory, known today as Fair Division, originated in early works back in the 50’s and has flourished since then in economics, computer science, and artificial intelligence. We focus on the case of indivisible items, in which the resources to be allocated cannot be split or shared. In this thesis, we focus on the problem of fairly allocating indivisible goods among agents which are equipped with leveled valuation functions. Such preferences, that have been studied before in economics and fair division literature, capture a simple and intuitive economic behavior; larger bundles are always preferred to smaller ones (i.e. quantity over quality). We provide a fine-grained analysis for various subclasses of leveled valuations focusing on two extensively studied notions of fairness, (approximate) MMS and EFX. We provide a series of theoretical contributions; in particular, we present a general positive result, showing the existence of 2/3-MMS allocations under valuations that are both leveled and submodular. We also show how some of our ideas can be used beyond the class of leveled valuations; for the case of two submodular (not necessarily leveled) agents we show that there is always a 2/3-MMS allocation, complementing a recent previous impossibility result. Then, we switch to the case of subadditive and fractionally subadditive leveled agents, where we are able to show tight (lower and upper) bounds of 1/2 on the approximation factor of MMS. Next, we show the existence of exact EFX allocations under general leveled valuations via a simple protocol that in addition satisfies several natural economic properties. Lastly, we take a mechanism design approach and we show that some well-studied allocation protocols are both truthful and approximately fair under leveled valuations. We give positive results for all important subclasses of leveled valuations.