Abstract
We study the problem of allocating indivisible goods among agents. When randomization is allowed, it is possible to achieve compelling fairness guarantees such as envy-freeness (Foley, 1967), which states that no agent should (in expectation) prefer any other agent's allocation to her own. For instance, we can simply allocate each good, independently of the other goods, to an agent chosen uniformly at random. However, while this scheme is fair ex-ante, it may produce outcomes that are very unfair ex-post, such as by chance assigning all the goods to a single agent. On the other hand, in the absence of randomization, some amount of ex-post unfairness is unavoidable. Nevertheless, it is possible to guarantee relaxations of envy-freeness that bound the maximum level of envy. One popular relaxation is envy-freeness up to one good (Lipton et al., 2004; Budish, 2011), which requires that the envy of any agent toward another agent can be removed by the elimination of at most one good from the envied agent's bundle.
Our goal in this work is to develop algorithms for constructing randomized allocations that are simultaneously exactly fair ex-ante and approximately fair ex-post. We focus on additive valuations, under which an agent's value for the union of two disjoint sets of resources is the sum of her values for the two sets. The key question we address is whether there always exists an ex-ante envy-free (EF) distribution over deterministic allocations that each satisfy envy-freeness up to one good (EF1). We settle this positively by designing a novel algorithm, Recursive Probabilistic Serial, which is an adaptation of the classic Probabilistic Serial (PS) algorithm of Bogomolnaia and Moulin (2001) that inherits much of the desirable behavior of PS (in particular, ex-ante envy-freeness), while also allowing a simple and natural decomposition over EF1 allocations. While a naive interpretation of our algorithm yields a distribution over a possibly-exponential number of deterministic allocations, we show that a support size polynomial in the number of agents and goods is sufficient, thus yielding an efficient variant of Recursive Probabilistic Serial.
In addition to ex-ante EF and ex-post EF1, one may want to achieve the economic efficiency notion of Pareto optimality, which states that it should be impossible to find an allocation that improves some agent's utility without reducing any other agent's. We show that it is impossible to achieve ex-ante Pareto optimality (that is, with respect to the randomized allocation) in conjunction with ex-ante EF and ex-post EF1. However, strong ex-ante guarantees --- in terms of both fairness and economic efficiency --- can be achieved if we are willing to compromise on the ex-post guarantee. In particular, we are able to achieve ex-ante group fairness (Conitzer et al., 2019), which generalizes both envy-freeness and Pareto optimality, in conjunction with two ex-post fairness properties that are incomparable but are both implied by EF1: proportionality up to one good or Prop1 (Conitzer et al, 2017) and envy-freeness up to one good more-and-less or $EF_1^1$ (Barman and Krishnamurthy, 2019). Our algorithm uses a rounding of the well-known Maximum Nash Welfare allocation, and by a novel characterization, we prove that this is the only allocation rule that can be used to achieve the desired properties.
For more details, we refer the reader to the full version of the paper (Freeman et al., 2020).
