Diverse Weighted Bipartite b-Matching
This work addresses the trade-off between diversity and efficiency in matching markets, which is relevant for applications like healthcare and advertising, but it is incremental as it builds on classical bipartite matching with a focus on diversity.
The paper tackles the problem of balancing diversity and efficiency in bipartite b-matching, where agents on one side can match to sets on the other, by proposing a quadratic programming approach and a scalable greedy algorithm with theoretical bounds, and demonstrates on real-world datasets that the efficiency loss due to diversity enforcement is not severe in practice.
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.