Near-optimal control of Ride-Hailing Platforms with Strategic Servers
Sushil Varma
Ph.D. Student
ISyE, Georgia Tech
In Academic Job Market
Joint work with
Francisco Castro
Asst. Professor
Anderson School of Management, UCLA
Siva Theja Maguluri
Associate Professor
ISyE, Georgia Tech
Strategic Agents in Ride-Hailing Platforms
Set a Driver Destination
When you set a Driver Destination in your app, we'll try and match you with trip requests from riders going towards that destination.
Surge Pricing
Area Preferences
Drivers can be strategic Preferred destinations based on offered prices
Objective
How to make optimal pricing and matching decisions in the presence of strategic agents?
Model: Stochastic Matching Network
Discrete Time System
State-Dependent Price
State-Dependent Match
Stochastic Arrivals
Arrival Rates
Model: Stochastic Matching Network
Discrete Time System
State-Dependent Price
State-Dependent Match
Stochastic Arrivals
Arrival Rates
Objective
Strategic Behavior
Model: Stochastic Matching Network
Customer Arrivals
Discrete Time System
Model: Stochastic Matching Network
Customer Arrivals
Discrete Time System
Price
Quantity
Demand Curve
Server Arrivals
Server can choose their own queues
A simple example
Model: Stochastic Matching Network
Customer Arrivals
Discrete Time System
Price
Quantity
Demand Curve
Server Arrivals
Server can choose their own queues
A simple example
Utility
Quantity
Supply Curve
Model: Stochastic Matching Network
Customer Arrivals
Discrete Time System
Price
Quantity
Demand Curve
Server Arrivals
Server can choose their own queues
A simple example
Utility
Quantity
Supply Curve
Service
Model: Stochastic Matching Network
Customer Arrivals
Discrete Time System
Price
Quantity
Demand Curve
Server Arrivals
Server can choose their own queues
A simple example
Utility
Quantity
Supply Curve
Service
Model: Stochastic Matching Network
Customer Arrivals
Discrete Time System
Price
Quantity
Demand Curve
Server Arrivals
Server can choose their own queues
A simple example
Utility
Quantity
Supply Curve
Service
Objective
Model: Stochastic Matching Network
Customer Arrivals
Discrete Time System
Price
Quantity
Demand Curve
Server Arrivals
Server can choose their own queues
A simple example
Utility
Quantity
Supply Curve
Service
Objective
Objective
Maximize Revenue – Cost – Waiting Penalty
Revenue:
Price
Waiting Penalty:
Cost:
There can be multiple prices associated with the same arrival rates!
Value function of an optimization problem!
Objective
Revenue:
Price
Waiting Penalty:
Cost:
There can be multiple prices associated with the same arrival rates!
Value function of an optimization problem!
Non-Strategic [Varma et al] v/s Strategic Setting
Benchmark
Pricing Policy
Matching Policy
Difference from Benchmark
Lower Bound
Fluid Model
Two-Price Policy
Max-Weight
Non Strategic Setting
Strategic Setting
None of the results apply directly to the strategic setting
Probabilistic Fluid Model
Random Matching
Probabilistic Two-Price
Benchmark: Fluid Model
Replace stochastic quantities by their deterministic counterparts
Subject to
Balance Equations to Match Customers and Servers
Compatibility Constraint
Lack of convexity!
How do we convexify the objective?
Benchmark: Probabilistic Fluid Model
Replace stochastic quantities by their deterministic counterparts
Subject to
Balance Equations to Match Customers and Servers
Compatibility Constraint
How do we convexify the objective?
Allow for probabilistic server policies
Non-Strategic [Varma et al] v/s Strategic Setting
Benchmark
Pricing Policy
Matching Policy
Difference from Benchmark
Lower Bound
Fluid Model
Two-Price Policy
Max-Weight
Non-Strategic Setting
Strategic Setting
Next goal: Devise a policy whose profit is close to the benchmark
Probabilistic Fluid Model
Random Matching
Probabilistic Two-Price
What if we employ the fluid optimal policy?
Fluid optimal policy is static with respect to the system state
The system will be unstable
We need to consider a perturbation of the fluid optimal
Revenue Loss
Expected Queue Length
Like a single server queue in HT
Revenue Loss
Expected Queue Length
Like a single server queue in HT
Static Customer Pricing
Probabilistic Two-Price Server
Intuition by an example
Service rate is 0 or 2 with prob 1/2
Probabilistic Fluid Optimal
1
2
0
Non-Strategic [Varma et al] v/s Strategic Setting
Benchmark
Pricing Policy
Matching Policy
Difference from Benchmark
Lower Bound
Fluid Model
Two-Price Policy
Max-Weight
Non-Strategic Setting
Strategic Setting
None of the results apply directly to the strategic setting
Probabilistic Fluid Model
Random Matching
Probabilistic Two-Price
Takeaways
What I did not talk about
Backup Slides
Summary of Results
Setting | Benchmark | Customer Pricing Policy | Server Pricing Policy | Matching Policy | ROC to Benchmark | Lower Bound |
Non-Strategic Agents [Varma et al.] | Fluid Model | Two-Price | Two-Price | Max-Weight | | |
Price-Dependent Utility | Probabilistic Fluid Model | Two-Price | Probabilistic Static | Max-Weight | | |
Price and Matching rate Dependent Utility | Random Matching | |||||
Price and Matching rate Dependent Utility | Probabilistic Fluid Model | Static Pricing | Probabilistic Two-Price | Random Matching | | |
Intuition by an example
Model: Stochastic Matching Network
Customer Arrivals
Set Price for each customer type
Accept/Reject Price
Mean Arrivals
Price
Quantity
Demand Curve
Stochastic Arrivals
Server Arrivals
Set Price for each server type
Picks a queue to join or leaves
Mean Arrivals
Stochastic Arrivals
Service
Discrete-Time Markov Chain
Takeaways