Competitive Analysis for Online Fair Division under Multiple Fairness Notions
It provides optimal online algorithms and impossibility results for a broad class of fair division problems, resolving many open cases in the literature.
The paper studies online fair division of indivisible items, designing algorithms that achieve optimal competitive ratios for various fairness notions across goods/chores, normalized/non-normalized utilities, and identical/general utility functions.
We study the online fair division of indivisible items with additive utilities, where items arrive sequentially and must be irrevocably allocated upon arrival. Considering various fairness notions, we focus on designing online algorithms that produce fair or approximately fair allocations for any instance. We measure algorithm performance using the competitive ratio, defined as the worst-case ratio between the fairness guarantee achieved by the online algorithm and that of an optimal offline allocation with full knowledge of future arrivals. We examine a broad spectrum of models, including the allocation of goods or chores, normalized versus non-normalized utilities, and identical versus general utility functions. We address the majority of the unresolved cases by providing online algorithms or proving the limits of the competitive ratio achievable by online algorithms. In most cases, the algorithms are shown to be optimal.