# Group-level Fairness Maximization in Online Bipartite Matching

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

## Key facts

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

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

- [Data-Driven Methods for Balancing Fairness and Efficiency in Ride-Pooling](https://mlsanity.com/paper/2110.03524/) (2021)
- [Fairness-aware Online Price Discrimination with Nonparametric Demand Models](https://mlsanity.com/paper/2111.08221/) (2021)
- [Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual](https://mlsanity.com/paper/2201.06021/) (2022)
- [Fairness Maximization among Offline Agents in Online-Matching Markets](https://mlsanity.com/paper/2109.08934/) (2021)
- [Fairer LP-based Online Allocation via Analytic Center](https://mlsanity.com/paper/2110.14621/) (2021)
- [Fair Secretaries with Unfair Predictions](https://mlsanity.com/paper/2411.09854/) (2024)
- [Network Revenue Management with Demand Learning and Fair Resource-Consumption Balancing](https://mlsanity.com/paper/2207.11159/) (2022)
- [Algorithmic Challenges in Ensuring Fairness at the Time of Decision](https://mlsanity.com/paper/2103.09287/) (2021)
- [Equity Promotion in Online Resource Allocation](https://mlsanity.com/paper/2112.04169/) (2021)
- [Equity Promotion in Public Transportation](https://mlsanity.com/paper/2211.14531/) (2022)
- [Discrimination-free Insurance Pricing with Privatized Sensitive Attributes](https://mlsanity.com/paper/2504.11775/) (2025)
- [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)
- [Long-term Fairness in Ride-Hailing Platform](https://mlsanity.com/paper/2407.17839/) (2024)
- [Learning Fair Demand Models](https://mlsanity.com/paper/2606.06830/) (2026)

## Abstract (arXiv)

We consider the allocation of limited resources to heterogeneous customers who arrive in an online fashion. We would like to allocate the resources "fairly", so that no group of customers is marginalized in terms of their overall service rate. We study whether this is possible to do so in an online fashion, and if so, what a good online allocation policy is. We model this problem using online bipartite matching under stationary arrivals, a fundamental model in the literature typically studied under the objective of maximizing the total number of customers served. We instead study the objective of maximizing the minimum service rate across all groups, and propose two notions of fairness: long-run and short-run. For these fairness objectives, we analyze how competitive online algorithms can be, in comparison to offline algorithms which know the sequence of demands in advance. For long-run fairness, we propose two online heuristics (Sampling and Pooling) which establish asymptotic optimality in different regimes (no specialized supplies, no rare demand types, or imbalanced supply/demand). By contrast, outside all of these regimes, we show that the competitive ratio of online algorithms is between 0.632 and 0.732. For short-run fairness, we show for complete bipartite graphs that the competitive ratio of online algorithms is between 0.863 and 0.942; we also derive a probabilistic rejection algorithm which is asymptotically optimal in the total demand. Depending on the overall scarcity of resources, either our Sampling or Pooling heuristics could be desirable. The most difficult situation for online allocation occurs when the total supply is just enough to serve the total demand. We simulate our algorithms on a public ride-hailing dataset, which both demonstrates the efficacy of our heuristics and validates our managerial insights.