Algorithms for Optimal Diverse Matching

Bipartite b -matching, where agents on one side of a market are matched to one or more agents or items on the other, is a classical model that is used in myriad application areas such as healthcare, advertising, education, and genera l resource allocation. Traditionally, the primary goal of su ch models is to maximize a linear function of the constituent matches (e.g., linear social welfare maximization) subjec t to some constraints. Recent work has studied a new goal of balancing whole-match diversity and economic efficiency, where the objective is instead a monotone submodular function ove r the matching. These more general models are largely NPhard. In this work, we develop a combinatorial algorithm tha t constructs provably-optimal diverse b -matchings in pseudo-polynomial time. Then, we show how to extend our algorithm to solve new variations of the diverse b -matching problem. We then compare directly, on real-world datasets, against the state-of-the-art, quadratic-programming-based appr oach to solving diverse b -matching problems and show that our method outperforms it in both speed and (anytime) solution quality.