Approximately Fair Allocation of Indivisible Items with Random Valuations

In this work, we consider the problem of fairly allocating a set of indivisible items to agents, who have additive and random valuations for the bundles of items they receive. The valuations that each agent has for all items are independent and bounded, and their realizations are only revealed after allocating the items. The goal is to determine an allocation that minimizes, in expectation, the maximum envy that an agent has for the bundle assigned to each other, without knowing in advance the realization of the random valuations. We first show how to compute in polynomial time and deterministically an allocation that guarantees an expected maximum envy of at most O(wpln(n)m/n), where n is the number of agents, m is the number of items and w is the maximum valuation for each item. Furthermore, we show that the above bound cannot be improved, that is, there is an instance for which the expected maximum envy of any allocation is at least Ω(wpln(n)m/n). Finally, we resort to randomized algorithms that return (random) allocations satisfying further efficiency guarantees, such as ex-ante envy-freeness and ex-ante Pareto optimality. If we relax the constraint of ex-ante Pareto optimality, we provide an algorithm that still works without knowing the probability distributions of agent valuations.