Fair Division Online: No Algorithm Guarantees Envy-Freeness Without Budget Slack
New proof shows online fair division is impossible without structure, but learning predictions can help.
A team of computer scientists (Cohen, Teh, Goldberg, Wooldridge) tackles the challenging problem of online fair division with budget constraints. In their model, goods arrive one by one and must be assigned irrevocably to agents or a charity, with fairness evaluated only against budget-feasible subsets of each recipient's bundle. The paper first delivers a sobering impossibility result: without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. This sets a hard theoretical lower bound on what is achievable in dynamic allocation settings like cloud resource provisioning or ad slot scheduling.
The authors then identify a structural condition—bounded density spread—that restores meaningful guarantees. Under this condition, they derive approximation algorithms for arbitrary item sizes and show that with common valuations and sufficiently small goods, the guarantees reach an optimal deterministic frontier. They also study resource augmentation, allowing slightly larger budgets than the fairness benchmark, and characterize the resulting improvement. Finally, and most relevant for practical AI systems, they develop a learning-augmented framework based on predicting joint value-size types. They prove that this approach yields consistency under perfect predictions and robustness to errors, while separate predictions of value and size marginals are insufficient to recover strong fairness guarantees—an insight that could guide future allocation systems that learn from past data.
- No deterministic online algorithm can guarantee any fixed approximation to envy-freeness under budget constraints, even in symmetric settings.
- Bounded density spread restores feasibility, enabling approximation algorithms with optimal deterministic frontiers for small goods.
- Learning-augmented predictions of joint value-size types improve fairness guarantees; separate value and size predictions do not suffice.
Why It Matters
Theoretical foundation for allocating scarce resources online (cloud, ads) with fairness, guiding future algorithmic systems using learned predictions.