Online Fair Division with Additional Information
This work addresses the challenge of fair resource allocation in dynamic environments, offering incremental improvements by leveraging structured information to enhance fairness in online settings.
The paper tackles the problem of fairly allocating indivisible goods in an online setting where goods arrive sequentially, showing that without information on future goods, achieving approximate fairness is impossible, but with additional information like normalized valuations or frequency predictions, algorithms can achieve stronger fairness guarantees, such as matching offline guarantees for share-based notions.
We study the problem of fairly allocating indivisible goods to agents in an online setting, where goods arrive sequentially and must be allocated irrevocably to agents. Focusing on the popular fairness notions of envy-freeness, proportionality, and maximin share fairness (and their approximate variants), we ask how the availability of information on future goods influences the existence and approximability of fair allocations. In the absence of any such information, we establish strong impossibility results, demonstrating the inherent difficulty of achieving even approximate fairness guarantees. In contrast, we demonstrate that knowledge of additional information -- such as aggregate of each agent's total valuations (equivalently, normalized valuations) or the multiset of future goods values (frequency predictions) -- would enable the design of fairer online algorithms. Given normalization information, we propose an algorithm that achieves stronger fairness guarantees than previously known results. Given frequency predictions, we introduce a meta-algorithm that leverages frequency predictions to match the best-known offline guarantees for a broad class of ''share-based'' fairness notions. Our complementary impossibility results in each setting underscore both the limitations imposed by uncertainty about future goods and the potential of leveraging structured information to achieve fairer outcomes in online fair division.