Abstract
In bipartite matching problems, vertices on one side of a bipartite graph are paired with those on the other. In its offline variant, both sides of the graph are known a priori; in its online variant, one side of the graph is available offline, while vertices on the other arrive online and are irrevocably and immediately matched (or ignored) by an algorithm. Examples of such problems include matching workers to firms, advertisers to keywords, organs to patients, and riders to rideshare drivers. Much of the literature focuses on maximizing the total relevance---modeled via total weight---of the matching. However, in many real-world problems, it is also important to consider contributions of diversity: hiring a diverse pool of candidates, displaying a relevant but diverse set of ads, and so on.
In this talk, we model the promotion of diversity in matching markets via maximization of a submodular function over the set of matched edges. We present new results in a generalization of traditional offline matching, b-matching, where vertices have both lower and upper bounds on the number of adjacent matched edges. We also present new theoretical results in online submodular bipartite matching. Finally, we conclude with ongoing work that approaches the problem of hiring a diverse cohort of workers through the lens of combinatorial pure exploration (CPE) in the multiarmed bandit setting, and discuss an ongoing experiment in this space at a large research university.
This talk will cover joint work with Saba Ahmadi, Faez Ahmed, Samsara Counts, Jeff Foster, Mark Fuge, Samir Khuller, Zhi Lang, Nicholas Mattei, Karthik A. Sankararaman, Candice Schumann, Aravind Srinivasan, and Pan Xu.