# Diverse Weighted Bipartite b-Matching

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2017.

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

- [Multiple Heads are Better than One: Few-shot Font Generation with Multiple Localized Experts](https://mlsanity.com/paper/2104.00887/) (2021)
- [Turbo: Informativity-Driven Acceleration Plug-In for Vision-Language Large Models](https://mlsanity.com/paper/2407.11717/) (2024)
- [Turbo: Informativity-Driven Acceleration Plug-In for Vision-Language Models](https://mlsanity.com/paper/2312.07408/) (2023)
- [Subgroup Fairness in Two-Sided Markets](https://mlsanity.com/paper/2106.02702/) (2021)
- [Robust Allocations with Diversity Constraints](https://mlsanity.com/paper/2109.15015/) (2021)
- [Ranking with Slot Constraints](https://mlsanity.com/paper/2310.17870/) (2023)

## Abstract (arXiv)

Bipartite matching, where agents on one side of a market are matched to agents or items on the other, is a classical problem in computer science and economics, with widespread application in healthcare, education, advertising, and general resource allocation. A practitioner's goal is typically to maximize a matching market's economic efficiency, possibly subject to some fairness requirements that promote equal access to resources. A natural balancing act exists between fairness and efficiency in matching markets, and has been the subject of much research. In this paper, we study a complementary goal---balancing diversity and efficiency---in a generalization of bipartite matching where agents on one side of the market can be matched to sets of agents on the other. Adapting a classical definition of the diversity of a set, we propose a quadratic programming-based approach to solving a supermodular minimization problem that balances diversity and total weight of the solution. We also provide a scalable greedy algorithm with theoretical performance bounds. We then define the price of diversity, a measure of the efficiency loss due to enforcing diversity, and give a worst-case theoretical bound. Finally, we demonstrate the efficacy of our methods on three real-world datasets, and show that the price of diversity is not bad in practice.