# Procedural Fairness in Multi-Agent Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 15 Jan 2026.

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

- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [Multi-objective Bandits: Optimizing the Generalized Gini Index](https://mlsanity.com/paper/1706.04933/) (2017)
- [Fair Allocation of Indivisible Public Goods](https://mlsanity.com/paper/1805.03164/) (2018)
- [Fair Public Decision Making](https://mlsanity.com/paper/1611.04034/) (2016)
- [The Core of the Participatory Budgeting Problem](https://mlsanity.com/paper/1610.03474/) (2016)
- [Pareto Regret Analyses in Multi-objective Multi-armed Bandit](https://mlsanity.com/paper/2212.00884/) (2022)
- [Eliciting Single-Peaked Preferences Using Comparison Queries](https://mlsanity.com/paper/1401.3449/) (2014)
- [An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret](https://mlsanity.com/paper/2209.11817/) (2022)
- [Equitable Allocations of Indivisible Goods](https://mlsanity.com/paper/1905.10656/) (2019)
- [No-Regret Learning for Fair Multi-Agent Social Welfare Optimization](https://mlsanity.com/paper/2405.20678/) (2024)
- [Honor Among Bandits: No-Regret Learning for Online Fair Division](https://mlsanity.com/paper/2407.01795/) (2024)
- [Funding Public Projects: A Case for the Nash Product Rule](https://mlsanity.com/paper/2005.07997/) (2020)
- [Improved Regret Bounds for Online Fair Division with Bandit Learning](https://mlsanity.com/paper/2501.07022/) (2025)
- [Fair Lotteries for Participatory Budgeting](https://mlsanity.com/paper/2404.05198/) (2024)

## Abstract (arXiv)

In the context of multi-agent multi-armed bandits (MA-MAB), fairness is often reduced to outcomes: maximizing welfare, reducing inequality, or balancing utilities. However, evidence in psychology, economics, and Rawlsian theory suggests that fairness is also about process and who gets a say in the decisions being made. We introduce procedural fairness as equal voice and formalize it for MA-MABs as equal representation within a policy over arms, using a core-stable Nash welfare objective based on representation rather than utility. Empirical results confirm that fairness notions based on optimizing for outcomes sacrifice equal voice and representation, while the sacrifice in outcome-based objectives (like equality and utilitarianism) is minimal under procedurally fair policies. We further prove that different fairness notions prioritize fundamentally different and incompatible values, highlighting that fairness requires explicit normative choices. This paper argues that procedural legitimacy deserves greater focus as a fairness objective and provides a framework for putting procedural fairness into practice.