# Matchings with Group Fairness Constraints: Online and Offline Algorithms

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2021.

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

- [Measuring Fairness Under Unawareness of Sensitive Attributes: A Quantification-Based Approach](https://mlsanity.com/paper/2109.08549/) (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)
- [Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms](https://mlsanity.com/paper/2301.02053/) (2023)
- [PFAttack: Stealthy Attack Bypassing Group Fairness in Federated Learning](https://mlsanity.com/paper/2410.06509/) (2024)
- [Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All](https://mlsanity.com/paper/2208.09951/) (2022)
- [Anti-Matthew FL: Bridging the Performance Gap in Federated Learning to Counteract the Matthew Effect](https://mlsanity.com/paper/2309.16338/) (2023)
- [Online Housing Market](https://mlsanity.com/paper/2501.15916/) (2025)

## Abstract (arXiv)

We consider the problem of assigning items to platforms in the presence of group fairness constraints. In the input, each item belongs to certain categories, called classes in this paper. Each platform specifies the group fairness constraints through an upper bound on the number of items it can serve from each class. Additionally, each platform also has an upper bound on the total number of items it can serve. The goal is to assign items to platforms so as to maximize the number of items assigned while satisfying the upper bounds of each class. In some cases, there is a revenue associated with matching an item to a platform, then the goal is to maximize the revenue generated. This problem models several important real-world problems like ad-auctions, scheduling, resource allocations, school choice etc.We also show an interesting connection to computing a generalized maximum independent set on hypergraphs and ranking items under group fairness constraints. We show that if the classes are arbitrary, then the problem is NP-hard and has a strong inapproximability. We consider the problem in both online and offline settings under natural restrictions on the classes. Under these restrictions, the problem continues to remain NP-hard but admits approximation algorithms with small approximation factors. We also implement some of the algorithms. Our experiments show that the algorithms work well in practice both in terms of efficiency and the number of items that get assigned to some platform.