# Past-Discounting is Key for Learning Markovian Fairness with Long Horizons

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 29 references that are in the map.
- First posted on arXiv 1 Apr 2025.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Learning Fair Policies in Multiobjective (Deep) Reinforcement Learning with Average and Discounted Rewards](https://mlsanity.com/paper/2008.07773/) (2020)
- [Learning Fairness in Multi-Agent Systems](https://mlsanity.com/paper/1910.14472/) (2019)
- [Learning Fair Policies in Decentralized Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2012.09421/) (2020)
- [Neural Approximate Dynamic Programming for On-Demand Ride-Pooling](https://mlsanity.com/paper/1911.08842/) (2019)
- [Online Fair Division: analysing a Food Bank problem](https://mlsanity.com/paper/1502.07571/) (2015)
- [Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve](https://mlsanity.com/paper/2105.05308/) (2021)
- [Remembering to Be Fair: Non-Markovian Fairness in Sequential Decision Making](https://mlsanity.com/paper/2312.04772/) (2023)
- [Using Simple Incentives to Improve Two-Sided Fairness in Ridesharing Systems](https://mlsanity.com/paper/2303.14332/) (2023)
- [DECAF: Learning to be Fair in Multi-agent Resource Allocation](https://mlsanity.com/paper/2502.04281/) (2025)

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

- [Temporal Fair Division in Multi-Agent Systems: From Precise Alternation Metrics to Scalable Coordination Proxies](https://mlsanity.com/paper/2605.14879/) (2026)

## Abstract (arXiv)

Fairness is an important consideration for dynamic resource allocation in multi-agent systems. Many existing methods treat fairness as a one-shot problem without considering temporal dynamics, which misses the nuances of accumulating inequalities over time. Recent approaches overcome this limitation by tracking allocations over time, assuming perfect recall of all past utilities. While the former neglects long-term equity, the latter introduces a critical challenge: the augmented state space required to track cumulative utilities grows unboundedly with time, hindering the scalability and convergence of learning algorithms. Motivated by behavioral insights that human fairness judgments discount distant events, we introduce a framework for temporal fairness that incorporates past-discounting into the learning problem. This approach offers a principled interpolation between instantaneous and perfect-recall fairness. Our central contribution is a past-discounted framework for memory tracking and a theoretical analysis of fairness memories, showing past-discounting guarantees a bounded, horizon-independent state space, a property that we prove perfect-recall methods lack. This result unlocks the ability to learn fair policies tractably over arbitrarily long horizons. We formalize this framework, demonstrate its necessity with experiments showing that perfect recall fails where past-discounting succeeds, and provide a clear path toward building scalable and equitable resource allocation systems.