Fairness-Efficiency Tradeoffs in Dynamic Fair Division

A set of T indivisible goods has to be allocated to a set of n agents with additive utilities, in a way that is fair and efficient. A standard fairness concept is envy-freeness, which requires that each agent prefers her own allocation over the allocation of any other agent. Even though envy is clearly unavoidable in this context - consider the case of a single indivisible good and two agents - providing approximately envy-free solutions is possible [3, 6]. Specifically, an allocation is envy-free up to one item (EF1) if for every pair of agents i and j, any envy i has for j can be eliminated by removing at most one good from j's bundle. Recently, Caragiannis et al. [3] show that the allocation that maximizes the product of the agents' utilities (with ties broken based on the number of agents with positive utility) is EF1 and Pareto efficient. The majority of the literature to date has focused on the case where the items are available to the algorithm upfront. In many situations of interest, however, items arrive online. A paradigmatic example is that of food banks [1, 5]. Food banks across the world receive food donations they must allocate; these donations are often perishable, and thus allocation decisions must be made quickly, and donations are typically leftovers, leading to uncertainty about items that will arrive in the future. Benadè et al. [2] study this problem, but focus only on fairness. They show that there exists a deterministic algorithm with vanishing envy, that is, the maximum pairwise envy (after all T items have been allocated) is sublinear in T, when the value vit of agent i for the t-th item is normalized to be in [0, 1]. Specifically, the envy is guaranteed to be at most O(√p T logT /n), and this guarantee is tight up to polylogarithmic factors. The same guarantee can also be achieved by the simple randomized algorithm that allocates each item to a uniformly random agent. These results hold even against an adaptive adversary that selects the value vit after seeing the allocation of the first t - 1 items. On the other hand, if we focus only on efficiency, our task is much easier. For example, we could simply allocate each item to the agent with the highest value. But, and this brings us to our interest here, the question remains: How should we make allocation decisions online in a way that is fair to the donation recipients, but also as efficient as possible?