Dynamic Fair Division with Partial Information

We consider the fundamental problem of fairly and efficiently allocating T indivisible items among n agents with additive preferences. Items become available over a sequence of rounds, and every item must be allocated immediately and irrevocably before the next one arrives. Previous work shows that when the agents’ valuations for the items are drawn from known distributions, it is possible (under mild assumptions) to find allocations that are envy-free with high probability and Pareto efficient ex post. However, this requires that agents accurately report their values to the algorithm, which rarely happens in practice. We study a partial-information setting, where true item values are hidden from the algorithm and it is only possible to elicit ordinal information in the form of a ranking or pairwise comparison relative to prior items. When values are drawn from i.i.d. distributions, or correlated distributions consisting of a shared common value for each item with i.i.d. noise, we give an algorithm that is envy-free and ( 1 − ϵ ) -welfare-maximizing with high probability. We provide similar guarantees (envy-freeness and a constant approximation to welfare with high probability) even with minimally expressive queries that ask for a comparison with a single previous item. For independent but nonidentical agents, we obtain envy-freeness and a constant approximation to Pareto efficiency with high probability. Our results are asymptotically tight. A computational study shows that envy-freeness and efficiency can be achieved on practical time-horizons.