Dynamic Matching for On-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.).