# On preserving non-discrimination when combining expert advice

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2018.

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

- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Evaluating Fairness of Machine Learning Models Under Uncertain and Incomplete Information](https://mlsanity.com/paper/2102.08410/) (2021)
- [Towards Return Parity in Markov Decision Processes](https://mlsanity.com/paper/2111.10476/) (2021)
- [A Unified Approach to Fair Online Learning via Blackwell Approachability](https://mlsanity.com/paper/2106.12242/) (2021)
- [Fairness with Continuous Optimal Transport](https://mlsanity.com/paper/2101.02084/) (2021)
- [Group Meritocratic Fairness in Linear Contextual Bandits](https://mlsanity.com/paper/2206.03150/) (2022)
- [Fairer LP-based Online Allocation via Analytic Center](https://mlsanity.com/paper/2110.14621/) (2021)
- [Fair Online Bilateral Trade](https://mlsanity.com/paper/2405.13919/) (2024)
- [Fairness-Aware Naive Bayes Classifier for Data with Multiple Sensitive Features](https://mlsanity.com/paper/2202.11499/) (2022)
- [Online Fair Revenue Maximizing Cake Division with Non-Contiguous Pieces in Adversarial Bandits](https://mlsanity.com/paper/2111.14387/) (2021)
- [Best-Case Lower Bounds in Online Learning](https://mlsanity.com/paper/2106.12688/) (2021)
- [Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria](https://mlsanity.com/paper/2609.22757/) (2026)

## Abstract (arXiv)

We study the interplay between sequential decision making and avoiding discrimination against protected groups, when examples arrive online and do not follow distributional assumptions. We consider the most basic extension of classical online learning: "Given a class of predictors that are individually non-discriminatory with respect to a particular metric, how can we combine them to perform as well as the best predictor, while preserving non-discrimination?" Surprisingly we show that this task is unachievable for the prevalent notion of "equalized odds" that requires equal false negative rates and equal false positive rates across groups. On the positive side, for another notion of non-discrimination, "equalized error rates", we show that running separate instances of the classical multiplicative weights algorithm for each group achieves this guarantee. Interestingly, even for this notion, we show that algorithms with stronger performance guarantees than multiplicative weights cannot preserve non-discrimination.