Grant: Discovery Grants Program - Individual
McMaster University
$52,000.00
Dynamic Matching for On-Demand Service Platforms
FY 2024-25
Summary
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.).
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2019-07050
Name nom
Zhou, Yun
Department département
DeGroote School of Business
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2019
Award amount
52000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
520
Area of application group en
Manufacturing processes and products
Area of application group fr
Procédés et produits industriels
Area of application en
Production and operations management
Area of application fr
Production et gestion des opérations
Research subject code
1606
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations management
Research subject fr
Gestion de la production
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Dynamic Matching for On-Demand Service Platforms
Keywords
dynamic matching; centralized matching; decentralized matching; approximate algorithm; reinforcement learning; on-demand service platforms
Application summary
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.).