Dynamic Matching for On-Demand Service Platforms

按需服务平台动态匹配

• 批准号: RGPIN-2019-07050
• 负责人: Zhou, Yun
• 金额: $ 1.89万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=716270
• 关键词: Dynamic; Matching; Demand; Service; Platforms

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

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