Truthful mechanisms to maximize the social welfare in real-time ride-sharing

Abstract

Ride-sharing contributes significantly to lowering trip expenses, easing traffic congestion and decreasing air pollution. However, current order pairing approaches in ride-sharing usually focus on minimizing total trip distances or maximizing platform profits, overlooking the drivers’ desire for increased earnings. As a result, drivers might provide dishonest information to gain higher profits, leading to inefficient order pairing for the ride-sharing platform and potential losses for both the platform and drivers. In this paper, we address this challenging issue by developing efficient order pairing mechanisms that maximize the social welfare of the platform and drivers. Specifically, we introduce two truthful auction-based order pairing mechanisms, SWMOM-VCG and SWMOM-GM, where drivers bid on platform-published orders to complete them and earn profits. We provide theoretical proof that both mechanisms fulfill the criteria of individual rationality, profitability, truthfulness and so on. Using real taxi order data from New York City, we assess the performance of both mechanisms and show that they achieve greater social welfare compared to existing methods. Additionally, we find that SWMOM-GM requires less computation time than SWMOM-VCG for order pairing, with only a minor reduction in social welfare.

1. Introduction

Presently, the development of an effective road transportation system poses a critical challenge in modern society. This is due to the substantial negative environmental impact of vehicular emissions and the exacerbation of traffic congestion resulting from the increasing number of vehicles on the road. Remarkably, each automobile typically transports an average of 1.6 passengers, signifying that a mere 25% of emissions can be attributed to actual human transportation, while the remaining emissions stem from the movement of unoccupied seats [16]. To mitigate the associated social expenses, such as trip expenses, traffic congestion, and environmental degradation, researchers from various fields have put forth the concept of ride-sharing as a viable resolution [5,22,24].

In fact, to capitalize on vacant seats and minimize passengers’ financial burden, ride-hailing enterprises such as Uber1

¹

http://www.uber.com

and Didi Chuxing2

²

https://www.didiglobal.com

have actively advanced the ride-sharing industry in recent years. In this business, vehicles can accept new ride requests while simultaneously fulfilling existing ones. According to iResearch,3

³

http://www.iresearch.com.cn

35.9% of taxi passengers opt for real-time ride-sharing services, with each taxi averaging 3.4 such services daily. For such a system to function optimally, the ride-sharing platform must efficiently pair incoming requests with available vehicles. Nevertheless, existing studies often focus on maximizing platform profits, reducing passenger expenses, or minimizing trip distances in the order pairing process, such as [18,33] and so on. These works overlook the reality that drivers also seek to maximize their earnings. Actually, drivers may provide untruthful information to gain a financial advantage, leading to suboptimal order pairing for the ride-sharing platform and, consequently, losses for both the platform and drivers. Thus, this paper aims to design highly efficient order pairing mechanisms that maximize the social welfare of both the platform and drivers while ensuring truthful information reporting from drivers.

In this paper, we assume that the platform charges prepaid fares4

⁴

In the ride-sharing industry, the prepaid fare for passengers is calculated based on multiple factors, including the departure and destination, current supply and demand conditions, and dynamic discounts. Once the passenger has paid the prepaid fare, no additional fees are incurred for the ride-sharing service.

on passengers upon placing ride requests. Then following the approach of several existing studies, the platform employs an auction-based mechanism, enabling drivers to bid on ride orders and subsequently determining the optimal pairing of orders with available vehicles and the corresponding driver payments. As previously discussed, this procedure ought to ensure profitability for both the platform and vehicle drivers, incentivizing their continued participation in the business. Therefore, Our objective is to design a mechanism that efficiently pairs orders to vehicles while maximizing the social welfare of the platform and drivers.5

⁵

A typical ride-sharing system involves three key entities: passengers, vehicle drivers and the ride-sharing platform. However, since we assume that the ride-sharing platform employs an upfront charing policy to passengers, it is not necessary to consider the revenues of passengers when pairing the orders with vehicles. Therefore the social welfare in this paper just consists of revenues of the ride-sharing platform and vehicle drivers.

Furthermore, it is crucial to consider that ride-sharing vehicles often vary in terms of associated expenses. Drivers may report this expense information untruthfully to boost their profits, potentially leading to suboptimal order pairing and diminished social welfare. Consequently, it is important to design a truthful mechanism that encourages honest bidding from drivers. In addition to the truthfulness, An effective mechanism should also adhere to several key economic principles: individual rationality, ensuring that drivers do not incur losses and maintain non-negative profits; and profitability [34], guaranteeing that the platform’s profits remain non-negative. Additionally, given the potential necessity of pairing a large volume of incoming orders to thousands of viable vehicles, the mechanism must be computationally efficient, facilitating near real-time pairing services through polynomial-time order pairing execution.

In this paper, we adopt a round-based order pairing approach to address the need for real-time service, consistent with the methods used in [33,34]. Specifically, we implement a one-sided reverse auction, wherein the vehicle drivers bid on orders posted by the platform with upfront charged fares. Subsequently, the ride-sharing platform determines the optimal order pairing and driver payments for each round, with the intent to maximize the social welfare while preserving individual rationality, profitability, truthfulness and computational efficiency. This paper contributes to the existing body of knowledge in the following ways:

• Firstly, we introduce a VCG based mechanism, termed SWMOM-VCG, designed to optimally pair ride orders with vehicle drivers in the ride-sharing, thereby maximizing the social welfare. We demonstrate that this mechanism successfully adheres to the above properties of individual rationality, profitability, truthfulness and computational efficiency.

• Moreover, while SWMOM-VCG is capable of performing order pairing within polynomial time, the actual computational burden remains significant in scenarios involving a vast number of incoming orders and potential vehicles. To expedite the order pairing process with only a minor compromise in social welfare, we propose an alternative mechanism, termed SWMOM-GM, which incorporates a greedy method for order pairing. We calculate the lower bound of social welfare for SWMOM-GM compared to the optimal pairing and demonstrate experimentally that its social welfare is only marginally lower than that of SWMOM-VCG. Importantly, SWMOM-GM also satisfies the above four properties.

• Finally, we conduct comprehensive experiments to assess the performance of our proposed mechanisms in comparison to the state-of-the-art approaches with respect to social welfare, social expenses, rate of served orders, and other relevant metrics. The experimental results demonstrate that our proposed mechanisms yield superior social welfare compared to the state-of-the-art approaches.

The paper is organized as follows: Section 2 provides an overview of the related work, Section 3 describes the problem in detail, and Sections 4 and 5 present the proposed mechanisms. Section 6 presents the experimental evaluation of these mechanisms, and the paper concludes with Section 7.

2. Related work

Numerous studies have been conducted to analyze various aspects of ride-sharing, including topics such as system implementation, route planning and so on [7,14,20,26]. For instance, [1] presents a flexible ride-sharing scheme incorporating spatio-temporal constraints, aimed at minimizing total trip distance and maximizing the number of served orders. When examining route planning, researchers typically focus on devising trip plans for each vehicle to pick up passengers while minimizing the overall trip distance [19] – a problem that has been proven to be NP-hard [27]. Several studies, such as [7,20,21], have attempted to address the route planning challenge in ride-sharing. Additionally, to expedite the generation of route planning in ride-sharing, a Kinetic Tree-based method has been proposed to decrease time complexity [15], while a branch-and-bound-based algorithm has been introduced to iteratively adjust the original route plan, resulting in the creation of a new plan [2].

Furthermore, as previously discussed, order pairing constitutes a critical component of ride-sharing systems. Existing research on order pairing in ride-sharing typically aims to minimize total trip distance, maximize the order served rate, or optimize profits. For instance, a spatio-temporal grid index has been proposed to facilitate passengers in quickly identifying vehicles with the shortest detour distances [20,21]. Additionally, a range of space-time pruning techniques have been employed to accelerate the pairing process [10]. In [3], a forecasting method is integrated with dynamic pricing techniques in the order pairing process to increase the number of served orders. Another approach involves an auction-based parallel order pairing mechanism, where drivers bid on orders published by the platform, which subsequently determines the pairing of drivers and orders [2]. This approach is further refined through the introduction of a greedy-based order packing algorithm [33]. In [6], a queuing theory-based order pairing framework is proposed with the objective of maximizing the platform’s profit.

Mechanism design has found extensive applications in various domains, such as auction [23], meeting scheduling [9] and public safety [25]. Given that the entities involved in ride-sharing (i.e., the platform, drivers, and passengers) are typically self-interested and may act strategically to maximize their profits, mechanism design is applied in ride-sharing to mitigate such strategic behavior [11]. In [17], a system named ABC is introduced to determine passengers’ ride-sharing plans based on their valuations, employing a VCG price to calculate passengers’ payments and ensure truthful valuation disclosure. A second-price-based auction mechanism is proposed to address the order pairing challenge in ride-sharing, with the objectives of maximizing the served order rate and minimizing the overall trip distance [18].

Moreover, several studies have employed auction-based mechanisms to pair orders with drivers, with the aim of maximizing social welfare, as demonstrated in [31,34]. Such works typically require passengers to report their valuations for the trips. However, accurately assessing trip expenses may prove challenging for passengers [4]. To tackle this issue, a pricing algorithm based on trip demand (incorporating departure and destination information) is proposed, along with an online mechanism designed to motivate passengers to truthfully report their trip information [28]. Furthermore, to maintain the platform’s budget balance, a pricing algorithm is developed to prevent budget deficits in a mixed bilateral ride-sharing market, where the distinction between drivers and passengers is not strictly defined [32]. Some studies have analyzed approaches to maximize the ride-sharing platform’s profit. For instance, in [2], the platform functions as an auctioneer, receiving bids from drivers and selecting the highest bidder to optimize profits. In [3], a second pricing-based reserve auction is employed to ensure truthful bidding from drivers and to maximize the platform’s profit.

However, to the best of our knowledge, existing works usually ignores the profits of both the platform and vehicle drivers. Consequently, in this paper, we propose auction-based truthful mechanisms wherein drivers bid on orders to maximize the social welfare of both the platform and drivers, ultimately ensuring that both sides remain motivated to participate in the business.

3. Problem formulation

In this section, we first present the fundamental concepts and describe the general framework of the ride-sharing system, and then we provide a detailed, formal definition of our problem in detail. Table 1 enumerates the key notations used in this paper.

Table 1

Notations

Notation	Explanation
t, T	Index, total number of time slices in an episode.
$\mathcal{O}$ , $\mathcal{V}$ , $\mathcal{G}$ , $\mathit{VP}$	Set of orders, set of viable vehicles, set of victorious vehicles which obtain orders in the order pairing, set of viable pairs.
${\mathit{lc}}_{\mathit{j}}^{\mathit{s}}$ , ${\mathit{lc}}_{\mathit{j}}^{\mathit{e}}$	Departure and destination of order ${\mathit{o}}_{\mathit{j}}$ .
${\mathit{t}}_{\mathit{j}}^{\mathit{r}}$ , ${\mathit{t}}_{\mathit{j}}^{\mathit{w}}$	Time when ${\mathit{o}}_{\mathit{j}}$ is raised and the longest time a passenger can wait after making riding request.
${\mathit{d}}_{\mathit{j}}$ , ${\mathit{n}}_{\mathit{j}}$ , ${\mathit{f}}_{\mathit{j}}$	Maximum detour rate that passengers in ${\mathit{o}}_{\mathit{j}}$ can bear, the number of passengers in ${\mathit{o}}_{\mathit{j}}$ and trip fare of ${\mathit{o}}_{\mathit{j}}$ paid to the platform.
${\mathit{lc}}_{\mathit{k}}$ , ${\mathit{s}}_{\mathit{k}}$ , ${\mathit{e}}_{\mathit{k}}$ , ${\mathit{n}}_{\mathit{k}}$ , ${\mathit{N}}_{\mathit{k}}$ , ${\mathit{h}}_{\mathit{k}}$	Current location, trip plan, expense per kilometer, the number of seats currently available, seat capacity and profit of vehicle ${\mathit{v}}_{\mathit{k}}$ .

3.1. Symbols and definitions

We model the order pairing process as an one-side reverse auction operating within a series of discrete time slices $\mathcal{T}=\{1\mathrm{,}2\mathrm{,}3\mathrm{,}\dots \mathrm{,}\mathit{T}\}$ . As shown in Fig. 1, we present the structure of a ride-sharing system. In a real-time ride-sharing system, passengers have the option to submit orders to the platform at any time. At the start of a given time slice t, the platform collects the set of orders ${\mathcal{O}}_{\mathit{t}}=\{{\mathit{o}}_{\mathit{j}}\}$ , consisting of newly received orders during the current time slice as well as unserved orders from the previous time slice. The definition of an order is provided below.

Fig. 1.

An auction-based real-time ride-sharing system. In this system, passengers first submit riding orders, and then vehicle drivers bid for the orders. The platform then pair orders with vehicles and provide payments to drives upon completion of the ride.

Definition 1 (Order).

Order ${\mathit{o}}_{\mathit{i}}$ can be formally represented as a tuple $⟨{\mathit{lc}}_{\mathit{j}}^{\mathit{s}}\mathrm{,}{\mathit{lc}}_{\mathit{j}}^{\mathit{e}}\mathrm{,}{\mathit{t}}_{\mathit{j}}^{\mathit{r}}\mathrm{,}{\mathit{t}}_{\mathit{j}}^{\mathit{w}}\mathrm{,}{\mathit{d}}_{\mathit{j}}\mathrm{,}{\mathit{n}}_{\mathit{j}}\mathrm{,}{\mathit{f}}_{\mathit{j}}⟩$ , where ${\mathit{lc}}_{\mathit{j}}^{\mathit{s}}$ and ${\mathit{lc}}_{\mathit{j}}^{\mathit{e}}$ correspond to the departure and destination of the order respectively, ${\mathit{t}}_{\mathit{j}}^{\mathit{r}}$ and ${\mathit{t}}_{\mathit{j}}^{\mathit{w}}$ represent the time when ${\mathit{o}}_{\mathit{j}}$ is raised and the longest wait time beared by the passenger, respectively, ${\mathit{d}}_{\mathit{j}}$ is the maximum detour rate acceptable to the passengers in ${\mathit{o}}_{\mathit{j}}$ , ${\mathit{n}}_{\mathit{j}}$ denotes the number of passengers in ${\mathit{o}}_{\mathit{j}}$ and ${\mathit{f}}_{\mathit{j}}$ represents the trip fare paid to the platform for the order.

Upon receiving riding orders, the platform is required to compute prepaid fares to be charged to passengers. Subsequently, passengers are given the option to accept or reject the offered fares.6

⁶

How passengers making decision is also a tricky problem. In [18], passengers bid strategically for riding services. In [31], a truthful mechanism was designed where passengers bid truthfully. However, as demonstrated in [28], requiring passengers to bid for vehicles can present challenges, and such mechanisms may not be practical for real-world applications. Therefore, in this paper we consider the prepaid fares to passengers and ignore the strategic bidding behavior of passengers.

Following the collection of orders, the platform must determine the set of viable vehicles ${\mathcal{V}}_{\mathit{t}}$ from the total pool of available vehicles. We provide a formal definition of a vehicle below.

Definition 2 (Vehicle).

Vehicle ${\mathit{v}}_{\mathit{k}}$ can be defined as a tuple $⟨{\mathit{lc}}_{\mathit{k}}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{,}{\mathit{e}}_{\mathit{k}}\mathrm{,}{\mathit{n}}_{\mathit{k}}\mathrm{,}{\mathit{N}}_{\mathit{k}}⟩$ , where ${\mathit{lc}}_{\mathit{k}}$ denotes the present location of ${\mathit{v}}_{\mathit{k}}$ , ${\mathit{s}}_{\mathit{k}}$ represents the vehicle’s trip plan, ${\mathit{e}}_{\mathit{k}}$ signifies the expense per kilometer incurred by ${\mathit{v}}_{\mathit{k}}$ , ${\mathit{n}}_{\mathit{k}}⩽{\mathit{N}}_{\mathit{k}}$ is the current number of available seats within ${\mathit{v}}_{\mathit{k}}$ , and ${\mathit{N}}_{\mathit{k}}$ denotes the maximum seat capacity of ${\mathit{v}}_{\mathit{k}}$ .

Fig. 2.

An example of trip plan.

Note that ${\mathit{e}}_{\mathit{k}}$ is an average value which is subject to various factors such as fuel expense, vehicle wear, maintenance expense and so on. For each vehicle, its trip plan is a sequence of departure and destination corresponding to the orders it is serving. In the following, we may use ${\mathit{o}}_{\mathit{j}}\in {\mathit{s}}_{\mathit{k}}$ to represent ${\mathit{lc}}_{\mathit{j}}^{\mathit{s}}\mathrm{,}{\mathit{lc}}_{\mathit{j}}^{\mathit{e}}\in {\mathit{s}}_{\mathit{k}}$ for the sake of simplicity and convenience. For the vehicle, serving a new order may lead to a detour for the orders in its initial trip plan. We use $\mathit{d}\mathrm{(}\mathit{i}\mathrm{,}\mathit{j}\mathrm{)}$ to denote the detour rate of ${\mathit{o}}_{\mathit{j}}$ in ${\mathit{s}}_{\mathit{k}}$ and it is equal to $\frac{{\mathit{len}}_{\mathit{k}}\mathrm{(}{\mathit{lc}}_{\mathit{j}}^{\mathit{s}}\mathrm{,}{\mathit{lc}}_{\mathit{j}}^{\mathit{e}}\mathrm{)}-\mathit{len}\mathrm{(}{\mathit{lc}}_{\mathit{j}}^{\mathit{s}}\mathrm{,}{\mathit{lc}}_{\mathit{j}}^{\mathit{e}}\mathrm{)}}{\mathit{len}\mathrm{(}{\mathit{lc}}_{\mathit{j}}^{\mathit{s}}\mathrm{,}{\mathit{lc}}_{\mathit{j}}^{\mathit{e}}\mathrm{)}}$ , where $\mathit{len}\mathrm{(}·\mathrm{)}$ represents the shortest driving distance between two locations and ${\mathit{len}}_{\mathit{k}}\mathrm{(}{\mathit{lc}}_{\mathit{j}}^{\mathit{s}}\mathrm{,}{\mathit{lc}}_{\mathit{j}}^{\mathit{e}}\mathrm{)}$ denotes the distance between ${\mathit{lc}}_{\mathit{j}}^{\mathit{s}}$ and ${\mathit{lc}}_{\mathit{j}}^{\mathit{e}}$ . For example, as illustrated in Fig. 2(a), ${\mathit{v}}_1$ ’s original trip plan is ${\mathit{lc}}_1^{\mathit{s}}\to {\mathit{lc}}_2^{\mathit{s}}\to {\mathit{lc}}_2^{\mathit{e}}\to {\mathit{lc}}_1^{\mathit{e}}$ . However, when ${\mathit{v}}_1$ obtains ${\mathit{o}}_3$ in Fig. 2(b), its trip plan is revised to ${\mathit{lc}}_1^{\mathit{s}}\to {\mathit{lc}}_2^{\mathit{s}}\to {\mathit{lc}}_3^{\mathit{s}}\to {\mathit{lc}}_3^{\mathit{e}}\to {\mathit{lc}}_2^{\mathit{e}}\to {\mathit{lc}}_1^{\mathit{e}}$ . The detour rate of ${\mathit{o}}_1$ is $\mathit{d}\mathrm{(}1\mathrm{,}1\mathrm{)}=\frac{5-3}{3}=0.67$ (the length of each edge is equal to 1). Based on the above definitions, we provide a formal definition of Viable Trip Plan below.

Definition 3 (Viable Trip Plan).

Having average speed ${\mathit{V}}_{\mathrm{ave}}$ of vehicles and a trip plan ${\mathit{s}}_{\mathit{k}}$ at time slice t, we define ${\mathit{s}}_{\mathit{k}}$ is viable for ${\mathit{v}}_{\mathit{k}}$ if the following criteria are satisfied:

${\sum }_{{\mathit{o}}_{\mathit{j}}\in {\mathit{s}}_{\mathit{k}}}{\mathit{n}}_{\mathit{j}}⩽{\mathit{N}}_{\mathit{k}}$ .

$\forall {\mathit{o}}_{\mathit{j}}\in {\mathit{s}}_{\mathit{k}}$ , $\mathit{d}\mathrm{(}\mathit{j}\mathrm{,}\mathit{k}\mathrm{)}⩽{\mathit{d}}_{\mathit{j}}$ .

$\forall {\mathit{lc}}_{\mathit{j}}^{\mathit{s}}\in {\mathit{s}}_{\mathit{k}}$ , ${\mathit{V}}_{\mathrm{ave}}·\mathrm{(}{\mathit{t}}_{\mathit{j}}^{\mathit{w}}+{\mathit{t}}_{\mathit{j}}^{\mathit{r}}-\mathit{t}\mathrm{)}⩾\mathit{len}\mathrm{(}{\mathit{lc}}_{\mathit{k}}\mathrm{,}{\mathit{lc}}_{\mathit{j}}^{\mathit{s}}\mathrm{)}$ .

The first criterion implies that the number of passengers in the vehicle cannot surpass its seat capacity at any time. The second and third criteria mean that the trip plan must adhere to order ${\mathit{o}}_{\mathit{j}}$ ’s waiting time and maximum detour rate constraints.

Definition 4 (Viable Pair).

A viable pair is defined as a tuple $\mathrm{(}{\mathit{o}}_{\mathit{j}}\mathrm{,}{\mathit{v}}_{\mathit{k}}\mathrm{)}$ if the trip plan of ${\mathit{v}}_{\mathit{k}}$ is still viable after the insertion of ${\mathit{o}}_{\mathit{j}}$ .

Upon receiving passenger orders, the platform computes all viable pairs at time slice t which constitutes the set of viable pairs ${\mathit{VP}}_{\mathit{t}}$ . Then the platform publishes the information of each order to the corresponding vehicles according to the set of viable pairs. Each vehicle calculates the additional expense of serving a new order and submits it as the bid to the platform. Note that when allowing multiple orders to be added into the viable trip plan of a vehicle at the same time, the issue becomes a combinatorial problem. The space of bidding bundle grows exponentially in the number of orders, which makes it impossible for bidders to report their full value function in a viable time even in a greedy manner. It is also impossible for the platform to do the optimal pairing in a viable time. Therefore we consider that the platform assign a maximum of one order to each vehicle per time slice. Furthermore, since the route planning is an NP-Hard problem [33], this papers assumes that vehicles utilize the method proposed in [20] to integrate departures and destinations of incoming orders into their original trip plan, where vehicles preserve the sequence of their existing orders and insert new orders into the position that incurs the least additional trip expense. Furthermore, we adopt a pruning method to expedite the searching process [30]. We use $\mathit{exps}\mathrm{(}\mathit{j}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}$ to represent the additional expense that vehicle ${\mathit{v}}_{\mathit{k}}$ serves order ${\mathit{o}}_{\mathit{j}}$ , which is calculated as follows: $$\begin{array}{}\text{(1)}& \mathit{exps}\mathrm{(}\mathit{j}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}={\mathit{c}}_{\mathit{k}}·\mathrm{\Delta }\mathit{D}\mathrm{(}\mathit{j}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}\end{array}$$ where $\mathrm{\Delta }\mathit{D}\mathrm{(}\mathit{j}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}$ denotes the additional trip distance incurred by vehicle ${\mathit{v}}_{\mathit{k}}$ when serving order ${\mathit{o}}_{\mathit{j}}$ . We use $\widehat{\mathit{exps}}\mathrm{(}\mathit{j}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}$ to represent the corresponding additional expense bid by the driver. Note that $\widehat{\mathit{exps}}\mathrm{(}\mathit{j}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}$ may not be equal to $\mathit{exps}\mathrm{(}\mathit{j}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}$ if the driver submits a dishonest bid. The set of all bids at time slice t is represented as follows: $$\begin{array}{}\text{(2)}& {\mathit{B}}_{\mathit{t}}=\{\widehat{\mathit{exps}}\mathrm{(}\mathit{j}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}|{\mathit{o}}_{\mathit{j}}\in {\mathit{O}}_{\mathit{t}}\mathrm{,}{\mathit{v}}_{\mathit{k}}\in {\mathit{V}}_{\mathit{t}}\mathrm{,}\mathrm{(}{\mathit{o}}_{\mathit{j}}\mathrm{,}{\mathit{v}}_{\mathit{k}}\mathrm{)}\in {\mathit{VP}}_{\mathit{t}}\}\end{array}$$

Finally, the platform performs order pairing based on the bids submitted by the drivers. The resulting pair is represented as ${\mathit{\sigma }}_{\mathit{t}}\mathrm{(}·\mathrm{)}$ . If ${\mathit{\sigma }}_{\mathit{t}}\mathrm{(}\mathit{k}\mathrm{)}=\mathit{j}$ , it indicates that ${\mathit{o}}_{\mathit{j}}$ is assigned to vehicle ${\mathit{v}}_{\mathit{k}}$ at time slice t. We use ${\mathcal{G}}_{\mathit{t}}\subseteq {\mathcal{V}}_{\mathit{t}}$ to represent the set of victorious vehicles which obtain the orders in the order pairing process. The platform also calculates the payment made to the victorious drivers who are paired with the orders, represented by ${\mathcal{P}}_{\mathit{t}}=\{{\mathit{p}}_{\mathit{j}}\}$ . Moreover, we can calculate the profit of vehicle ${\mathit{v}}_{\mathit{k}}$ , denoted as ${\mathit{h}}_{\mathit{k}}$ , and the profit of the platform, denoted as ${\mathit{H}}_{\mathit{p}}$ , as follows: $$\begin{array}{}\text{(3)}& {\mathit{h}}_{\mathit{k}}=\left\{\begin{array}{ll}{\mathit{p}}_{\mathit{k}}-\mathit{exps}\mathrm{(}{\mathit{\sigma }}_{\mathit{t}}\mathrm{(}\mathit{k}\mathrm{)}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}\mathrm{)}\mathrm{,}& \text{if }{\mathit{v}}_{\mathit{k}}\in {\mathcal{G}}_{\mathit{t}}.\\ 0\mathrm{,}& \text{otherwise}.\end{array}\right.\text{(4)}& {\mathit{H}}_{\mathit{p}}={\displaystyle \sum }_{{\mathit{v}}_{\mathit{k}}\in {\mathcal{G}}_{\mathit{t}}}\mathrm{(}{\mathit{f}}_{{\mathit{\sigma }}_{\mathit{t}}\mathrm{(}\mathit{j}\mathrm{)}}-{\mathit{p}}_{\mathit{k}}\mathrm{)}\end{array}$$ By utilizing Equations (3) and (4), the social welfare can be calculated as follows: $$\begin{array}{}\text{(5)}& \begin{array}{rl}{\mathit{SF}}_{\mathit{t}}& ={\mathit{H}}_{\mathit{p}}+{\displaystyle \sum }_{{\mathit{v}}_{\mathit{k}}\in {\mathcal{G}}_{\mathit{t}}}{\mathit{h}}_{\mathit{k}}\\ & ={\displaystyle \sum }_{{\mathit{v}}_{\mathit{k}}\in {\mathcal{G}}_{\mathit{t}}}\mathrm{(}{\mathit{f}}_{{\mathit{\sigma }}_{\mathit{t}}\mathrm{(}\mathit{k}\mathrm{)}}-\mathit{exps}\mathrm{(}\mathit{j}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}\mathrm{)}\end{array}\end{array}$$

3.2. Problem definition

Following the presentation of relevant symbols and definitions, we provide the definition of the problem that this paper addresses.

Definition 5 (SWMOM).

Given the set of vehicles ${\mathcal{V}}_{\mathit{t}}$ at time slice t and the set of orders ${\mathcal{O}}_{\mathit{t}}$ , S ocial W elfare M aximization O rder M atching (SWMOM) is to pair orders with vehicles for the purpose of maximizing the social welfare (as defined in Equation (5)) under the constraint of each vehicle’s trip plan remaining viable after order pairing process.

As discussed previously, our mechanisms need to satisfy these economic properties including individual rationality, profitability, truthfulness and computational efficiency. In more detail, we provide the formal definitions of these properties below.

Definition 6 (Individual rationality).

A mechanism is individual rational if the profit of each driver is non-negative, i.e., $\forall \mathit{k}\mathrm{,}{\mathit{h}}_{\mathit{k}}⩾0$ .

Definition 7 (Profitability).

A mechanism is profitable if the profit of the platform is non-negative, i.e., ${\mathit{H}}_{\mathit{p}}⩾0$ .

Definition 8 (Truthfulness).

A mechanism is truthful if the best strategy of any driver is to bid its expense truthfully, i.e., $\forall {\mathit{v}}_{\mathit{k}}\mathrm{,}{\mathit{h}}_{\mathit{k}}⩾\widehat{{\mathit{h}}_{\mathit{k}}}$ where $\widehat{{\mathit{h}}_{\mathit{k}}}=\widehat{{\mathit{p}}_{\mathit{k}}}-\mathit{exps}\mathrm{(}{\mathit{\sigma }}_{\mathit{t}}\mathrm{(}\mathit{k}\mathrm{)}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}$ is the profit when the driver bids untruthfully, in which $\widehat{{\mathit{p}}_{\mathit{k}}}$ is the payment and $\mathit{exps}\mathrm{(}{\mathit{\sigma }}_{\mathit{t}}\mathrm{(}\mathit{k}\mathrm{)}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}$ is the true expense of the driver.

Definition 9 (Computational efficiency).

A mechanism is computational efficient if the process of order pairing and pricing can be accomplished in a polynomial time.

4. SWMOM-VCG mechanism

In this section, we introduce a Vickrey–Clarke–Groves (VCG) inspired reverse auction mechanism for the SWMOM framework, named SWMOM-VCG. This mechanism consists of two distinct components: Order Pairing and Pricing, described in Algorithm 1. The order Pairing process is modeled as a bipartite graph Pairing and we utilize the VCG pricing method7

⁷

Vickrey–Clarke–Groves (VCG) [8,13,29] is widely recognized as a highly efficient auction mechanism where the participants reveal their information truthfully.

to calculate the payment received by the victorious driver. In the following, we will introduce Order Pairing and Pricing in detail respectively.

Algorithm 1

SWMOM-VCG mechanism

Order Pairing: In the beginning of Algorithm 1, the drivers’ bids in conjunction with the orders’ prepaid fares are used to construct a bipartite graph featuring two distinct sets of nodes symbolizing ${\mathcal{O}}_{\mathit{t}}$ and ${\mathcal{V}}_{\mathit{t}}$ respectively (lines 1∼2). The weight assigned to each edge corresponds to the partial social welfare derived from each pair $\mathrm{(}{\mathit{o}}_{\mathit{i}}\mathrm{,}{\mathit{v}}_{\mathit{j}}\mathrm{)}$ : $$\begin{array}{}\text{(6)}& \widehat{\mathit{sf}}\mathrm{(}\mathit{j}\mathrm{,}\mathit{k}\mathrm{)}={\mathit{f}}_{\mathit{j}}-\widehat{\mathit{exps}}\mathrm{(}\mathit{j}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}\end{array}$$ Note that the edges possessing negative weights are excluded from the bipartite graph. We use the notation $\widehat{\mathit{sf}}\mathrm{(}\mathit{j}\mathrm{,}\mathit{k}\mathrm{)}$ to denote the social welfare of the pair, assuming truthful bidding. Then, we incorporate the maximum weighted matching (MWM) algorithm [12] to maximize the social welfare for both the platform and the vehicle drivers (line 3).

Pricing: After pairing orders with drivers, the platform reuses the MWM algorithm to calculate the optimal social welfare, denoted as ${\mathit{SF}}_{-{\mathit{v}}_{{\mathit{k}}^{\ast }}}^{\ast }$ , when ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ is removed from the auction (lines 5∼11). The payment allocated to the victorious driver is expressed as: $$\begin{array}{}\text{(7)}& {\mathit{p}}_{{\mathit{k}}^{\ast }}=min\mathrm{(}{\mathit{p}}_{{\mathit{k}}^{\ast }}^{\mathrm{vcg}}\mathrm{,}{\mathit{f}}_{{\mathit{j}}^{\ast }}\mathrm{)}\end{array}$$ where ${\mathit{p}}_{{\mathit{k}}^{\ast }}^{\mathrm{vcg}}=\widehat{\mathit{exps}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}+\mathrm{(}{\mathit{SF}}_{\mathit{t}}^{\ast }-{\mathit{SF}}_{-{\mathit{v}}_{{\mathit{k}}^{\ast }}\mathrm{,}\mathit{t}}^{\ast }\mathrm{)}$ denotes the VCG price. The driver will receive the lesser value between the VCG price and the order’s prepaid fare as the payment (line 9).

Finally, the platform takes the unpaired orders that have not surpassed their maximum waiting time threshold (line 12) to the next time slice, and try to establish new pairs for these orders.

4.1. Theoretical analysis

In the following, we provide a formal proof that SWMOM-VCG satisfies the key properties of individual rationality, profitability, truthfulness and computational efficiency.

Theorem 1.

SWMOM-VCG guarantees individual rationality. Proof 1.

When ${\mathit{p}}_{{\mathit{k}}^{\ast }}^{\mathrm{vcg}}\mathrm{>}{\mathit{f}}_{{\mathit{j}}^{\ast }}$ , the profit of the driver ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ is ${\mathit{h}}_{{\mathit{k}}^{\ast }}={\mathit{f}}_{{\mathit{j}}^{\ast }}-\mathit{exps}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}=\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{k}}^{\ast }\mathrm{)}$ . Since the platform only takes non-negative weight $\widehat{\mathit{sf}}\mathrm{(}\mathit{j}\mathrm{,}\mathit{k}\mathrm{)}$ into consideration, we can get ${\mathit{h}}_{{\mathit{k}}^{\ast }}=\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{k}}^{\ast }\mathrm{)}⩾0$ . When ${\mathit{p}}_{{\mathit{k}}^{\ast }}^{\mathrm{vcg}}⩽{\mathit{f}}_{{\mathit{j}}^{\ast }}$ , according to Theorem 3, the profit of ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ is ${\mathit{h}}_{{\mathit{k}}^{\ast }}={\widetilde{\mathit{SF}}}_{\mathit{t}}-{\mathit{SF}}_{-{\mathit{v}}_{{\mathit{k}}^{\ast }}\mathrm{,}\mathit{t}}^{\ast }={\mathit{SF}}_{\mathit{t}}^{\ast }-{\mathit{SF}}_{-{\mathit{v}}_{{\mathit{k}}^{\ast }}\mathrm{,}\mathit{t}}^{\ast }$ . It is evident that we have ${\mathit{SF}}_{\mathit{t}}^{\ast }⩾{\mathit{SF}}_{-{\mathit{v}}_{{\mathit{k}}^{\ast }}\mathrm{,}\mathit{t}}^{\ast }$ , and ${\mathit{h}}_{{\mathit{k}}^{\ast }}⩾0$ can be derived. Therefore, SWMOM-VCG can guarantee individual rationality.

Theorem 2.

SWMOM-VCG guarantees profitability. Proof 2.

As defined in Equation (7), we can get that ${\mathit{p}}_{{\mathit{k}}^{\ast }}=min\mathrm{(}\widehat{\mathit{exps}}\mathrm{(}{\mathit{k}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}+\mathrm{(}{\mathit{SF}}_{\mathit{t}}^{\ast }-{\mathit{SF}}_{-{\mathit{v}}_{{\mathit{k}}^{\ast }}\mathrm{,}\mathit{t}}^{\ast }\mathrm{)}\mathrm{,}{\mathit{f}}_{{\mathit{j}}^{\ast }}\mathrm{)}⩽{\mathit{f}}_{{\mathit{j}}^{\ast }}$ . Therefore, the platform’s profit is non-negative, and thus SWMOM-VCG can guarantee profitability.

Theorem 3.

SWMOM-VCG guarantees truthfulness. Proof 3.

In this analysis, we establish that no driver can enhance their profit through the submission of an untruthful bid. When ${\mathit{p}}_{{\mathit{k}}^{\ast }}^{\mathrm{vcg}}\mathrm{>}{\mathit{f}}_{{\mathit{j}}^{\ast }}$ , the profit of ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ is ${\mathit{h}}_{{\mathit{k}}^{\ast }}={\mathit{f}}_{{\mathit{j}}^{\ast }}-\mathit{exps}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}$ . Since ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ cannot change ${\mathit{f}}_{{\mathit{j}}^{\ast }}$ , The individual is unable to enhance their profit by bidding untruthfully. When ${\mathit{p}}_{{\mathit{k}}^{\ast }}^{\mathrm{vcg}}⩽{\mathit{f}}_{{\mathit{j}}^{\ast }}$ , the profit of ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ is calculated as follows: $$\begin{array}{rl}{\mathit{h}}_{{\mathit{k}}^{\ast }}& ={\mathit{p}}_{{\mathit{k}}^{\ast }}^{\mathrm{vcg}}-\mathit{exps}\mathrm{(}{\mathit{k}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}\\ & =\widehat{\mathit{exps}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}+{\mathit{SF}}_{\mathit{t}}^{\ast }-{\mathit{SF}}_{-{\mathit{v}}_{{\mathit{k}}^{\ast }}\mathrm{,}\mathit{t}}^{\ast }-\mathit{exps}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}\\ & =\widehat{\mathit{exps}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}+{\mathit{f}}_{{\mathit{j}}^{\ast }}-\widehat{\mathit{exps}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}-\mathit{exps}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}\\ & +{\displaystyle \sum }_{{\mathit{v}}_{\mathit{k}}\in {\mathcal{G}}_{\mathit{t}}\setminus \{{\mathit{v}}_{{\mathit{k}}^{\ast }}\}}\mathrm{(}{\mathit{f}}_{{\mathit{\sigma }}_{\mathit{t}}\mathrm{(}\mathit{k}\mathrm{)}}-\widehat{\mathit{exps}}\mathrm{(}{\mathit{\sigma }}_{\mathit{t}}\mathrm{(}\mathit{k}\mathrm{)}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{\left)}\mathrm{\right)}-{\mathit{SF}}_{-{\mathit{v}}_{{\mathit{k}}^{\ast }}\mathrm{,}\mathit{t}}^{\ast }\\ & =\widetilde{{\mathit{SF}}_{\mathit{t}}}-{\mathit{SF}}_{-{\mathit{v}}_{{\mathit{k}}^{\ast }}\mathrm{,}\mathit{t}}^{\ast }\end{array}$$ where $\widetilde{{\mathit{SF}}_{\mathit{t}}}$ denotes the social welfare when the driver ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ bids $\widehat{\mathit{exps}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}=\mathit{exps}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}$ . Since ${\mathit{SF}}_{-{\mathit{v}}_{{\mathit{k}}^{\ast }}\mathrm{,}\mathit{t}}$ is independent of ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ ’s bid, ${\mathit{u}}_{{\mathit{k}}^{\ast }}$ is maximized when he obtains ${\mathit{\sigma }}_{\mathit{t}}\mathrm{(}{\mathit{k}}^{\ast }\mathrm{)}$ , which can maximize ${\mathit{SF}}_{\mathit{t}}$ , and can also maximize $\widetilde{{\mathit{SF}}_{\mathit{t}}}$ , i.e. $\widehat{\mathit{exps}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}=\mathit{exps}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}$ . Therefore, SWMOM-VCG can guarantee truthfulness.

Theorem 4.

SWMOM-VCG guarantees computational efficiency. Proof 4.

Here we analyze the time complexity of our mechanism as presented in Algorithm 1. In the beginning of the algorithm, it consumes $\mathcal{O}\mathrm{(}\mathit{m}\mathit{n}\mathrm{)}$ to construct a bipartite graph $\mathit{GH}$ , where $\mathit{m}=|{\mathcal{V}}_{\mathit{t}}|$ and $\mathit{n}=|{\mathcal{O}}_{\mathit{t}}|$ . In the Order Pairing phase, it consumes $\mathcal{O}\mathrm{(}{\mathit{\mu }}^3\mathrm{)}$ to maximize the pairing weight [12], where $\mathit{\mu }=max\mathrm{(}\mathit{m}\mathrm{,}\mathit{n}\mathrm{)}$ . In the Pricing phase, it consumes $\mathcal{O}\mathrm{(}\mathit{\iota }{\mathit{\mu }}^3\mathrm{)}$ to calculate the payments for all victorious drivers, where $\mathit{\iota }=min\mathrm{(}\mathit{m}\mathrm{,}\mathit{n}\mathrm{)}$ . Therefore, SWMOM-VCG can guarantee computational efficiency.

5. SWMOM-GM mechanism

While SWMOM-VCG can accomplish order pairing within polynomial time, the substantial time consumption associated with processing thousands of vehicles and incoming orders renders it unsuitable for ensuring real-time performance. Therefore we propose an enhanced mechanism, named SWMOM-GM, which incorporates a greedy method for order pairing and employs a critical value for driver payments. This mechanism, though more computationally efficient, may result in a minor reduction in the social welfare. Detailed in Algorithm 2, SWMOM-GM is composed of Order Pairing and Pricing components. In the following, we provide a detailed overview of Order Pairing and Pricing respectively.

Algorithm 2

SWMOM-GM mechanism

Order Pairing: In the beginning of Algorithm 2, the platform calculates the social welfare of each viable pair $\mathrm{(}{\mathit{o}}_{\mathit{j}}\mathrm{,}{\mathit{v}}_{\mathit{k}}\mathrm{)}$ utilizing Equation (6) and saves the non-negative weight $\widehat{\mathit{sf}}\mathrm{(}\mathit{j}\mathrm{,}\mathit{k}\mathrm{)}$ into a heap for the subsequent order pairing phase (lines 1 and 2). Following the initialization, the platform iteratively pairs orders with vehicles. During each iteration, the platform selects an optimal pairing pair $\mathrm{(}{\mathit{o}}_{{\mathit{j}}^{\ast }}\mathrm{,}{\mathit{v}}_{{\mathit{k}}^{\ast }}\mathrm{)}$ that has the maximum immediate social welfare (line 5). To achieve truthfulness, the platform will not pair ${\mathit{o}}_{{\mathit{j}}^{\ast }}$ with its monopoly vehicle.8

⁸

A vehicle is a monopoly vehicle for an order if this order is only bid by this vehicle.

This constraint on monopoly vehicles is crucial for ensuring truthfulness, as such vehicles could potentially submit arbitrarily low bids. If ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ is not ${\mathit{o}}_{{\mathit{j}}^{\ast }}$ ’s monopoly vehicle, the platform proceeds to pair ${\mathit{o}}_{{\mathit{j}}^{\ast }}$ with ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ (line 8).

Pricing: We calculate the critical value for ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ as his received payment. In this phase, the victorious vehicles are temporarily set aside and a process similar to Order Pairing is carried out over the remaining vehicles (lines 11∼25). For every pair $\mathrm{(}{\mathit{o}}_{{\mathit{j}}^{\prime }}\mathrm{,}{\mathit{v}}_{{\mathit{k}}^{\prime }}\mathrm{)}$ , the critical value can be calculated as ${\mathit{p}}_{{\mathit{k}}^{\ast }}^{\mathrm{cr}}={\mathit{f}}_{{\mathit{j}}^{\ast }}-\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}^{\prime }\mathrm{,}{\mathit{k}}^{\prime }\mathrm{)}$ . Note that if ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ bids more than ${\mathit{p}}_{{\mathit{k}}^{\ast }}^{\mathrm{cr}}$ to serve ${\mathit{o}}_{{\mathit{j}}^{\ast }}$ , ${\mathit{v}}_{{\mathit{j}}^{\ast }}$ will not replace ${\mathit{v}}_{{\mathit{j}}^{\prime }}$ as the victorious vehicle during this iteration. The maximum value among these critical values is assigned as the payment for ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ (line 18).

5.1. Theoretical analysis

In the following, we provide a proof that SWMOM-GM satisfies the properties of individual rationality, profitability, truthfulness and computational efficiency. Furthermore, we calculate the lower bound of the social welfare when utilizing SWMOM-GM in comparison to the optimal one.

Theorem 5.

SWMOM-GM guarantees individual rationality. Proof 5.

In SWMOM-GM, we assume ${\mathit{v}}_{{\mathit{k}}^{\ast }}\in {\mathcal{W}}_{\mathit{t}}$ obtains ${\mathit{o}}_{{\mathit{j}}^{\ast }}$ . There must be a pair $\mathrm{(}{\mathit{o}}_{{\mathit{j}}^{\ast }}\mathrm{,}{\mathit{v}}_{{\mathit{k}}^{\prime }}\mathrm{)}$ after $\mathrm{(}{\mathit{o}}_{{\mathit{j}}^{\ast }}\mathrm{,}{\mathit{v}}_{{\mathit{k}}^{\ast }}\mathrm{)}$ since ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ is not a monopoly vehicle for ${\mathit{o}}_{{\mathit{j}}^{\ast }}$ . Here, $\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{k}}^{\ast }\mathrm{)}⩾\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{k}}^{\prime }\mathrm{)}$ . Therefore we can get ${\mathit{p}}_{{\mathit{k}}^{\ast }}=max\{{\mathit{f}}_{{\mathit{j}}^{\ast }}-\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}^{\prime }\mathrm{,}{\mathit{k}}^{\prime }\mathrm{)}\}⩾{\mathit{f}}_{{\mathit{j}}^{\ast }}-\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{k}}^{\prime }\mathrm{)}⩾{\mathit{f}}_{{\mathit{j}}^{\ast }}-\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{k}}^{\ast }\mathrm{)}=\widehat{\mathit{exps}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}=\mathit{exps}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{{\mathit{k}}^{\ast }}\mathrm{)}$ . Therefore, SWMOM-GM can guarantee individual rationality.

Theorem 6.

SWMOM-GM guarantees profitability. Proof 6.

Since the platform only saves non-negative $\widehat{\mathit{sf}}\mathrm{(}\mathit{j}\mathrm{,}\mathit{k}\mathrm{)}$ (line 2), we can get $\widehat{\mathit{sf}}\mathrm{(}\mathit{j}\mathrm{,}\mathit{k}\mathrm{)}={\mathit{f}}_{\mathit{j}}-\widehat{\mathit{exps}}\mathrm{(}\mathit{j}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}⩾0$ . Since $\widehat{\mathit{exps}}\mathrm{(}\mathit{j}\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}⩾0$ , ${\mathit{p}}_{{\mathit{k}}^{\ast }}=max\{{\mathit{f}}_{{\mathit{j}}^{\ast }}-\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}^{\prime }\mathrm{,}{\mathit{k}}^{\prime }\mathrm{)}\}⩾0$ . Therefore, SWMOM-GM can guarantee profitability.

Theorem 7.

SWMOM-GM guarantees truthfulness. Proof 7.

We establish that no driver ${\mathit{v}}_{\mathit{k}}$ can achieve greater profits by submitting untruthful bids. We provide a step-by-step proof of the claim.

Case 1: ${\mathit{v}}_{\mathit{k}}$ always loses whether bidding truthfully nor not. According to Equation (3), we can get ${\mathit{u}}_{\mathit{k}}=0$ and thus ${\mathit{v}}_{\mathit{k}}$ cannot enhance ${\mathit{h}}_{\mathit{k}}$ by changing the bid.

Case 2: ${\mathit{v}}_{\mathit{k}}$ wins by bidding untruthfully but loses by bidding truthfully. When ${\mathit{v}}_{\mathit{k}}$ bids untruthfully, we assume that ${\mathit{v}}_{\mathit{k}}$ replaces ${\mathit{v}}_{{\mathit{k}}^{\ast }}$ to obtain ${\mathit{o}}_{{\mathit{j}}^{\ast }}$ with a payment ${\hat{\mathit{p}}}_{\mathit{k}}$ . Since ${\mathit{v}}_{\mathit{k}}$ who bids truthfully will lose in the auction, we have ${\widehat{\mathit{sf}}}^{\prime }\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}\mathit{k}\mathrm{)}⩾\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{k}}^{\ast }\mathrm{)}⩾\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}\mathit{k}\mathrm{)}$ , where ${\widehat{\mathit{sf}}}^{\prime }\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}\mathit{k}\mathrm{)}$ is the corresponding partial social welfare that ${\mathit{v}}_{\mathit{k}}$ can make when he bids on the expense of ${\mathit{o}}_{{\mathit{j}}^{\ast }}$ untruthfully. We can get ${\hat{\mathit{p}}}_{\mathit{k}}={\mathit{f}}_{{\mathit{j}}^{\ast }}-\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{k}}^{\ast }\mathrm{)}⩽{\mathit{f}}_{{\mathit{j}}^{\ast }}-\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}\mathit{k}\mathrm{)}=\mathit{exps}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}$ . Thus its profit is ${\mathit{u}}_{\mathit{k}}={\hat{\mathit{p}}}_{\mathit{k}}-\mathit{exps}\mathrm{(}{\mathit{j}}^{\ast }\mathrm{,}{\mathit{s}}_{\mathit{k}}\mathrm{)}⩽0$ .

Case 3: ${\mathit{v}}_{\mathit{k}}$ always wins in the auction and obtains the same order ${\mathit{o}}_{\mathit{j}}$ whether bidding truthfully or not. Clearly, we can see that from the Pricing process, the payment of ${\mathit{v}}_{\mathit{k}}$ is independent on his bid.

Case 4: ${\mathit{v}}_{\mathit{k}}$ always wins in the auction whether bidding truthfully or not, but obtains different orders. We assume that ${\mathit{v}}_{\mathit{k}}$ obtains ${\mathit{o}}_{\mathit{j}}$ when he bids truthfully and obtains ${\mathit{o}}_{\mathit{j}}^{\ast }$ when he bids untruthfully. According to Case 2 the order obtained by ${\mathit{v}}_{\mathit{k}}$ bidding untruthfully will result in a negative profit.

Based on the above analysis, it can be concluded that SWMOM-GM can guarantee truthfulness.

Theorem 8.

SWMOM-GM guarantees computational efficiency. Proof 8.

Here we analyze the time complexity of our mechanism as presented in Algorithm 2. In the beginning of Algorithm 2, it consumes $\mathrm{(}\mathit{O}\mathrm{)}\mathrm{(}\mathit{m}\mathit{n}log\mathrm{(}\mathit{m}\mathit{n}\mathrm{)}\mathrm{)}$ to save $\widehat{\mathit{sf}}\mathrm{(}\mathit{j}\mathrm{,}\mathit{k}\mathrm{)}$ into a heap, where $\mathit{m}=|{\mathcal{V}}_{\mathit{t}}|$ and $\mathit{n}=|{\mathcal{O}}_{\mathit{t}}|$ . In the Order Pairing phase, it consumes $\mathcal{O}\mathrm{(}\mathit{\iota }log\mathrm{(}\mathit{m}\mathit{n}\mathrm{)}\mathrm{)}$ to pair orders with vehicles, where $\mathit{\iota }=min\mathrm{(}\mathit{m}\mathrm{,}\mathit{n}\mathrm{)}$ . In the Pricing phase, it consumes $\mathcal{O}\mathrm{(}{\mathit{\iota }}^{2}log\mathrm{(}\mathit{m}\mathit{n}\mathrm{)}\mathrm{)}$ to calculate the payments received by all victorious drivers. Therefore, SWMOM-GM guarantees computational efficiency and has a better performance than SWMOM-VCG in terms of the time complexity.

Theorem 9.

The social welfare made in SWMOM-GM ${\mathit{SF}}_{\mathcal{S}}⩾\frac{1}{\mathit{\iota }}·{\mathit{SF}}_{{\mathcal{S}}^{\ast }}$ where ${\mathit{SF}}_{{\mathcal{S}}^{\ast }}$ is the social welfare made in the optimal pairing. Proof 9.

We use $\mathcal{S}$ and ${\mathcal{S}}^{\ast }$ denote the solutions (i.e. order pairing pairs) of SWMOM-GM and the optimal pairing respectively. The achieved social welfare can be represented as ${\mathit{SF}}_{\mathcal{S}}$ and ${\mathit{SF}}_{{\mathcal{S}}^{\ast }}$ respectively. We use $\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}_{\mathit{h}}\mathrm{,}{\mathit{k}}_{\mathit{h}}\mathrm{)}$ to represent the maximum social welfare of pair in $\mathcal{S}$ and use ${\widehat{\mathit{sf}}}^{\ast }\mathrm{(}\mathit{j}\mathrm{,}\mathit{k}\mathrm{)}$ to denote the social welfare of $\mathrm{(}{\mathit{o}}_{\mathit{j}}\mathrm{,}{\mathit{v}}_{\mathit{k}}\mathrm{)}\in {\mathcal{S}}^{\ast }$ . It is evident that ${\widehat{\mathit{sf}}}^{\ast }\mathrm{(}\mathit{j}\mathrm{,}\mathit{k}\mathrm{)}⩽\widehat{\mathit{sf}}\mathrm{(}{\mathit{j}}_{\mathit{h}}\mathrm{,}{\mathit{k}}_{\mathit{h}}\mathrm{)}⩽{\mathit{SF}}_{\mathcal{S}}$ and $|{\mathcal{S}}^{\ast }|⩽min\mathrm{(}|{\mathcal{O}}_{\mathit{t}}|\mathrm{,}|{\mathcal{V}}_{\mathit{t}}|\mathrm{)}=\mathit{\iota }$ . Therefore we can get ${\mathit{SF}}_{{\mathcal{S}}^{\ast }}={\sum }_{\mathrm{(}{\mathit{o}}_{\mathit{j}}\mathrm{,}{\mathit{v}}_{\mathit{k}}\mathrm{)}\in {\mathit{S}}^{\ast }}{\widehat{\mathit{sf}}}^{\ast }\mathrm{(}\mathit{j}\mathrm{,}\mathit{k}\mathrm{)}⩽\mathit{\iota }·{\mathit{SF}}_{\mathcal{S}}$ . As a result, ${\mathit{SF}}_{\mathcal{S}}⩾\frac{1}{\mathit{\iota }}·{\mathit{SF}}_{{\mathcal{S}}^{\ast }}$ .

6. Experimental evaluation

In this section, we conduct experiments to evaluate the performance of our mechanisms using the real taxi order data from New York city.9

⁹

https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page

6.1. Experimental setup

The data set used for evaluating our mechanisms is the Manhattan taxi order data set. The data set contains data of all days in June 2016. In order to avoid random disruption, instead of randomly running the experiments on the data of one day, we extract the fundamental characteristics of these data and then generate the data for running the experiments.10

¹⁰

In this paper, we try to evaluate our mechanisms in the realistic situations. Therefore, we will preprocess the data set and then obtain the characteristics of some necessary properties. We then generate the order data for experiments and consider different settings of order demands, under which we demonstrate the effectiveness of our mechanisms.

Fig. 3.

The number of orders on weekdays and weekends.

In Fig. 3, a huge difference is observed between the number of taxi orders on weekdays and weekends. Consequently, we exclude weekend order data, leaving 22 days for analysis. Subsequently, we obtain Manhattan’s road network data from Open Street Map, which is represented as a directed graph consisting of 4,490 vertices and 9,762 edges. Utilizing the k-means algorithm, we cluster departures and destinations from the order data and then divide Manhattan into distinct blocks, as illustrated in Fig. 4. This enables the generation of order data for conducting experimental evaluations. Moreover, to ascertain vehicle expenses, we gather fuel consumption data from the Ministry of Public Information and Communications of China.11

¹¹

http://www.miit.gov.cn/asopCmsSearch

Apart from the taxi order and fuel consumption data, several other parameters must be initialized, including seat capacity, average vehicle speed, maximum waiting time, maximum detour rate and the number of vehicles. The configurations for these parameters are provided in Table 2.

Fig. 4.

Dividing Manhattan into several blocks by clustering departure and destination regions from the order data.

Table 2

Parameter values

Parameters	Values
Seat Capacity $\mathrm{(}{\mathit{N}}_{\mathit{k}}\mathrm{)}$	4
Average Vehicle Speed $\mathrm{(}{\mathit{V}}_{\mathrm{ave}}\mathrm{)}$	12 (mph)
Maximum Waiting Time $\mathrm{(}{\mathit{t}}_{\mathit{j}}^{\mathit{w}}\mathrm{)}$	3, 4, 5, 6, 7, 8 (minutes)
Maximum Detour Rate $\mathrm{(}{\mathit{d}}_{\mathit{j}}\mathrm{)}$	0.25, 0.50, 0.75, 1.00
Number of Vehicles	$100\mathrm{,}200\mathrm{,}\dots \mathrm{,}900\mathrm{,}1000$

6.2. Benchmark approaches and metrics

In order to show the effectiveness of our mechanisms, we intend to evaluate them by considering different demanding situations. Specifically, we consider three different time windows, i.e. 4:00 am–5:00 am, 4:00 pm–5:00 pm and 9:00 pm–10:00 pm, corresponding to low, medium and high riding demands. The amount of orders in 9:00 pm–10:00 pm is the largest in the day, and the amount of orders in 4:00 am–5:00 am is the smallest and the amount of orders in 4:00 pm–5:00 pm is at a medium level. In each time window, we assign one minute to each time slice. If an order remains unserved in the current time slice, it is postponed to the next time slice. An order is removed from consideration if it has surpassed its maximum waiting time. Vehicles with unaccomplished orders trip according to their trip plans, while idle vehicles randomly navigate to explore potential passenger opportunities.

Our experimental evaluation compares the performance of our proposed mechanisms, namely SWMOM-VCG and SWMOM-GM, with that of Nearest-Pairing and SPARP [3]. In Nearest-Pairing, an incoming order is paired with the nearest available vehicle. We selected this pairing method owing to its widespread usage in major ride-sharing platforms like Uber [2]. SPARP, on the other hand, is a state-of-art approach for pairing orders with vehicles. This method explores all viable route plans to identify the optimal plan whenever a new order is integrated into the trip plan.

We conduct experimental evaluations of our mechanisms, considering varying numbers of vehicles in different time windows. Our evaluation criteria include six metrics, namely: social welfare, which represents the sum of driver and platform profits; rate of served orders, which denotes the proportion of successfully paired orders to the total number of orders; social cost, referring to the total cost of driver services; profit of the platform; total profits of drivers; and total payments to drivers.

Fig. 5.

Results of low demands (4:00 am–5:00 am), where we can find that the social welfare of all approaches, except Nearest Pairing, increases as the number of vehicles rises. Furthermore, we can see that the profit of the platform in SWMOM-VCG is relatively lower and the profits of drivers are higher than SWMOM-GM.

Fig. 6.

Results of medium demands (4:00 pm–5:00 pm), where we can find that all metrics increases since the amount of orders increases and SWMOM-VCG can make a better social welfare than another three approaches.

Fig. 7.

Results of peak demands (9:00 pm–10:00 pm), which is similar to Fig. 6.

6.3. Experimental results

We conduct experiments with varying numbers of vehicles, repeating each experiment 100 times with randomly sampled parameters. The average value of each metric is then computed. The results of these experiments for different time windows, namely 4:00 am–5:00 am, 4:00 pm–5:00 pm and 9:00 pm–10:00 pm, are shown in Figs 5, 6 and 7, with the x-axis representing the changing number of vehicles and the y-axis representing the relevant metric. Additionally, we conduct an extra experiment during the high-demand period of 9:00 pm–10:00 pm to evaluate actual runtime. This experiment is carried out using a configuration of macOS Mojave 10.14.5, Intel Core i5 2.3 GHz, and 8G RAM.

Figure 5 presents the experimental results of serving orders with low demands, spanning the time window of 4:00 am–5:00 am. As shown in Fig. 5(a), the social welfare of all approaches, except Nearest Pairing, increases as the number of vehicles rises. This is attributed to the concurrent increase in the total number of served orders, as shown in Fig. 5(b). However, because of low riding demands, we can see that the growth of the social welfare becomes slower with the increased number of vehicles. Furthermore, we can see that although the rate of served orders of Nearest Pairing is high (as shown in Fig. 5(b)), its social welfare increases first with the initially increased number of vehicles, and then decreases. This is because on one hand, Nearest Pairing cannot guarantee efficient pairing but just pair order with the nearest vehicle, which results in low social welfare for each pair, and on the other hand, some vehicles cannot obtain orders and have to randomly travel to search for potential passengers, which results in increased social costs (as shown in Fig. 5(c)). Both facts cause the decreased social welfare of Nearest Pairing when there exist over enough vehicles serving riding orders. We also find that SWMOM-VCG achieves comparable social welfare to that of SPARP, albeit with a marginally lower rate of served orders. Additionally, we can see that SWMOM-GM demonstrates only slightly lower social welfare and served order rates compared to SWMOM-VCG. However, SWMOM-GM can be executed with significantly less computation time than SWMOM-VCG (this will be explained later on).

Our analysis will now turn to the examination of the profit made by the platform and the vehicle drivers. Note that there is no pricing method in the Nearest Pairing, and therefore we can not compute the payments to drivers and the profits of the platform and drivers. That’s why we can only show the results of our mechanisms and SPARP in Figs 5(d), 5(f) and 5(e). We find that the profit of the platform in SWMOM-VCG is relatively lower and the profits of drivers are higher than SWMOM-GM. This is because the VCG pricing method in SWMOM-VCG makes a higher payment to drivers.

We now run experiments by considering medium riding demands (time window 4:00 pm–5:00 pm) and peak riding demands (time window 9:00 pm–10:00 pm). The experiments results are shown in Figs 6 and 7. We can find that compared to Fig. 5, all metrics increase since the amount of orders increases. Because there exist enough riding orders, the social welfare of Nearest Pairing also keeps increasing compared to Fig. 5(a). Furthermore, we can find that SWMOM-VCG can make a better social welfare than another three approaches.

Finally, we analyze the running time in the peak time windows, which is shown in Fig. 8. The running time of SWMOM-VCG is the largest compared to the other approaches, and SWMOM-GM takes significantly less computation than SPARP and SWMOM-VCG. Note that in our experimental analysis, although SPARP can make a good social welfare, its computation cost is heavy. The reason for the increased time consumption lies in the fact that, during the insertion of a new order, the routing algorithm employed by SPARP must systematically enumerate all possible route plans in order to identify the optimal one, which may require the adjustment of the original trip plan. Consequently, this process can result in a longer duration for the overall routing operation. Moreover, adjusting the original route plan to find the optimal one may harm the rights of some currently served passengers.

Fig. 8.

Running time of peak demand period, where we can see that SWMOM-GM based on a greedy manner takes significantly less computation than SPARP and SWMOM-VCG.

In general, from the above experimental results, we can see that SPARP gives more profits to drivers (make more payments to drivers) which causes the sacrifice of profit of the platform. Profits of drivers and payments to drivers in SWMOM-VCG are higher than those in SWMOM-GM since VCG pricing method make higher payments to drivers. For the social cost, we can find that the social cost of Nearest Pairing is the highest since it just pair order with the nearest vehicles. Although SWMOM-VCG achieves the maximum social welfare, SWMOM-GM exhibits superior computational efficiency, albeit at a slight reduction in the social welfare.

7. Conclusion and future work

This paper proposes two auction-based mechanisms, SWMOM-VCG and SWMOM-GM, designed to pair riding orders with vehicles in order to maximize the social welfare of both the ride-sharing platform and vehicle drivers. We provide theoretical proofs demonstrating that these mechanisms hold desirable properties, including individual rationality, profitability, truthfulness and computational efficiency. Additionally, we conducted extensive experiments using real taxi order data from New York City and compared the performance of our mechanisms against several benchmark approaches in various demand scenarios. The experimental results illustrate that our mechanisms achieved good performance in terms of social welfare. Furthermore, we found that SWMOM-GM outperforms SWMOM-VCG in terms of computational efficiency with only a slight decrease in social welfare. It is important to note that we do not consider long-term social welfare in this paper. The order pairing results in the current time slice may impact future pairing results, demand and supply. In the future, we plan to incorporate this factor into our models. Additionally, free vehicles currently randomly travel, but in future work, we aim to consider the dispatching of idle vehicles to reduce social costs.