Fair Division of Resources: From Indivisible Goods to Cakes
COM1 Level 2
SR9, COM1-02-09
Abstract:
In fair division, the goal is to divide a set of resources amongst several agents so that every agent receives what they perceive to be a fair share. This is often a challenging task. This thesis aims to provide more insights into fair division by studying theories, structures, algorithms, and complexities related to fair allocations in various settings, thereby revealing possibilities and impossibilities within the field.
In Part I, we study instances wherein the goods are indivisible. In the allocation of indivisible goods, the maximum Nash welfare rule has been characterized as the only rule within the class of additive welfarist rules that guarantees envy-freeness up to one good (EF1). We extend this characterization to the class of all welfarist rules. We then examine the structure of EF1 allocations by studying their reachability when agents are allowed to exchange goods sequentially. We investigate whether it is always possible to reach an EF1 allocation from another EF1 allocation via a sequence of exchanges such that every intermediate allocation is also EF1. In circumstances where this can be done, we investigate whether there is also an optimal sequence of such exchanges. Another problem that we study is the reformation of an unfair allocation into an EF1 allocation via such sequences. We investigate the complexity of deciding whether this reformation process is possible and the complexity of computing the number of exchanges needed whenever this is possible. Furthermore, we provide bounds to the number of exchanges required in the reformation process in the worst case.
In Part II, we study instances wherein the goods are divisible. We characterize the existence of a connected strongly-proportional allocation of an interval cake. We devise algorithms to determine this condition and to compute such an allocation if it exists. This problem is investigated along different axes, including whether the agents are hungry, whether the agents have different entitlements, and whether the agents are required to have a small positive value more than their entitlements. We then study the problem wherein the resource is in the form of a graph, also known as a graphical cake. Unlike for the interval cake, a connected envy-free allocation is not guaranteed to exist for a graphical cake. We devise efficient algorithms to compute connected allocations with low envy in a graphical cake. We also derive guarantees when each agent can receive more than one connected piece.