Dynamic Matching for On-Demand Service Platforms

在过去的几年里，类似Uber的双边按需服务平台的繁荣对人们的日常生活产生了重大影响。将供需联系起来的匹配机制是平台内决策过程的一个重要组成部分。例如，Uber和Lyft等拼车/叫车服务为司机和乘客牵线搭桥；Uber Eats和Amazon Flex等众包递送平台为快递员匹配订单；Upwork等自由职业者平台为雇主和自由职业者牵线搭桥，以获得短期就业。对于大多数按需平台，匹配决策必须实时做出，因为供应和需求对延迟都很敏感。此外，市场双方的抵达过程都存在高度的不确定性。由于这些原因，有效和高效的供需匹配对平台来说既是一项艰巨的任务，也是一项必不可少的任务。在这项拟议的研究中，我打算研究适用于不同平台的以下动态匹配问题：I。集中一对一匹配。这就是优步等平台在提供叫车服务(如UberX和UberXL)时面临的问题。由于供需特征(例如，地点、评级)的异质性，这一问题很难解决。我将开发一个马尔可夫决策过程模型来描述这个问题，并专注于最大化总预期匹配回报的算法和计算研究。特别是，我将开发具有性能保证的近似算法和强化学习方法来高效地解决该问题。(Ii)。集中式多对一匹配。拼车服务(例如，Uber Pool)和众包交付服务(例如，Uber Eats)等平台通常将多个需求单位分配给同一供应商。为了解决这个问题，我提出了一个双层动态优化框架。外层解决了“匹配”问题(即，将多个需求单位分配给供应商)，而内层解决了“路线”问题(例如，Uber Pool司机找到了一条路线来接送乘客)。我的目标是开发高效的近似算法来计算最优匹配和“路由”决策。(三)。分散式动态匹配。本质上，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.).