Special Seminar in CMS and HSS
Pengyu Qian is a PhD student in the Decision, Risk and Operations division at Graduate School of Business, Columbia University where he is advised by Yash Kanoria. He received B.S. in Mathematics from Peking University in 2015. His research studies networked marketplaces with an emphasis on online decision-making, using tools from applied probability and modern optimization. He is interested in foundational theoretical models motivated by problems in revenue management and pricing, and matching markets. His research emphasizes algorithms and mechanisms that not only have good theoretical guarantees, but also are simple, robust, and hence practical for real-world systems.
Modern, technologically-enabled markets are disrupting many industry sectors, including transportation, lodging, healthcare and others. There remain major challenges in optimizing these marketplaces, as these systems are highly complex, marked by high-dimensional state space, a large number of interacting self-interested agents, and imperfect demand predictions. In this talk, I will describe my contribution to the dynamic control and mechanism aspects of these systems. The talk has two parts:
(i) Oblivious dynamic resource allocation.
For many applications, such as shared transportation, real-world demand is hard to predict and volatile. Motivated by this, we introduce a novel and rich family of Mirror Backpressure (MBP) dynamic resource allocation policies. The MBP policies are simple and practical, and crucially do not need any estimate of the demand arrival rates (these rates are permitted to vary slowly in time), in contrast to existing methods. MBP is inspired by the mirror descent algorithm for optimization and the backpressure policy for network control. Under mild conditions, we propose MBP policies that are provably near optimal, relative to the optimal policy that knows the demand arrival rates.
(ii) Price discovery and efficiency in waiting lists.
Waiting lists allocate items by offering agents a choice among items with associated waiting times. These waiting times serve as prices that are determined endogenously and adjust according to the stochastic arrivals and departures of agents. We study the allocative efficiency under such dynamically adjusting prices by drawing a connection between this price adjustment process and the stochastic gradient descent optimization algorithm. We show that the loss due to price fluctuations is bounded by the granularity of price changes. Additional conditions allow us to identify markets where the loss is close to the bound or exponentially small.