Tuesday, March 20, 2018. 12:00PM. NSH 1507.
John Dickerson -- Diversity in Matching Markets
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 Faez Ahmed, Samsara Counts, Jeff Foster, Mark Fuge, Karthik A. Sankararaman, Candice Schumann, Aravind Srinivasan, and Pan Xu.
Bio: John P Dickerson is an Assistant Professor of Computer Science at the University of Maryland. His research centers on solving practical economic problems using techniques from computer science, stochastic optimization, and machine learning. He has worked extensively on theoretical and empirical approaches to designing markets for organ allocation, dating, admissions, and computational advertising.