Maximin Shares in Structured Fair Allocation

Abstract

The problem of fairly dividing a shared resource among members of a group—each with her own preferences—arises frequently. For example, consider a group of friends sharing a sushi platter. One friend may only want very specific pieces. Another could be indifferent to most pieces, but strongly detests any piece containing seaweed. Yet another friend could simply wish to receive a varied selection of pieces. The question then becomes: “How can the platter be shared among the friends, so that the division is considered fair by each of the friends?” In this dissertation we consider a variant of this fair division problem, in which the shared resource is a collection of indivisible items. In particular, we mainly focus on subvariants where additional structure is imposed through constraints on which combinations of items that can be given to the same person. For example, a person may be forbidden from receiving more items of a certain type than she can reasonably make use of. As fairness criteria, we consider variants of the maximin share (MMS) guarantee. This guarantee requires each person to receive a collection of items that are, in her opinion, no worse than what she could guarantee herself, if she had to partition the items into bundles and received among these bundles her least preferred one. Papers A to C consider variants of the fair division problem with hereditary constraints on which bundles are allowed. Under this type of constraints, if an agent is allowed to receive a certain bundle of items, then she is also allowed to receive any subset of this bundle. In the three papers, we study both specific types of hereditary constraints (papers A and B), as well hereditary constraints on a more general level (Paper C). For both cases, we show that there always exists allocations that satisfy the MMS guarantee within a constant-factor approximation. Additionally, we show that such allocations can for many hereditary constraints be found in polynomial time. Paper D considers a different type of constraint, in which the items are located on a graph. The edges of this graph indicate that items share spatial or temporal properties. Each agent is required to receive a bundle that induces a connected subgraph. In the paper, a novel local fairness criterion is introduced and studied. This fairness criterion makes use of the structure of the graph to induce a social network from any chosen allocation; If two persons receive a pair of items that are connected by an edge, then the persons are connected in the social network. The fairness criterion then requires that a pairwise variant of MMS is satisfied for any pair of persons adjacent in the social network. We show that this fairness criterion can always be satisfied by a constant factor approximation. For certain restricted cases, we show that such allocations can be found in polynomial time. Paper E examines the problem from a different direction. Instead of imposing additional structure by placing constraints on which bundles can be given to an agent, it instead considers the effects of restricting the number of items that are to be allocated. Specifically, we show that when the number of items is only slightly larger than the number of persons, then there is ample shared structure in the partitions used to determine each agent’s MMS. This shared structure is then used to shown that in this restricted case, there always exists an allocation that satisfies the MMS guarantee.