A classical and long-standing problem in computer science and economics, with widespread application in health-care, education, advertising, and general resource allocation is the bipartite matching problem. In bipartite matching, items on one side of a market are matched to items on the other. For example, allocating conference papers to reviewers requires allocating multiple reviewers to each paper and each paper should be matched to three or more reviewers
When forming teams to review designs, we often allocate reviewers based on their expertise. However, having multiple reviewers who are all from the same department or are similar to each other may not be desirable. To address this, we proposed a new algorithm for diverse matching, using a quadratic programming based approach to solve a super-modular minimization problem that balances diversity and quality of the solution. We demonstrated the efficacy of our methods on three real-world datasets and showed that, in practice, encouraging diverse teams does not sacrifice performance.
How does one form diverse teams when people have multiple attributes?
While the MIQP approach showed promise in forming diverse teams, MIQPs do not provide any guarantee to reach the optimal solution and the initial approach was limited to cases when we want to form teams with respect to a single attribute. So address these issues, we proposed a new algorithm, which guarantees finding the optimal matching, while balancing for multiple attributes.
How does one form diverse teams when people arrive sequentially?
We also proposed a method for the online version of this problem, where we do not know the availability of people beforehand. In such cases, we need to decide at the moment whether to assign a newly arrived person to a team or not. The online matching algorithms are relevant to crowd markets, reviewer assignment for journal papers as well as domains where discrete items arrive sequentially.