Diversity in Matching Markets

on YouTube ↗50m

" summary

Introduces an online bipartite matching method that maximizes a monotone submodular objective via the multilinear extension and two simple online policies: a sampled-probability MMP algorithm (losing a 1−1/e factor) and a contention-resolution based policy with a different worst-case loss. Tests include synthetic budgets (1–15 matches) where greedy sometimes outperforms theory, and an IRB-approved University of Maryland grad‑admissions study using a square‑root coverage objective, a classifier and simulated Skype interviews (~6x cost) that increase gender/region coverage with almost no loss in utilitarian score.

AI-written summary · about

" chapters (23)

1. 0:00Intro
2. 0:43MATCHING MARKETS
3. 1:46MORE THAN LINEAR MAXIMIZATION
4. 3:46DIVERSITY VIA SUBMODULARITY
5. 4:56THIS TALK How can we balance diversity and efficiency in a principled way?
6. 9:22TWO-PHASE APPROACH Separate the algorithms into two phases: • Offline: obtain an upper bound on the offline optimal solution
7. 11:20OFFLINE PHASE Solve the following program maximize F(x)
8. 12:43ONLINE PHASE: TWO ALGORITHMS
9. 15:05COMPETITIVE RATIO
10. 17:15EARLY, EXPLORATORY EXPERIMENTS Run experiments on two common submodular functions Budget additive: • Maximize the sum of weights subject to a budget constraint B
11. 23:32OUR HIRING SETTING
12. 24:44INFORMATION GATHERING For the sake of this talk, assume we have two ways to gain information
13. 25:39KEY QUESTIONS How should a company allocate its limited interviewing resources to select the
14. 26:10HIGH-LEVEL APPROACH Model as a multi-armed bandit (MAB) problem in the Combinatorial Pure Exploration (CPE) setting
15. 28:23SWAP: STRONG-WEAK ARM PULL We present the strong-weak arm pull (SWAP) algorithm, which chooses which arms to pull, and when, based on input from an oracle that maximizes a monotone submodular objective function.
16. 28:55SWAP ALGORITHM
17. 30:49THEORETICAL RESULTS
18. 31:34AN ONGOING EXPERIMENT WITH BANDIT-BASED HIRING
19. 32:32FORMALLY PROMOTING DIVERSITY WITH SWAP In our experiments, we define diversity via an adaptation of the submodular
20. 36:45GRADUATE ADMISSIONS EXPERIMENT SETUP, CONTINUED Using our classifier, we ran simulations of SWAP diversifying for different sets of attributes
21. 37:29CAVEATS These are not policy recommendations!
22. 38:32GRADUATE ADMISSIONS EXPERIMENT RESULTS
23. 39:42EXTENSIONS

" related talks

• 29mClearing Matching Markets Efficiently: Informative Signals and Match RecommendationsItai Ashlagi · Societal Networks 2018
• 44mClearing Matching Markets Efficiently: Informative signals and Match RecommendationsPeng Shi · Platform Markets 2019
• 44mOnline Advertisements and Online AlgorithmsNikhil Devanur · Algorithmic Game Theory and Practice 2015
• 32mDynamic Matching ModelsAna Bušić · Societal Networks 2018
• 44mFacilitating the Search for Partners on Matching PlatformsYash Kanoria · Platform Markets 2019
• 36mThe Intractability of Hylland-Zeckhauser and its AftermathThorben Tröbst · Online and Matching-Based Market Design 2023
• 44mComputational Complexity of Matching in Ride SharingAmin Saberi · Platform Markets 2019
• 33mThe Rideshare Dispatch Problem (Aka Online Bipartite Matching with Supply Externalities)Sid Banerjee · Societal Networks 2018