| Περίληψη: | 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.
|
|---|
