Dynamic Matching for On-Demand Service Platforms

在过去的几年里，像优步这样的双边按需服务平台的蓬勃发展对人们的日常生活产生了重大影响。连接供需的匹配机制是平台内决策过程的关键组成部分。例如，优步（Uber）和Lyft等拼车/叫车服务将司机与乘客匹配起来；Uber Eats和Amazon Flex等众包配送平台将快递员与订单匹配起来；Upwork等自由职业平台为雇主和自由职业者提供短期就业机会。对于大多数按需平台来说，匹配决策必须实时做出，因为供应和需求对延迟都很敏感。此外，市场双方的到达过程都存在高度的不确定性。因此，有效、高效的供需匹配是平台面临的一项艰巨而又重要的任务。在本次提出的研究中，我打算研究以下适用于不同平台的动态匹配问题：******(I)。集中式一对一匹配。这是优步等打车服务平台（例如UberX和UberXL）所面临的问题。由于供应和需求特征（例如，地点、评级）的异质性，这个问题很困难。我将开发一个马尔可夫决策过程模型来表述这个问题，并专注于最大化总预期匹配奖励的算法和计算研究。特别是，我将开发具有性能保证的近似算法和强化学习方法来有效地解决问题。******(ii)。集中式多对一匹配。拼车服务（如Uber Pool）和众包外卖服务（如Uber Eats）等平台通常会将多个需求单位分配给同一供应商。为了表述这个问题，我提出了一个双层动态优化框架。外部层解决了“匹配”问题（即，将几个需求单元分配给供应商），而内部层解决了“路由”问题（例如，找到优步拼车司机接送乘客的路线）。我的目标是开发有效的近似算法来计算最优匹配和“路由”决策。******(iii)。分散的动态匹配。从本质上讲，Upwork和Airbnb等平台是市场，在这里，供需以一种分散的方式相互匹配。与经济匹配理论相比，按需平台的去中心化匹配更具时效性，且与短期回报相关。我将把这个问题表述为一个顺序博弈，并描述其均衡性。我还将研究平台可能采取的干预措施，以提高匹配效益。******在上述研究项目的基础上，我还将研究匹配效率的提高对社会的影响（例如，它如何影响交通拥堵，长期就业机会等）。**

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.). **