# Fairer LP-based Online Allocation via Analytic Center

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 57 references that are in the map.
- First posted on arXiv 27 Oct 2021.

## Builds on (most cited first, 25 of 25)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment](https://mlsanity.com/paper/1610.08452/) (2016)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Fairness in Reinforcement Learning](https://mlsanity.com/paper/1611.03071/) (2016)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Calibrated Fairness in Bandits](https://mlsanity.com/paper/1707.01875/) (2017)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Fair Contextual Multi-Armed Bandits: Theory and Experiments](https://mlsanity.com/paper/1912.08055/) (2019)
- [Equal Opportunity in Online Classification with Partial Feedback](https://mlsanity.com/paper/1902.02242/) (2019)
- [Individual Fairness in Hindsight](https://mlsanity.com/paper/1812.04069/) (2018)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits](https://mlsanity.com/paper/1504.06937/) (2015)
- [Fair Algorithms for Learning in Allocation Problems](https://mlsanity.com/paper/1808.10549/) (2018)
- [Fair Dynamic Rationing](https://mlsanity.com/paper/2102.01240/) (2021)
- [A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management](https://mlsanity.com/paper/1802.06192/) (2018)
- [Primal Beats Dual on Online Packing LPs in the Random-Order Model](https://mlsanity.com/paper/1311.2578/) (2013)
- [Online Allocation and Pricing: Constant Regret via Bellman Inequalities](https://mlsanity.com/paper/1906.06361/) (2019)
- [Fairness and Utilization in Allocating Resources with Uncertain Demand](https://mlsanity.com/paper/1906.09050/) (2019)
- [Group-level Fairness Maximization in Online Bipartite Matching](https://mlsanity.com/paper/2011.13908/) (2020)
- [The Bayesian Prophet: A Low-Regret Framework for Online Decision Making](https://mlsanity.com/paper/1901.05028/) (2019)
- [On preserving non-discrimination when combining expert advice](https://mlsanity.com/paper/1810.11829/) (2018)
- [Sequential Fair Allocation of Limited Resources under Stochastic Demands](https://mlsanity.com/paper/2011.14382/) (2020)
- [Advance Service Reservations with Heterogeneous Customers](https://mlsanity.com/paper/1805.05554/) (2018)

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

- [Honor Among Bandits: No-Regret Learning for Online Fair Division](https://mlsanity.com/paper/2407.01795/) (2024)
- [Utility Fairness in Contextual Dynamic Pricing with Demand Learning](https://mlsanity.com/paper/2311.16528/) (2023)
- [Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies](https://mlsanity.com/paper/2408.12845/) (2024)
- [Network Revenue Management with Demand Learning and Fair Resource-Consumption Balancing](https://mlsanity.com/paper/2207.11159/) (2022)
- [Improved Regret Bounds for Online Fair Division with Bandit Learning](https://mlsanity.com/paper/2501.07022/) (2025)

## Abstract (arXiv)

In this paper, we consider an online resource allocation problem where a decision maker accepts or rejects incoming customer requests irrevocably in order to maximize expected reward given limited resources. At each time, a new order/customer/bid is revealed with a request of some resource(s) and a reward. We consider a stochastic setting where all the orders are i.i.d. sampled from an unknown distribution. Such formulation arises from many classic applications such as the canonical (quantity-based) network revenue management problem and the Adwords problem. While the literature on the topic mainly focuses on regret minimization, our paper considers the textitfairness aspect of the problem. On a high level, we define the fairness in a way that a fair online algorithm should treat similar agents/customers similarly, and the decision made for similar agents/customers should be consistent over time. To achieve this goal, we define the fair offline solution as the analytic center of the offline optimal solution set, and introduce textitcumulative unfairness as the cumulative deviation from the online solutions to the fair offline solution over time. We propose a fair algorithm based on an interior-point LP solver and a mechanism that dynamically detects unfair resource spending. Our algorithm achieves cumulative unfairness on the scale of order O(log(T)), while maintains the regret to be bounded without dependency on T. In addition, compared to the literature, our result is produced under less restrictive assumptions on the degeneracy of the underlying linear program.