# Almost Envy-free Repeated Matching in Two-sided Markets

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Sep 2020.

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

- [Temporal Fairness in Multiwinner Voting](https://mlsanity.com/paper/2312.04417/) (2023)
- [Two-Sided Matching Meets Fair Division](https://mlsanity.com/paper/2107.07404/) (2021)
- [Resource Sharing Through Multi-Round Matchings](https://mlsanity.com/paper/2211.17199/) (2022)
- [Automating Food Drop: The Power of Two Choices for Dynamic and Fair Food Allocation](https://mlsanity.com/paper/2406.06363/) (2024)
- [Promoting Two-sided Fairness in Dynamic Vehicle Routing Problem](https://mlsanity.com/paper/2405.19184/) (2024)
- [Fairness in Repeated Matching: A Maximin Perspective](https://mlsanity.com/paper/2510.04624/) (2025)
- [Temporal Panel Selection in Ongoing Citizens' Assemblies](https://mlsanity.com/paper/2602.16194/) (2026)

## Abstract (arXiv)

A two-sided market consists of two sets of agents, each of whom have preferences over the other (Airbnb, Upwork, Lyft, Uber, etc.). We propose and analyze a repeated matching problem, where some set of matches occur on each time step, and our goal is to ensure fairness with respect to the cumulative allocations over an infinite time horizon. Our main result is a polynomial-time algorithm for additive, symmetric (vi(j) = vj(i)), and binary (vi(j) ∈ a,1) valuations that both (1) guarantees "envy-freeness up to a single match" (EF1) and (2) selects a maximum weight matching on each time step. Thus for this class of valuations, fairness can be achieved without sacrificing economic efficiency. This result holds even for "dynamic valuations", i.e., valuations that change over time. Although symmetry is a strong assumption, we show that this result cannot be extended to asymmetric binary valuations: (1) and (2) together are impossible even when valuations do not change over time, and for dynamic valuations, even (1) alone is impossible. To our knowledge, this is the first analysis of envy-freeness in a repeated matching setting.