ISyE Seminar Series: Nick Arnosti
"Greedy Policies for Stationary Dynamic Matching"
Nick Arnosti
Associate Professor at the Department of Industrial and Systems Engineering
University of Minnesota Twin Cities
About the Seminar:
We study a foundational model of dynamic matching market with abandonment. This model has been studied by Collina et al. (2020) and Aouad and Sarıtac (2022), and other papers have considered special cases. We compare the performance of greedy policies – which identify a set of “acceptable” matches up front, and perform these matches as soon as possible – to that of an omniscient benchmark which knows the full arrival and departure sequence.
We identify our greedy policy using a novel family of linear programs, which provide a lower bound on our policy’s performance in two settings of interest:
- All agents have the same departure rate.
- Bipartite matching. Agents on the same side of the market have the same departure rate.
We also show that the value of our linear program is at least 1/2 of the reward earned by the omniscient policy ( Propositions 2 & 3). Therefore, for both settings above, our greedy policy provably earns at least half of the omniscient benchmark (Theorem 1). This improves upon the bound of 1/8 from Collina et al. (2020). Our competitive ratio of 1/2 is the best possible: no online policy can provide a better guarantee (Theorem 2).
Numerical evidence suggests that our guarantee of 1/2 holds even when our departure rate conditions are not satisfied. We prove this for instances with two types (Theorem 3).
Related Paper:
"Greedy Policies for Stationary Dynamic Matching"
About the Speaker:
Nick Arnosti is an Assistant Professor at the Department of Industrial and Systems Engineering at the University of Minnesota. Previously, Arnosti was an Assistant Professor at Columbia Business School, where he taught the MBA core class Operations Management, as well as a PhD elective on Rationing Social Goods. He received a PhD in Operations Research from Stanford University in 2016 (advised by Ramesh Johari and Paul Milgrom). His research focuses on market design, with particular emphasis on giving away social goods such as affordable housing and public school seats. He has also studied the allocation of hunting licenses, hiking permits, and discounted tickets to events.
If you wish to be added to the ISyE Graduate Seminar Series emailing list, please email Event Coordinator Emily Rice at [email protected].