Fair division of indivisible goods

• Κύριος συγγραφέας: Ιωαννίδης, Σταύρος
• Άλλοι συγγραφείς: Ioannidis, Stavros
• Γλώσσα: English
• Έκδοση: 2020
• Θέματα: 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.