# Fairness in Repeated Matching: A Maximin Perspective

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 81 references that are in the map.
- First posted on arXiv 6 Oct 2025.

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

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [Online Fair Division: analysing a Food Bank problem](https://mlsanity.com/paper/1502.07571/) (2015)
- [Proportional Aggregation of Preferences for Sequential Decision Making](https://mlsanity.com/paper/2306.14858/) (2023)
- [Temporal Fairness in Multiwinner Voting](https://mlsanity.com/paper/2312.04417/) (2023)
- [Maximum Nash Welfare and Other Stories About EFX](https://mlsanity.com/paper/2001.09838/) (2020)
- [Fair Division with Binary Valuations: One Rule to Rule Them All](https://mlsanity.com/paper/2007.06073/) (2020)
- [Repeated Fair Allocation of Indivisible Items](https://mlsanity.com/paper/2304.01644/) (2023)
- [Temporal Elections: Welfare, Strategyproofness, and Proportionality](https://mlsanity.com/paper/2408.13637/) (2024)
- [Temporal Fair Division of Indivisible Items](https://mlsanity.com/paper/2410.14593/) (2024)
- [Multiwinner Temporal Voting with Aversion to Change](https://mlsanity.com/paper/2408.11017/) (2024)
- [Equitable Allocations of Indivisible Goods](https://mlsanity.com/paper/1905.10656/) (2019)
- [Better Collective Decisions via Uncertainty Reduction](https://mlsanity.com/paper/2207.04983/) (2022)
- [Strengthening Proportionality in Temporal Voting](https://mlsanity.com/paper/2505.22513/) (2025)
- [Repeatedly Matching Items to Agents Fairly and Efficiently](https://mlsanity.com/paper/2207.01589/) (2022)
- [Almost Envy-free Repeated Matching in Two-sided Markets](https://mlsanity.com/paper/2009.09336/) (2020)
- [On Maximum Weighted Nash Welfare for Binary Valuations](https://mlsanity.com/paper/2204.03803/) (2022)
- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Not in My Backyard! Temporal Voting Over Public Chores](https://mlsanity.com/paper/2508.08810/) (2025)
- [Envy-Freeness in House Allocation Problems](https://mlsanity.com/paper/1905.00468/) (2019)
- [Uniform Welfare Guarantees Under Identical Subadditive Valuations](https://mlsanity.com/paper/2005.00504/) (2020)
- [Multi-agent Online Scheduling: MMS Allocations for Indivisible Items](https://mlsanity.com/paper/2304.13405/) (2023)
- [Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division](https://mlsanity.com/paper/1901.09527/) (2019)
- [Fair Allocation of Two Types of Chores](https://mlsanity.com/paper/2211.00879/) (2022)
- [Stochastic Bandits for Egalitarian Assignment](https://mlsanity.com/paper/2410.05856/) (2024)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [Envy-free Matchings with Lower Quotas](https://mlsanity.com/paper/1704.04888/) (2017)
- [Fair Division through Information Withholding](https://mlsanity.com/paper/1907.02583/) (2019)
- [Online Algorithms for the Santa Claus Problem](https://mlsanity.com/paper/2210.07333/) (2022)
- [On the Hardness of Fair Allocation under Ternary Valuations](https://mlsanity.com/paper/2403.00943/) (2024)
- [Combinatorial Algorithm for Restricted Max-Min Fair Allocation](https://mlsanity.com/paper/1409.0607/) (2014)

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

- [The Price of Proportional Representation in Temporal Voting](https://mlsanity.com/paper/2605.11157/) (2026)
- [Online Fair Division with Budget Constraints](https://mlsanity.com/paper/2607.23310/) (2026)

## Abstract (arXiv)

We study a sequential decision-making model where a set of items is repeatedly matched to the same set of agents over multiple rounds. The objective is to determine a sequence of matchings that either maximizes the utility of the least advantaged agent at the end of all rounds (optimal) or at the end of every individual round (anytime optimal). We investigate the computational challenges associated with finding (anytime) optimal outcomes and demonstrate that these problems are generally computationally intractable. However, we provide approximation algorithms, fixed-parameter tractable algorithms, and identify several special cases whereby the problem(s) can be solved efficiently. Along the way, we also establish characterizations of Pareto-optimal/maximum matchings, which may be of independent interest to works in matching theory and house allocation.