AI Research Portal

This paper addresses the challenge of designing matching policies for gig platforms that balance system revenue with customer waiting times, especially in the presence of "priority" features. The core idea is a hybrid model combining online matching and queue theory, which allows for quantitative analysis of user waiting times. The authors propose an LP-based sampling framework with parameterized policies to achieve this balance. Empirical claims are validated through comprehensive experiments on real datasets, demonstrating the framework's efficiency in promoting profit while adhering to committed waiting times.

The paper identifies several bottlenecks in existing gig platform matching policies:

Extended Waiting Times: Revenue-boosting features like Uber's "back-to-back" and Uber Eats' "Batch Order Route" lead to user complaints about excessive waiting times, despite increasing platform revenue.
Inability to Quantify Waiting Times: Current online matching frameworks, often based on bipartite graphs and real-time decision-making, struggle to quantitatively analyze request waiting times caused by preceding service delays. This is because they typically assume immediate service or ignore the practice of assigning multiple orders to a single driver.

A novel hybrid model combining online matching and queue theory for quantitative analysis of user waiting times in gig platforms.
An LP-based sampling framework featuring two parameters: a feasible solution to a benchmark Linear Program (LP-P) and a vector specifying the queue capacity maintained by each server.
A unified queue-theory-based method for competitive analysis of the framework's performance under different settings.
Theoretical findings validated by comprehensive experiments on real datasets, demonstrating the efficiency of the matching framework in promoting profit and meeting committed waiting times.
Proof of a 1/2-competitive policy for "serve-or-go" requests (zero waiting time warranty).
Proof of a competitive ratio of at least 1 – 1/(1 + L) for IID exponentially distributed service times.
Proof of a competitive ratio of at least 1 - (1/η)(1 + o(1)) for the general case with constant bounded memory.

The paper proposes a hybrid model called Online Matching with Guaranteed Waiting Time (OM-GWT). This model uses an edge-weighted bipartite graph G = (I, J, E), where I represents server types and J represents online request types. Each online request j arrives following an independent Poisson process of rate λj. Each server i has a warranty wi for an expected waiting time. Each edge e = (i, j) has a profit ve and a random service time Ce.

The online process involves an instant and irrevocable decision upon request arrival: either reject it or assign it to a feasible server i. If assigned, j joins a "virtual" queue Qi maintained by server i, which processes requests following a First-Come-First-Serve (FCFS) policy. Each server has a unit serving capacity. A policy ALG is feasible if the queue maintained by each server i meets its designated waiting-time warranty wi. The objective is to design an online policy ALG that is feasible and achieves a total expected profit as large as possible, captured by max Σe∈E ve · E[Xe].

The method utilizes an LP-Based Sampling Framework (SAMP), which takes two parameters:

A feasible solution x = {xe} to a benchmark Linear Program (LP-P).
A capacity vector L = {Li}i∈I, where Li is the queue capacity imposed on server i.

Key Equations (LP-P): LP-P: max Σe∈E ve xe subject to: Σe∈Ej xe ≤ λj, ∀j ∈ J; Σe∈Ei xe E[Ce] ≤ 1, ∀i ∈ I; 0 ≤ xe, ∀e ∈ E.

SAMP Algorithm Flow:

An online request of type j arrives at time t ∈ [0, T].
Sample an edge e = (i, j) ∈ Ej with probability xe/λj and reject j otherwise.
Assign j to i if the queue on server i is not blocked (i.e., there are no more than Li - 1 requests assigned to i, including the one receiving the service). Reject j otherwise.

The capacity vector L is determined based on the input waiting-time warranty wi to ensure the policy is feasible. The paper then analyzes the competitive ratio (CR) of SAMP(x*, L) where x* is an optimal solution to LP-P.

Graph Structure: Edge-weighted bipartite graph G = (I, J, E), where I is the set of server types (offline agents) and J is the set of online request types (online agents). Edges e = (i, j) indicate compatibility.
Spatial Attributes: Specific spatial attributes are associated with each server type (e.g., preferred working areas) and request type (e.g., starting and ending locations).
Arrival Process: Each online request (of type) j arrives following an independent Poisson process of rate λj over a time horizon [0, T].
Server Warranty: Each server i is designated with a warranty of an expected waiting time wi, meaning requests selecting service from i are guaranteed an expected waiting time no more than wi.
Profit and Service Time: Each edge e = (i, j) is associated with a weight ve > 0 representing the profit flow and incurs a random service time Ce. {Ce|e ∈ E} are assumed independent.
Queue Policy: Servers process all requests in their queue Qi following a First-Come-First-Serve (FCFS) policy.
Serving Capacity: Every server has a unit serving capacity, serving only one request at any time.
LP-P Objective: Maximize total expected profit Σe∈E ve xe.
LP-P Constraints:
- Σe∈Ej xe ≤ λj: Expected number of served requests of type j in unit time is no larger than arrival rate.
- Σe∈Ei xe E[Ce] ≤ 1: Expected accumulative service time on server i in unit time is no larger than one (unit capacity).
- 0 ≤ xe: Non-negativity.
Capacity Vector L (IID Exponential Service Time): L = {Li := [wi/β] + 1 | i ∈ I}, where β = E[Ce].
Constant Bounded Memory (General Case): max t≥0:Pr[Ce≥t]>0 (E[Ce|Ce ≥ t] - t) ≤ ci · E[Ce], ∀e ∈ Ei, with ci < c̄, ∀i ∈ I.
Capacity Vector L(x) (General Case)**: Li(x) = 1 / (2 + (wi - c̄i βi) / (Σe∈Ei E[Ce]xe / xi)) if wi < c̄i βi; Li(x*) = 1 if wi ≥ c̄i βi. Where βi := maxe∈Ei E[Ce] and s²e := Var[Ce]/E²[Ce].
Time Horizon: T ≫ 1, with some results obtained when T → ∞.
Computational Environment: All experiments conducted on a PC with 3.2GHz 12th Gen Intel Core i9 processor and 128GB main memory.

Dataset: A real-world Didi dataset containing millions of taxi trips collected in Haikou, China, from May to September 2017. The study area was restricted to longitude/latitude ranges (110.18, 110.48) and (19.90, 20.10), partitioned into a 15 × 10 grid.
Metrics:
- Competitive Ratio (CR): Ratio of the algorithm's total expected profit to the offline optimal policy's total expected profit (E[ALG] / E[π*off]).
- Curbing Ratio: Ratio of the average waiting time of riders of a given priority level to the designated waiting-time warranty. A lower curbing ratio indicates higher effectiveness in reducing waiting times.
Baselines: Greedy-based algorithm (Greedy), uniform-based algorithm (Uniform), and reinforcement-learning-based algorithm (RODA).
Numeric Results:
- Serve-or-Go Case (Figure 2): SAMP achieves decreasing CRs as T increases, consistently staying above the 1/2 lower bound. When T > 9000, SAMP nearly reaches this bound.
- IID Exponential Service Time Case (Figure 3a): SAMP's CRs always exceed the lower bound in Theorem 2. Its advantage over other baselines grows with larger L.
- IID Exponential Service Time Case (Figure 3b): SAMP significantly reduces riders' waiting times across priorities under profit maximization, with all baselines staying below a curbing ratio of 1.
- General Case (Figure 4a): SAMP maintains CRs above the bounds in Theorem 3, outperforming all baselines for any η.
- General Case (Figure 4b): SAMP reduces average waiting time by over 65%.
- Average Waiting Time on Two Priority Levels (Figure 4c): For η = 2.78, SAMP shows lower average waiting times for both Priority and Normal levels compared to baselines.

Homogeneous Arrival Rates: The current model assumes an independent Poisson arrival process of homogeneous rate for each request type. Generalizing to heterogeneous arrival rates for online requests is a stated future direction, implying a current limitation.
Tradeoff between Profit and Fairness: The paper notes that studying the potential tradeoff between profit and fairness within the current framework is a future research direction, suggesting that the current model does not explicitly optimize for fairness.

Method evidence: "In this paper, we propose a hybrid model combining features from online matching and queue theory. We aim to design matching policies to promote profit in gig platforms, while curbing users' waiting time to guaranteed levels." (section: 1 Introduction)
Result evidence: "Figure 3b shows that SAMP significantly reduces riders' waiting times across priorities under profit maximization, while all baselines stay below a curbing ratio of 1." (section: Results and Discussions)
Limitation evidence: "The first is to generalize the current setting to heterogeneous arrival rates for online requests. The second is to study the potential tradeoff between profit and fairness within the current framework." (section: 7 Conclusion and Future Directions)

Matching Policy Design for Gig Platforms with “Priority” Features

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures