Dynamic Matching for On-Demand Service Platforms

在过去的几年里，像优步这样的双边按需服务平台的蓬勃发展对人们的日常生活产生了重大影响。连接供需的匹配机制是平台内决策过程的关键组成部分。例如，优步（Uber）和Lyft等拼车/叫车服务将司机与乘客匹配起来；Uber Eats和Amazon Flex等众包配送平台将快递员与订单匹配起来；Upwork等自由职业平台为雇主和自由职业者提供短期就业机会。对于大多数按需平台来说，匹配决策必须实时做出，因为供应和需求对延迟都很敏感。此外，市场双方的到达过程都存在高度的不确定性。因此，有效、高效的供需匹配是平台面临的一项艰巨而又重要的任务。在本次提出的研究中，我打算研究以下适用于不同平台的动态匹配问题：

In the past few years, the boom of Uber-like two-sided on-demand service platforms has made a significant impact on people's everyday life. The matching mechanism that links supply and demand is a critical contributing component to the decision-making processes that occur within the platforms. For example, ride-sharing/-hailing services like Uber and Lyft match drivers with riders; crowdsourced delivery platforms such as Uber Eats and Amazon Flex match couriers with orders; freelancing platforms such as Upwork connect employers with freelancers for short-term employment. For most on-demand platforms, matching decisions must be made in real time, as both supply and demand are sensitive to delay. Moreover, there is a high degree of uncertainty associated with the arrival processes on both sides of the market. Due to those reasons, effective and efficient matching between supply and demand is both a difficult and essential task for the platforms. In this proposed research, I intend to study the following dynamic matching problems applicable to different platforms: (i). Centralized one-to-one matching. This is the problem faced by platforms such as Uber for their ride-hailing services (e.g., UberX and UberXL). The problem is difficult due to the heterogeneity in supply and demand characteristics (e.g., location, rating). I will develop a Markov decision process model to formulate the problem, and focus on algorithmic and computational studies for maximizing total expected matching rewards. In particular, I will develop approximate algorithms with performance guarantee and reinforcement learning methods to solve the problem efficiently. (ii). Centralized many-to-one matching. Platforms such as ridesharing services (e.g., Uber Pool) and crowdsourced delivery services (e.g., Uber Eats) often assign multiple demand units to the same supplier. To formulate the problem, I propose a bi-level dynamic optimization framework. The outer-level solves the “matching” problem (i.e., the assignment of several demand units to a supplier), whereas the inner level solves the “routing” problem (e.g., finding a route to pickup and drop off riders by an Uber Pool driver). I aim to develop efficient approximate algorithms to compute the optimal matching and “routing” decisions. (iii). Decentralized dynamic matching. In essence, platforms such as Upwork and Airbnb are marketplaces, where supply and demand match with each other in a decentralized way. In contrast with the economic matching theories, decentralized matching in on-demand platforms are more time-sensitive and associated with short-term rewards. I will formulate the problem as a sequential game and characterize its equilibrium. I will also investigate possible interventions by the platform to improve matching benefits. Based on the above research projects, I will also study how improved matching efficiency impacts on society (e.g., how it affects traffic congestion, long-term job opportunities, etc.).