Fair division of indivisible goods

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...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Κύριος συγγραφέας: Ιωαννίδης, Σταύρος
Άλλοι συγγραφείς: Ioannidis, Stavros
Γλώσσα:English
Έκδοση: 2020
Θέματα:
Διαθέσιμο Online:http://hdl.handle.net/10889/13532
id nemertes-10889-13532
record_format dspace
spelling nemertes-10889-135322022-09-06T05:13:10Z Fair division of indivisible goods Προβλήματα δίκαιης κατανομής μη διαιρέσιμων αγαθών Ιωαννίδης, Σταύρος Ioannidis, Stavros Fair division Computational social choice Algorithmic game theory Δίκαιη μοιρασιά αντικειμένων 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. Στη διπλωματική αυτή ασχολούμαστε με το πρόβλημα της δίκαιης κατανομής ενός συνόλου μη διαιρέσιμων αντικειμένων σε ένα σύνολο παικτών. Ο κάθε παίκτης έχει μια προτίμηση για κάθε αντικείμενο βάση των οποίων ο στόχος μας είναι να κατασκευάσουμε αλγορίθμους που θα κατανέμουν τα αντικείμενα και θα μας δίνουν ως αποτέλεσμα μια δίκαιη κατανομή. Αρκετές φορές δεν μπορούμε να πετύχουμε απόλυτη δικαιοσύνη στην κατανομή και μελετάμε προσεγγίσεις αυτής της έννοιας. Μελετάμε ακόμη μοντέλα δίκαιης μοιρασιάς όπου επιτρέπεται η χρήση χρημάτων από κάποια πηγή προς τους παίκτες. Υπάρχουν 2 βασικά μοντέλα που επιτρέπουν τη χρήση χρημάτων προς τους παίκτες τα οποία παρουσιάζουμε και αναλύουμε στην εργασία. Εκτός από το κλασικό πρόβλημα της ανάθεσης αντικειμένων στους παίκτες μελετάμε και το πρόβλημα των διαπραγματεύσεων μεταξύ των παικτών πάνω στα αντικείμενα που πρέπει να μοιραστούν. Σε αυτά τα προβλήματα οι παίκτες συνάπτουν συμφωνίες μεταξύ τους για τα αντικείμενα που τους ενδιαφέρουν με σκοπό να καταλήξουν σε μια δίκαιη μοιρασιά. Παρουσιάζουμε το πρόβλημα των διαπραγματεύσεων σε κάποιο συγκεκριμένο μοντέλο με χρήση χρημάτων. Τέλος σε μια ξεχωριστή ενότητα παρουσιάζουμε δικά μας αποτελέσματα και συνεισφορές στο πεδίο της δίκαιης κατανομής μη διαιρέσιμων αγαθών. Μελετήσαμε το πρόβλημα των ελαχίστων πληρωμών που πρέπει να γίνουν ώστε μια κατανομή αγαθών να είναι δίκαιη καθώς και την ύπαρξη μηχανισμών για την κατανομή των αντικειμένων χωρίς στρατηγικό ενδιαφέρον για τους παίκτες. 2020-07-12T12:54:58Z 2020-07-12T12:54:58Z 1994-05-28 http://hdl.handle.net/10889/13532 en application/pdf application/pdf
institution UPatras
collection Nemertes
language English
topic Fair division
Computational social choice
Algorithmic game theory
Δίκαιη μοιρασιά αντικειμένων
spellingShingle Fair division
Computational social choice
Algorithmic game theory
Δίκαιη μοιρασιά αντικειμένων
Ιωαννίδης, Σταύρος
Fair division of indivisible goods
description 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.
author2 Ioannidis, Stavros
author_facet Ioannidis, Stavros
Ιωαννίδης, Σταύρος
author Ιωαννίδης, Σταύρος
author_sort Ιωαννίδης, Σταύρος
title Fair division of indivisible goods
title_short Fair division of indivisible goods
title_full Fair division of indivisible goods
title_fullStr Fair division of indivisible goods
title_full_unstemmed Fair division of indivisible goods
title_sort fair division of indivisible goods
publishDate 2020
url http://hdl.handle.net/10889/13532
work_keys_str_mv AT iōannidēsstauros fairdivisionofindivisiblegoods
AT iōannidēsstauros problēmatadikaiēskatanomēsmēdiairesimōnagathōn
_version_ 1771297362777473024