4/13/23 | 4:15pm | E25-111

Yash Kanoria

Associate Professor
Columbia

Abstract: Motivated by online matching markets and network revenue management (NRM) problems with many types (e.g., fulfillment optimization), we study dynamic spatial matching (DSM) in which supply and demand live in d dimensional space and need to be matched with each other dynamically. If demand and supply have the same spatial distribution, greedy matching suffices, and achieves average match distance of the same order as the distance to the nearest neighbor, *except* for the case of d=1 and both supply and demand arriving dynamically over time. If demand and supply have different spatial distributions, the matching constraint has bite and greedy matching fails. We introduce a unifying and practical algorithmic principle for NRM and DSM dubbed SOAR: Simulate, Optimize, Assign, Repeat, which repeatedly simulates the future to enable good matching decisions. Simulating one sample path at each stage already enables SOAR to produce near optimal regret for the majority of NRM models in the literature, and for DSM with non-atomic demand and supply distributions. For particularly challenging NRM and DSM models, SOAR with multiple simulated sample paths at each stage achieves near optimal regret.

Papers:
Paper 1
Paper 2 (with O. Besbes and Akshit Kumar)
Paper 3 (with Y. Chen, A. Kumar, and W. Zhang)

Bio: Yash Kanoria is an Associate Professor of Business in the Decision, Risk and Operations division at Columbia Business School, specializing in the design and optimization of marketplaces, especially matching markets. Previously, he obtained a BTech in Electrical Engineering from IIT Bombay in 2007, a PhD from Stanford in 2012, and spent a year at Microsoft Research New England during 2012-13 as a Schramm postdoctoral fellow. He received a National Science Foundation CAREER Award in 2017, and was a finalist for the 2018 Wagner Prize in Operations Research practice for the design of a large-scale centralized seat allocation process for engineering colleges in India. He is currently on sabbatical at Amazon, optimizing the supply chain.