Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/13532
Title: Fair division of indivisible goods
Other Titles: Προβλήματα δίκαιης κατανομής μη διαιρέσιμων αγαθών
Authors: Ιωαννίδης, Σταύρος
Keywords: Fair division
Computational social choice
Algorithmic game theory
Keywords (translated): Δίκαιη μοιρασιά αντικειμένων
Abstract: In this thesis we study fair division problems. Fair division problems are categorized generally as resource allocation problems where we have to divide items to players or agents satisfying specific fairness notions. The task depends on many parameters like the nature of the items we allocate to agents which may be either divisible or indivisible, the functions we use to model the agents preferences, whether a central algorithm runs for the problem or the agents themselves converge to a solution namely whether the problem is centralized or distributed. Here we study only the case where the items are indivisible and hence, they must be allocated as a whole to some agent. This thesis is organized in three Chapters. Chapter 1 is about the classic setup of a fair division problem of indivisible goods. We present the classic model of the problem, we give definitions about the functions that model agents’ preferences, we discuss ways to measure system efficiency inheriting notions from welfare economics, we present some of the most commonly used fairness notions like proportionality and envy-freeness and finally, we present some recent theorems and results on these notions. Chapter 2 deals with distributed fair division. Here the agents negotiate rational deals on exchanging goods that benefit them. We present the model of distributed fair division and mark the key differences from Chapter 1. We give a summary of results from some key papers and close with some fairness results and negotiations in general. The final Chapter, Chapter 3 deals with results that we discovered while working on this thesis concerning fair division problems using subsidy. We study the minimum subsidy required for an allocation to be envy-freeable and conclude with an approximation algorithm and a hardness result.
Abstract (translated): Στη διπλωματική αυτή ασχολούμαστε με το πρόβλημα της δίκαιης κατανομής ενός συνόλου μη διαιρέσιμων αντικειμένων σε ένα σύνολο παικτών. Ο κάθε παίκτης έχει μια προτίμηση για κάθε αντικείμενο βάση των οποίων ο στόχος μας είναι να κατασκευάσουμε αλγορίθμους που θα κατανέμουν τα αντικείμενα και θα μας δίνουν ως αποτέλεσμα μια δίκαιη κατανομή. Αρκετές φορές δεν μπορούμε να πετύχουμε απόλυτη δικαιοσύνη στην κατανομή και μελετάμε προσεγγίσεις αυτής της έννοιας. Μελετάμε ακόμη μοντέλα δίκαιης μοιρασιάς όπου επιτρέπεται η χρήση χρημάτων από κάποια πηγή προς τους παίκτες. Υπάρχουν 2 βασικά μοντέλα που επιτρέπουν τη χρήση χρημάτων προς τους παίκτες τα οποία παρουσιάζουμε και αναλύουμε στην εργασία. Εκτός από το κλασικό πρόβλημα της ανάθεσης αντικειμένων στους παίκτες μελετάμε και το πρόβλημα των διαπραγματεύσεων μεταξύ των παικτών πάνω στα αντικείμενα που πρέπει να μοιραστούν. Σε αυτά τα προβλήματα οι παίκτες συνάπτουν συμφωνίες μεταξύ τους για τα αντικείμενα που τους ενδιαφέρουν με σκοπό να καταλήξουν σε μια δίκαιη μοιρασιά. Παρουσιάζουμε το πρόβλημα των διαπραγματεύσεων σε κάποιο συγκεκριμένο μοντέλο με χρήση χρημάτων. Τέλος σε μια ξεχωριστή ενότητα παρουσιάζουμε δικά μας αποτελέσματα και συνεισφορές στο πεδίο της δίκαιης κατανομής μη διαιρέσιμων αγαθών. Μελετήσαμε το πρόβλημα των ελαχίστων πληρωμών που πρέπει να γίνουν ώστε μια κατανομή αγαθών να είναι δίκαιη καθώς και την ύπαρξη μηχανισμών για την κατανομή των αντικειμένων χωρίς στρατηγικό ενδιαφέρον για τους παίκτες.
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΜΔΕ)



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.