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 (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.
Introduction
Matching problems are fundamental to modern resource allocation, from assigning reviewers to research papers to matching organ donors with patients. Traditionally, these systems prioritize "efficiency," such as maximizing the total expertise of a reviewer panel. However, in real-world applications, diversity is equally critical. A panel should ideally reflect a balance of gender, nationality, and background to ensure a broad range of perspectives.
In their research, Ahmadi et al. investigate the computational complexity of building diverse teams when multiple attributes are involved. While matching for a single diverse attribute (such as country) is computationally tractable, the authors prove that balancing multiple features simultaneously (e.g., gender and nationality) is NP-hard. This complexity poses a significant hurdle for applications like conference organizing, where diversity is rarely one-dimensional.
Methodology: Optimal Diverse Matching via Cycle Detection
To address the NP-hardness of multi-attribute matching, the authors propose a novel combinatorial algorithm based on Negative-Cycle-Detection.
The Objective Function
The authors define a utility function that subtracts a "concentration index" (inspired by the Herfindahl index used in economics) from the total matching weight. This index penalizes teams that are too homogeneous, thereby incentivizing diversity across all specified attributes.
Auxiliary Graph and Local Exchanges
The matching problem is represented as an auxiliary graph where "switches" represent teams and "ports" represent specific combinations of features. The key insight is that any change to a matching can be viewed as a "local exchange"—moving a worker from Team A to Team B, another from B to C, and so on. In the auxiliary graph, these exchanges form cycles.
Starting from an initial valid matching, the algorithm searches for "negative cycles"—paths of exchanges that improve the overall diversity and efficiency score. By employing a high-performance variant of the Bellman-Ford algorithm (the Goldberg-Radzik variant), the method iteratively updates the matching until no further improvements are possible, guaranteeing a globally optimal solution.
Experimental Results
The algorithm was evaluated using the UIUC multi-aspect review assignment evaluation dataset, which includes 73 research papers and 189 prospective reviewers. Reviewers were categorized into expertise clusters, and the dataset was augmented with synthetic gender attributes to test multi-attribute capabilities.
Performance and Scalability
The authors compared their algorithm against a state-of-the-art Mixed-Integer Quadratic Programming (MIQP) solver (Gurobi). For the full dataset of 73 papers, the MIQP solver failed to converge within a 4-hour time limit. In contrast, the proposed combinatorial algorithm found the optimal solution in approximately 3 hours (11,040 seconds).
Diversity Gains
When the diversity objective was active, the system successfully balanced gender and expertise. Without the diversity objective, only 27.3% of teams were gender-balanced; with it, 100% of the papers received a balanced reviewer panel (two male, two female) without sacrificing expertise.
Conclusion
This work establishes the NP-hardness of multi-attribute diverse matching and introduces the first pseudo-polynomial time algorithm that guarantees an optimal solution. By leveraging the underlying structure of the matching problem through an auxiliary graph, the authors provide a specialized alternative to standard industrial solvers. Future research directions include extending this framework to online matching scenarios and integrating specific individual fairness constraints alongside diversity goals.
Summary updated