# Online Learning Demands in Max-min Fairness

arXiv: https://arxiv.org/abs/2012.08648 · HTML: https://mlsanity.com/paper/2012.08648/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Dec 2020.

## Built on by (most cited first, 6 of 6)

- [Scalable Verification of GNN-based Job Schedulers](https://mlsanity.com/paper/2203.03153/) (2022)
- [Fairness-aware Online Price Discrimination with Nonparametric Demand Models](https://mlsanity.com/paper/2111.08221/) (2021)
- [Network Revenue Management with Demand Learning and Fair Resource-Consumption Balancing](https://mlsanity.com/paper/2207.11159/) (2022)
- [Learning Competitive Equilibria in Exchange Economies with Bandit Feedback](https://mlsanity.com/paper/2106.06616/) (2021)
- [Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning](https://mlsanity.com/paper/2407.04898/) (2024)
- [Fair PCA, One Component at a Time](https://mlsanity.com/paper/2503.21563/) (2025)

## Abstract (arXiv)

We describe mechanisms for the allocation of a scarce resource among multiple users in a way that is efficient, fair, and strategy-proof, but when users do not know their resource requirements. The mechanism is repeated for multiple rounds and a user's requirements can change on each round. At the end of each round, users provide feedback about the allocation they received, enabling the mechanism to learn user preferences over time. Such situations are common in the shared usage of a compute cluster among many users in an organisation, where all teams may not precisely know the amount of resources needed to execute their jobs. By understating their requirements, users will receive less than they need and consequently not achieve their goals. By overstating them, they may siphon away precious resources that could be useful to others in the organisation. We formalise this task of online learning in fair division via notions of efficiency, fairness, and strategy-proofness applicable to this setting, and study this problem under three types of feedback: when the users' observations are deterministic, when they are stochastic and follow a parametric model, and when they are stochastic and nonparametric. We derive mechanisms inspired by the classical max-min fairness procedure that achieve these requisites, and quantify the extent to which they are achieved via asymptotic rates. We corroborate these insights with an experimental evaluation on synthetic problems and a web-serving task.