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...
Κύριος συγγραφέας: | |
---|---|
Άλλοι συγγραφείς: | |
Γλώσσα: | 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 |