# Fairness Maximization among Offline Agents in Online-Matching Markets

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 59 references that are in the map.
- First posted on arXiv 18 Sep 2021.

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

- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Group-Fairness in Influence Maximization](https://mlsanity.com/paper/1903.00967/) (2019)
- [Fair Dynamic Rationing](https://mlsanity.com/paper/2102.01240/) (2021)
- [Balancing the Tradeoff between Profit and Fairness in Rideshare Platforms During High-Demand Hours](https://mlsanity.com/paper/1912.08388/) (2019)
- [Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve](https://mlsanity.com/paper/2105.05308/) (2021)
- [Allocation Problems in Ride-Sharing Platforms: Online Matching with Offline Reusable Resources](https://mlsanity.com/paper/1711.08345/) (2017)
- [Group-level Fairness Maximization in Online Bipartite Matching](https://mlsanity.com/paper/2011.13908/) (2020)
- [Fair-by-design matching](https://mlsanity.com/paper/1802.02562/) (2018)
- [An Experimental Study of Algorithms for Online Bipartite Matching](https://mlsanity.com/paper/1808.04863/) (2018)
- [The Price of Fairness for Indivisible Goods](https://mlsanity.com/paper/1905.04910/) (2019)
- [Matchings with Group Fairness Constraints: Online and Offline Algorithms](https://mlsanity.com/paper/2105.09522/) (2021)
- [Spatio-Temporal Pricing for Ridesharing Platforms](https://mlsanity.com/paper/1801.04015/) (2018)
- [Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity](https://mlsanity.com/paper/1811.05100/) (2018)
- [Trading the System Efficiency for the Income Equality of Drivers in Rideshare](https://mlsanity.com/paper/2012.06850/) (2020)
- [Matching Algorithms for Blood Donation](https://mlsanity.com/paper/2108.04862/) (2021)
- [Online Discrepancy Minimization for Stochastic Arrivals](https://mlsanity.com/paper/2007.10622/) (2020)
- [Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program](https://mlsanity.com/paper/2103.13024/) (2021)
- [Online Policies for Efficient Volunteer Crowdsourcing](https://mlsanity.com/paper/2002.08474/) (2020)
- [Multi-stage and Multi-customer Assortment Optimization with Inventory Constraints](https://mlsanity.com/paper/1908.09808/) (2019)
- [Improved Approximation Algorithms for Stochastic Matching](https://mlsanity.com/paper/1505.01439/) (2015)
- [Attenuate Locally, Win Globally: An Attenuation-based Framework for Online Stochastic Matching with Timeouts](https://mlsanity.com/paper/1804.08062/) (2018)

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

- [No-regret Algorithms for Fair Resource Allocation](https://mlsanity.com/paper/2303.06396/) (2023)
- [Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual](https://mlsanity.com/paper/2201.06021/) (2022)
- [Time Fairness in Online Knapsack Problems](https://mlsanity.com/paper/2305.13293/) (2023)
- [Interpolating Item and User Fairness in Multi-Sided Recommendations](https://mlsanity.com/paper/2306.10050/) (2023)
- [Equity Promotion in Online Resource Allocation](https://mlsanity.com/paper/2112.04169/) (2021)
- [Fair Allocation in Dynamic Mechanism Design](https://mlsanity.com/paper/2406.00147/) (2024)

## Abstract (arXiv)

Matching markets involve heterogeneous agents (typically from two parties) who are paired for mutual benefit. During the last decade, matching markets have emerged and grown rapidly through the medium of the Internet. They have evolved into a new format, called Online Matching Markets (OMMs), with examples ranging from crowdsourcing to online recommendations to ridesharing. There are two features distinguishing OMMs from traditional matching markets. One is the dynamic arrival of one side of the market: we refer to these as online agents while the rest are offline agents. Examples of online and offline agents include keywords (online) and sponsors (offline) in Google Advertising; workers (online) and tasks (offline) in Amazon Mechanical Turk (AMT); riders (online) and drivers (offline when restricted to a short time window) in ridesharing. The second distinguishing feature of OMMs is the real-time decision-making element. However, studies have shown that the algorithms making decisions in these OMMs leave disparities in the match rates of offline agents. For example, tasks in neighborhoods of low socioeconomic status rarely get matched to gig workers, and drivers of certain races/genders get discriminated against in matchmaking. In this paper, we propose online matching algorithms which optimize for either individual or group-level fairness among offline agents in OMMs. We present two linear-programming (LP) based sampling algorithms, which achieve online competitive ratios at least 0.725 for individual fairness maximization (IFM) and 0.719 for group fairness maximization (GFM), respectively. We conduct extensive numerical experiments and results show that our boosted version of sampling algorithms are not only conceptually easy to implement but also highly effective in practical instances of fairness-maximization-related models.