An Algorithm for Multi-Attribute Diverse Matching
This addresses the challenge of balancing diversity and efficiency in resource allocation for applications like healthcare and advertising, representing an incremental advance over prior work on single-feature diversity.
The paper tackles the problem of maximizing diversity across multiple features in bipartite b-matching, proving it is NP-hard and developing a combinatorial algorithm that finds provably-optimal solutions in pseudo-polynomial time, with demonstrated computational efficiency in a reviewer assignment application.
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 general resource allocation. Traditionally, the primary goal of such models is to maximize a linear function of the constituent matches (e.g., linear social welfare maximization) subject 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 over the matching. Basic versions of this problem are solvable in polynomial time. In this work, we prove that the problem of simultaneously maximizing diversity along several features (e.g., country of citizenship, gender, skills) is NP-hard. To address this problem, we develop the first combinatorial algorithm that constructs provably-optimal diverse b-matchings in pseudo-polynomial time. We also provide a Mixed-Integer Quadratic formulation for the same problem and show that our method guarantees optimal solutions and takes less computation time for a reviewer assignment application.