# Trading-off price for data quality to achieve fair online allocation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 59 references that are in the map.
- First posted on arXiv 23 Jun 2023.

## Builds on (most cited first, 30 of 34)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Fairness in Reinforcement Learning](https://mlsanity.com/paper/1611.03071/) (2016)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [On the Privacy Risks of Algorithmic Fairness](https://mlsanity.com/paper/2011.03731/) (2020)
- [Differentially Private Fair Learning](https://mlsanity.com/paper/1812.02696/) (2018)
- [Multisided Fairness for Recommendation](https://mlsanity.com/paper/1707.00093/) (2017)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [Differential Privacy and Fairness in Decisions and Learning Tasks: A Survey](https://mlsanity.com/paper/2202.08187/) (2022)
- [Towards Fair Classifiers Without Sensitive Attributes: Exploring Biases in Related Features](https://mlsanity.com/paper/2104.14537/) (2021)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Noise-tolerant fair classification](https://mlsanity.com/paper/1901.10837/) (2019)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Selection Problems in the Presence of Implicit Bias](https://mlsanity.com/paper/1801.03533/) (2018)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Simple and Fast Algorithm for Binary Integer and Online Linear Programming](https://mlsanity.com/paper/2003.02513/) (2020)
- [Regularized Online Allocation Problems: Fairness and Beyond](https://mlsanity.com/paper/2007.00514/) (2020)
- [On Fair Selection in the Presence of Implicit Variance](https://mlsanity.com/paper/2006.13699/) (2020)
- [Bounding and Approximating Intersectional Fairness through Marginal Fairness](https://mlsanity.com/paper/2206.05828/) (2022)
- [Optimal Data Acquisition for Statistical Estimation](https://mlsanity.com/paper/1711.01295/) (2017)
- [A Nearest Neighbor Characterization of Lebesgue Points in Metric Measure Spaces](https://mlsanity.com/paper/2007.03937/) (2020)
- [Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity](https://mlsanity.com/paper/1811.05100/) (2018)
- [Dynamic Placement in Refugee Resettlement](https://mlsanity.com/paper/2105.14388/) (2021)
- [The Parity Ray Regularizer for Pacing in Auction Markets](https://mlsanity.com/paper/2106.09503/) (2021)

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

- [FairJob: A Real-World Dataset for Fairness in Online Systems](https://mlsanity.com/paper/2407.03059/) (2024)
- [Fairness-Regularized Online Optimization with Switching Costs](https://mlsanity.com/paper/2512.11131/) (2025)

## Abstract (arXiv)

We consider the problem of online allocation subject to a long-term fairness penalty. Contrary to existing works, however, we do not assume that the decision-maker observes the protected attributes -- which is often unrealistic in practice. Instead they can purchase data that help estimate them from sources of different quality; and hence reduce the fairness penalty at some cost. We model this problem as a multi-armed bandit problem where each arm corresponds to the choice of a data source, coupled with the online allocation problem. We propose an algorithm that jointly solves both problems and show that it has a regret bounded by O(√T). A key difficulty is that the rewards received by selecting a source are correlated by the fairness penalty, which leads to a need for randomization (despite a stochastic setting). Our algorithm takes into account contextual information available before the source selection, and can adapt to many different fairness notions. We also show that in some instances, the estimates used can be learned on the fly.