# Long-Term Resource Allocation Fairness in Average Markov Decision Process (AMDP) Environment

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 39 references that are in the map.
- First posted on arXiv 14 Feb 2021.

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

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Efficient Exploration via State Marginal Matching](https://mlsanity.com/paper/1906.05274/) (2019)
- [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)
- [Beyond Parity: Fairness Objectives for Collaborative Filtering](https://mlsanity.com/paper/1705.08804/) (2017)
- [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)
- [How Do Fair Decisions Fare in Long-term Qualification?](https://mlsanity.com/paper/2010.11300/) (2020)
- [Algorithms for Fairness in Sequential Decision Making](https://mlsanity.com/paper/1901.08568/) (2019)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [Causal Modeling for Fairness in Dynamical Systems](https://mlsanity.com/paper/1909.09141/) (2019)
- [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019)
- [Fairness in Learning-Based Sequential Decision Algorithms: A Survey](https://mlsanity.com/paper/2001.04861/) (2020)
- [Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems](https://mlsanity.com/paper/1710.06100/) (2017)
- [Discrimination through optimization: How Facebook's ad delivery can lead to skewed outcomes](https://mlsanity.com/paper/1904.02095/) (2019)

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

- [On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes](https://mlsanity.com/paper/2403.06806/) (2024)
- [Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits](https://mlsanity.com/paper/2208.09254/) (2022)
- [Long-Term Fairness in Sequential Multi-Agent Selection with Positive Reinforcement](https://mlsanity.com/paper/2407.07350/) (2024)
- [Fair Resource Allocation in Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2411.09804/) (2024)
- [Price of Fairness in Short-Term and Long-Term Algorithmic Selections](https://mlsanity.com/paper/2605.06227/) (2026)
- [Fair Policy Optimization in Major-Minor Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2609.36174/) (2026)

## Abstract (arXiv)

Fairness has emerged as an important concern in automated decision-making in recent years, especially when these decisions affect human welfare. In this work, we study fairness in temporally extended decision-making settings, specifically those formulated as Markov Decision Processes (MDPs). Our proposed notion of fairness ensures that each state's long-term visitation frequency is at least a specified fraction. This quota-based notion of fairness is natural in many resource-allocation settings where the dynamics of a single resource being allocated is governed by an MDP and the distribution of the shared resource is captured by its state-visitation frequency. In an average-reward MDP (AMDP) setting, we formulate the problem as a bilinear saddle point program and, for a generative model, solve it using a Stochastic Mirror Descent (SMD) based algorithm. The proposed solution guarantees a simultaneous approximation on the expected average-reward and fairness requirement. We give sample complexity bounds for the proposed algorithm and validate our theoretical results with experiments on simulated data.