Date/Time
Date(s) - August 25, 2023
10:40 am - 11:30 am
Location
Weil Hall 406
Categories No Categories
Alejandro Toriello
Date : Friday, August 25, 2023
Mode : In-Person
Affiliation: Georgia Tech
Bio: Visit Page
Title: Batching and Greedy Policies: How Good Are They in Dynamic Matching?
Abstract: We study a dynamic non-bipartite stochastic matching problem, where nodes appear following type-specific independent distributions and wait in the system for a given sojourn time. This problem is motivated by applications in ride-sharing and freight transportation marketplaces, and is related to other on-demand marketplaces. We study the asymptotic properties of two widely used policies, batching and greedy, by analyzing a single-pair case and then converting to the general counterpart using a fluid relaxation and randomization. We show that the batching policy is asymptotically optimal with respect to the sojourn time; similarly, while a straightforward greedy policy may not be optimal, a greedy policy with randomized modifications is asymptotically optimal. Perhaps more practically relevant, both policies converge exponentially fast to approximate optimality. We also extend our model to an impatient setting in which each unmatched node leaves at the end of each period with a type-dependent probability. We show that the results for the two policies still hold under different assumptions about the nodes’ patience; roughly speaking, the batching policy requires more patient nodes than the greedy policy to remain optimal. We present a computational study simulating freight transportation and ride-sharing marketplaces to assess the empirical effectiveness of the policies. Our results suggest that platforms can achieve near-optimal performance by using simple greedy or batching policies, with only a reasonably small maximum waiting time guarantee, and even in the presence of potentially impatient nodes. Joint work with PhD student Myungeun Eom.
Speaker Bio: Alejandro Toriello is a Professor of Industrial and Systems Engineering at Georgia Tech, where he also obtained his BS (2003) and PhD (2010). His research interests include supply chains and logistics, particularly problems motivated by e-commerce, platforms and the “last mile”, and mathematical optimization, especially discrete and/or dynamic problems with applications in cloud computing, online advertisement and resource allocation. Toriello is the 2023 President of the INFORMS Transportation Science and Logistics Society and an editorial board member for Transportation Science and Transportation Research Part B. He is a recipient of the National Science Foundation’s CAREER award and was a 2019 participant of the NAE Frontiers of Engineering Symposium.