# Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 64 references that are in the map.
- First posted on arXiv 21 Aug 2022.

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

- [Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings](https://mlsanity.com/paper/1607.06520/) (2016)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [Fairness in Ranking under Uncertainty](https://mlsanity.com/paper/2107.06720/) (2021)
- [Maxmin-Fair Ranking: Individual Fairness under Group-Fairness Constraints](https://mlsanity.com/paper/2106.08652/) (2021)
- [Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation](https://mlsanity.com/paper/2005.14122/) (2020)
- [Fair-by-design matching](https://mlsanity.com/paper/1802.02562/) (2018)
- [A Technique for Obtaining True Approximations for k-Center with Covering Constraints](https://mlsanity.com/paper/2007.03946/) (2020)
- [Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings](https://mlsanity.com/paper/2202.03237/) (2022)
- [Democratic Fair Allocation of Indivisible Goods](https://mlsanity.com/paper/1709.02564/) (2017)
- [A Lottery Model for Center-type Problems With Outliers](https://mlsanity.com/paper/1710.00287/) (2017)
- [Best-of-Both-Worlds Fair-Share Allocations](https://mlsanity.com/paper/2102.04909/) (2021)
- [Matchings with Group Fairness Constraints: Online and Offline Algorithms](https://mlsanity.com/paper/2105.09522/) (2021)
- [Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual](https://mlsanity.com/paper/2201.06021/) (2022)
- [Incremental Fairness in Two-Sided Market Platforms: On Smoothly Updating Recommendations](https://mlsanity.com/paper/1909.10005/) (2019)
- [Simultaneously Achieving Ex-ante and Ex-post Fairness](https://mlsanity.com/paper/2004.02554/) (2020)
- [Efficient, Fair, and Incentive-Compatible Healthcare Rationing](https://mlsanity.com/paper/2102.04384/) (2021)
- [Fair Disaster Containment via Graph-Cut Problems](https://mlsanity.com/paper/2106.05424/) (2021)
- [Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties](https://mlsanity.com/paper/2105.03093/) (2021)

## Abstract (arXiv)

We study the probabilistic assignment of items to platforms that satisfies both group and individual fairness constraints. Each item belongs to specific groups and has a preference ordering over platforms. Each platform enforces group fairness by limiting the number of items per group that can be assigned to it. There could be multiple optimal solutions that satisfy the group fairness constraints, but this alone ignores item preferences. Our approach explores a `best of both worlds fairness' solution to get a randomized matching, which is ex-ante individually fair and ex-post group-fair. Thus, we seek a `probabilistic individually fair' distribution over `group-fair' matchings where each item has a `high' probability of matching to one of its top choices. This distribution is also ex-ante group-fair. Users can customize fairness constraints to suit their requirements. Our first result is a polynomial-time algorithm that computes a distribution over `group-fair' matchings such that the individual fairness constraints are approximately satisfied and the expected size of a matching is close to OPT. We empirically test this on real-world datasets. We present two additional polynomial-time bi-criteria approximation algorithms that users can choose from to balance group fairness and individual fairness trade-offs. For disjoint groups, we provide an exact polynomial-time algorithm adaptable to additional lower `group fairness' bounds. Extending our model, we encompass `maxmin group fairness,' amplifying underrepresented groups, and `mindom group fairness,' reducing the representation of dominant groups.'