# Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 58 references that are in the map.
- First posted on arXiv 16 Jan 2022.

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

- [FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms](https://mlsanity.com/paper/2002.10764/) (2020)
- [Balancing the Tradeoff between Profit and Fairness in Rideshare Platforms During High-Demand Hours](https://mlsanity.com/paper/1912.08388/) (2019)
- [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)
- [Matchings with Group Fairness Constraints: Online and Offline Algorithms](https://mlsanity.com/paper/2105.09522/) (2021)
- [Online Stochastic Matching: New Algorithms and Bounds](https://mlsanity.com/paper/1606.06395/) (2016)
- [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)
- [A Framework for Fairness in Two-Sided Marketplaces](https://mlsanity.com/paper/2006.12756/) (2020)
- [Fairness Maximization among Offline Agents in Online-Matching Markets](https://mlsanity.com/paper/2109.08934/) (2021)
- [Subgroup Fairness in Two-Sided Markets](https://mlsanity.com/paper/2106.02702/) (2021)
- [Improved Approximation Algorithms for Stochastic Matching](https://mlsanity.com/paper/1505.01439/) (2015)

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

- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Fairness in Matching under Uncertainty](https://mlsanity.com/paper/2302.03810/) (2023)
- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)
- [Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All](https://mlsanity.com/paper/2208.09951/) (2022)
- [Design a Win-Win Strategy That Is Fair to Both Service Providers and Tasks When Rejection Is Not an Option](https://mlsanity.com/paper/2407.00032/) (2024)
- [Generalizing Fair Top-k Selection: An Integrative Approach](https://mlsanity.com/paper/2603.04689/) (2026)
- [Fair Online Resource Allocation](https://mlsanity.com/paper/2606.18679/) (2026)

## Abstract (arXiv)

Online bipartite-matching platforms are ubiquitous and find applications in important areas such as crowdsourcing and ridesharing. In the most general form, the platform consists of three entities: two sides to be matched and a platform operator that decides the matching. The design of algorithms for such platforms has traditionally focused on the operator's (expected) profit. Since fairness has become an important consideration that was ignored in the existing algorithms a collection of online matching algorithms have been developed that give a fair treatment guarantee for one side of the market at the expense of a drop in the operator's profit. In this paper, we generalize the existing work to offer fair treatment guarantees to both sides of the market simultaneously, at a calculated worst case drop to operator profit. We consider group and individual Rawlsian fairness criteria. Moreover, our algorithms have theoretical guarantees and have adjustable parameters that can be tuned as desired to balance the trade-off between the utilities of the three sides. We also derive hardness results that give clear upper bounds over the performance of any algorithm.