Abstract
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 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. 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. The source code is made available at https://github.com/faezahmed/diverse_matching.
Introduction
In many real-world scenarios—such as assigning reviewers to academic papers, students to schools, or employees to project teams—the objective extends beyond simple utility maximization to include diversity. While "single-feature" diversity (e.g., ensuring nationality balance) is well-understood, humans are intersectional. Optimizing for multiple attributes simultaneously (e.g., gender, expertise, and seniority) introduces significant complexity.
This paper addresses the multi-attribute bipartite b-matching problem. We demonstrate that the jump from one diversity feature to two shifts the problem from polynomial-time solvable to NP-hard. Features are often correlated or constrained by capacity, making it difficult to improve diversity in one dimension without adversely affecting another.
Methodology: A Combinatorial Approach
To overcome the limitations of standard Mixed-Integer Quadratic Programming (MIQP) solvers, which often struggle with large-scale matching problems, we propose a novel combinatorial algorithm based on an auxiliary graph representation.
The core of the approach involves treating the matching problem as a flow network. We construct an auxiliary graph where edges represent the "cost"—in terms of lost utility or diversity—of reassigning an individual from one team to another.
The algorithm iteratively improves the matching by detecting and "canceling" negative cycles in this graph. A negative cycle indicates a sequence of local exchanges that increases the overall objective function. Critically, we prove that the absence of negative cycles in this auxiliary graph guarantees that the current matching is the global optimum.
Experimental Evaluation
The algorithm was evaluated using the UIUC multi-aspect review assignment dataset, comprising 73 papers and 189 reviewers with 25-dimensional expertise vectors. Gender labels were augmented to test multi-attribute capabilities.
Compared to the state-of-the-art Gurobi MIQP solver:
- Efficiency: For a subset of 13 papers, our algorithm was approximately 268x faster (14.8s vs. 3,979s).
- Scalability: On the full 73-paper set, Gurobi failed to converge within 4 hours, whereas our algorithm found the optimal solution in roughly 3 hours (11,040 seconds).
- Diversity Quality: Without the diversity objective, only 27.3% of teams were gender-balanced. With our algorithm, 100% of the papers received a balanced set of reviewers (two male, two female) while still maintaining high expertise matches.
Conclusion and Future Work
We have presented the first combinatorial algorithm for provably-optimal multi-attribute diverse matching. While the algorithm operates in pseudo-polynomial time, it significantly outperforms general-purpose solvers for this specific class of problems. Future research will explore online matching environments where participants arrive dynamically and the integration of explicit algorithmic fairness constraints alongside diversity objectives.
Summary updated