Malcolm Egan

Nir Oren

Michal Jakob

Hybrid Mechanisms for On-Demand Transport

Keywords: On-demand transport, taxis, pricing

Market mechanisms are now playing a key role in allocating and pricing on-demand transportion services. In practice, most such services use posted-price mechanisms, where both passengers and drivers are offered a journey price which they can accept or reject. However, providers such as Liftago and GrabTaxi have begun to adopt a mechanism whereby auctions are used to price drivers. These latter mechanisms are neither postedprice nor classical double auctions, and can instead be considered a hybrid mechanism. In this paper, we describe and study the properties of a novel hybrid on-demand transport mechanism. As these mechanisms require knowledge of passenger demand, we analyze the data-profit tradeoff as well as how passenger and driver preferences influence mechanism performance. We show that the revenue loss for the provider scales with √ n log n for n passenger requests under a multi-armed bandit learning algorithm with beta distributed preferences. We also investigate the effect of subsidies on both profit and the number of successful journeys allocated by the mechanism, comparing these with a posted-price mechanism, showing improvements in profit with a comparable number of successful requests.

I. INTRODUCTION

An important component of the transportation infrastructure in any city is on-demand or demand-responsive transport. As the name suggests, the timetable and route of these services are not fixed, contrasting with the operation of most trains and buses. As such, on-demand transport (ODT) is useful for last mile transportation-from hubs to residences-and also for areas with low populations or passengers with special needs (e.g., the elderly and disabled) [START_REF] Cordeau | The dial-a-ride problem: models and algorithms[END_REF].

ODT services can be not-for-profit, municipality funded, or profit driven. Although all types of services are often present in a city, they face different challenges. In particular, the routing and scheduling problems (where to go and when to pick up each passenger) in-typically small-scale-not-forprofit services are typically solved in a centralized manner and aim to minimize costs [START_REF] Cordeau | The dial-a-ride problem: models and algorithms[END_REF]- [START_REF] Kümmel | Framework for automated taxi operation: the family model[END_REF]. This is due to long-term revenue guarantees from the municipality or local government.

On the other hand, profit-driven ODT services have traditionally been dominated by taxis. Here, revenue from each passenger must be accounted for in routing and scheduling. Moreover, the taxi company and drivers have a restricted ability to optimize pricing, due to regulation [START_REF] Yang | A multiperiod dynamic model of taxi services with endogenous service intensity[END_REF]- [START_REF] Yang | Nonlinear pricing of taxi services[END_REF]. As such, factors such as how each passenger is priced, how much each driver is paid, where taxis wait, and which passengers they M. Egan is with the CITI Lab, 69621 Villeurbanne, France which is a joint laboratory in Université de Lyon, INSA-Lyon, and INRIA (e-mail: malcom.egan@inria.fr). During the preparation of this paper he was also with the Faculty of Electrical Engineering, Czech Technical University in Prague. N. Oren is with the Department of Computing Science, University of Aberdeen (e-mail: n.oren@abdn.ac.uk). M. Jakob is with the Faculty of Electrical Engineering, Czech Technical University in Prague (e-mail: michal.jakob@agents.fel.cvut.cz).

pick-up play an important role both for minimizing passenger waiting times and fares, and for improving the profits of each driver and the taxi company. Optimizing pricing, scheduling, and routing in this environment is challenging, although significant progress has been made under the assumption of slowly time-varying pricing, where the problem can be reduced to a minimum cost scheduling and routing problem [START_REF] Glaschenko | Multiagent real time scheduling system for taxi companies[END_REF], [START_REF] Bai | A novel approach to independent taxi scheduling problem based on stable matching[END_REF], [START_REF] Yang | A multiperiod dynamic model of taxi services with endogenous service intensity[END_REF]- [START_REF] Ta | An efficient ridesharing framework for maximizing shared route[END_REF].

Recently, ODT providers such as UberX1 have been using machine learning techniques to improve routing, scheduling and pricing. In contrast with taxi companies, these ODT providers exploit market mechanisms to price and allocate passengers and drivers. In this case, studied in [START_REF] Egan | A double auction mechanism for on-demand transport networks[END_REF]- [START_REF] Kleiner | A mechanism for dynamic ride sharing based on parallel auctions[END_REF], up-front prices can be set using information gleaned from large amounts of data (e.g., collected via smartphone apps), and can be dynamically adjusted to account for time, supply and demand, and pick-up and drop-off locations-a significant departure from the static approaches used by traditional taxis.

The use of market mechanisms for pricing and allocation [START_REF] Shoham | Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations[END_REF]- [START_REF] Nisan | Algorithmic Game Theory[END_REF] is raising new challenges for the design of ODT systems. In particular, modern ODT providers are using a range of market mechanisms, not limited to the posted-price approach [START_REF] Borgs | Optimal multiperiod pricing with service guarantees[END_REF], [START_REF] Kleinberg | The value of knowing a demand curve: bounds on regret for online posted-price auctions[END_REF]- [START_REF] Besbes | Dynamic pricing without knowing the demand function: risk bounds and near-optimal algorithms[END_REF] currently adopted by Uber, where passengers and drivers are offered prices that they can accept or reject. For example, Liftago2 has adopted a hybrid mechanism where the payment received by drivers is determined by an auction and the price paid by passengers is determined by a posted-price mechanism. At present, it is not clear how to determine which mechanism is best suited to each city and scale of provider, beyond financially risky real-world experimentation.

There are two main approaches to study market design for on-demand transport. The first relies on tools from economics in the form of equlibrium analysis. In particular, equilibrium conditions have been derived and solutions studied in work such as [START_REF] Yang | Equilibrium properties of taxi markets with search frictions[END_REF], [START_REF] Wang | Pricing strategies for a taxi-hailing platform[END_REF]- [START_REF] Djavadian | An agent-based day-to-day adjustment process for modeling 'Mobility as a Service' with a two-sided flexible transport market[END_REF]. The main conclusions from this analysis are structural properties of the relationship between market supply and demand in the aggregate; that is, equilibrium behavior of passengers and drivers. While this analysis yields useful high-level insights for regulators, it is not presently possible to use these frameworks to optimize the market mechanism itself for individual providers. However, we note that the simulation-based method to study stochastic user equilibria accounting for within-day operating policies in [START_REF] Djavadian | An agent-based day-to-day adjustment process for modeling 'Mobility as a Service' with a two-sided flexible transport market[END_REF] appears promising in this respect.

The second approach is to develop and compare particular market mechanisms over fixed periods of time, using agent-based modeling approaches. These mechanisms usually take the form of posted-price approaches, and here, several mechanisms have been proposed [START_REF] Yang | A multiperiod dynamic model of taxi services with endogenous service intensity[END_REF], [START_REF] Gan | Optimizing efficiency in taxi systems: scaling-up and handling arbitrary constraints[END_REF], [START_REF] Gan | Optimal pricing for improving efficiency of taxi systems[END_REF], [START_REF] Borgs | Optimal multiperiod pricing with service guarantees[END_REF], [START_REF] Egan | A double auction mechanism for on-demand transport networks[END_REF]- [START_REF] Kleiner | A mechanism for dynamic ride sharing based on parallel auctions[END_REF], [START_REF] Egan | A profit-aware negotiation mechanism for on-demand transport services[END_REF], [START_REF]Market mechanism design for profitable on-demand transport services[END_REF]. Typically, these approaches either assume passengers will accept all journeys at a given price or rely on passengers and drivers truthfully revealing their preferences in the form of maximum prices, waiting times and other factors such as vehicle type (e.g., [START_REF] Gan | Game theoretic considerations for optimizing taxi system efficiency[END_REF]- [START_REF] Kleiner | A mechanism for dynamic ride sharing based on parallel auctions[END_REF]). The assumption that passengers are willing to reveal the maximum price they are prepared to pay is problematic, as often passenger preferences are not well-defined as this is not the way ODTs are currently used. Nevertheless, market mechanisms that assume that passengers and drivers have private price preferences is currently limited to [START_REF] Egan | A double auction mechanism for on-demand transport networks[END_REF]- [START_REF] Zeng | Dynamic taxi pricing[END_REF], [START_REF] Egan | A profit-aware negotiation mechanism for on-demand transport services[END_REF]- [START_REF] Zhou | An efficient double auction mechanism for ondemand transport services in cloud-based mobile commerce[END_REF].

In this paper, we introduce a new hybrid mechanism for ODT services to resolve the tension between supply and demand, where passengers are offered a price they can accept or reject and driver payments and allocations are determined by an auction. That is, like [START_REF] Egan | A double auction mechanism for on-demand transport networks[END_REF]- [START_REF] Zeng | Dynamic taxi pricing[END_REF], [START_REF] Egan | A profit-aware negotiation mechanism for on-demand transport services[END_REF]- [START_REF] Zhou | An efficient double auction mechanism for ondemand transport services in cloud-based mobile commerce[END_REF], passengers and drivers are not required to perfectly reveal their price preferences. Moreover, we do not assume that passengers are prepared to bid (e.g., [START_REF] Egan | A double auction mechanism for on-demand transport networks[END_REF], [START_REF] Zhang | A discounted trade reduction mechanism for dynamic ridesharing pricing[END_REF], [START_REF] Zhou | An efficient double auction mechanism for ondemand transport services in cloud-based mobile commerce[END_REF]) nor that drivers receive a salary (as in [START_REF] Zeng | Dynamic taxi pricing[END_REF], [START_REF] Egan | A profit-aware negotiation mechanism for on-demand transport services[END_REF], [START_REF]Market mechanism design for profitable on-demand transport services[END_REF]).

There are two key questions that we address: (1) how does the availability of data affect the price that should be offered by the service? and (2) how do passenger and driver cost and profit preferences affect the performance of the mechanism? The first question concerns data availability, taking into account the possibility of offering cheaper fares to obtain more information about passenger pricing preferences. It has a direct influence on the effectiveness of the machine learning techniques used to optimize pricing and allocation within the mechanism. This also includes algorithms that are used to estimate demand and trip information [START_REF] Balan | Real-time trip information service for a large taxi fleet[END_REF], [START_REF] Guo | Understanding ride-on-demand service: demand and dynamic pricing[END_REF]- [START_REF] Moreira | Predicting taxi-passenger demand using streaming data[END_REF] as well as market formation [START_REF] Brooks | Congregating and market formation[END_REF], which determines which passengers can be allocated to each driver. In contrast, the second question considers properties which the mechanism cannot control, as such driver and passenger preferences are determined a priori due to social, cultural and geographic factors; including the presence of consumer habits [START_REF] Verplanken | Interventions to break and create customer habits[END_REF].

To evaluate our hybrid mechanism, we develop an agentbased model which captures preferences of individual passengers with respect to journey prices, and drivers with respect to their minimum profit requirements per journey. Our model can be viewed as an extension of [START_REF] Egan | A double auction mechanism for on-demand transport networks[END_REF], [START_REF]Market mechanism design for profitable on-demand transport services[END_REF] where both passengers and drivers are self-interested. We formally demonstrate several properties of the hybrid mechanism, including truthfulness of passenger and driver reports, tradeoffs between profit and historical data available to the provider, and the impact of preferences on provider profit.

We also propose two variations on the hybrid mechanism to improve the proportion of passengers that are transported by a driver (which we refer to as the mechanism's efficiency). That is, both the passenger accepts the price offered by the mechanism and there is a driver willing to transport the passenger. These variations are inspired by the social planning perspective in auctions [START_REF] Wang | Auctions versus posted-price selling[END_REF] and incorporate variations in the prices passengers are prepared to pay and subsidies to incentivize drivers to transport each passenger.

Ultimately, the performance of a mechanism for an ODT system depends on the long-term behavior of the mechanism, accounting for the system's spatial-temporal profile. In particular, the spatial distribution of passenger requests, where drivers without passengers wait, and the passenger drop-off locations all affect key system metrics, namely the profit of the provider, the prices passengers pay, and the daily profits of drivers. As such, we provide a system-level evaluation of our hybrid mechanism and compare it to existing mechanisms for taxis as well as a two-sided posted-price mechanism inspired by the approach adopted by Uber. We show that the hybrid mechanism can significantly outperform a twosided posted-price mechanism in terms of the profit, while maintaining comparable success rates. We also investigate provider subsidies, which further improve the success rate at the cost of a lower profit. The remainder of this paper is organized as follows. In Section II, we detail our system model. In Section III, we apply this model to existing ODT services, providing us with a basis for comparison. Section IV, introduces the proposed hybrid mechanism, and in Section V, we analyze the hybrid mechanism to investigate tradeoffs between the quantity of data and imperfect knowledge of system parameters on the profit. In Section VI, two variations on the hybrid mechanism to vary the tradeoff between profit and proportion of passengers successfully transported are proposed. In Section VII, we explain our simulation setup and investigate the effect of system parameters on profit and success rate for the hybrid mechanism, a two-sided posted-price mechanism and the traditional dispatcher taxi model. In Section VIII, we summarize our work and consider future extensions.

II. SYSTEM MODEL

In this section, we develop an agent-based model for the ODT system which forms a basis for our hybrid mechanism in Section IV. We consider an ODT system consisting of a provider (responsible for pricing passengers and matching these with drivers), d vehicles/drivers who each service a single passenger at a time (i.e., ridesharing is not supported), and n passengers that enter the system at different times.

A. Passenger Agent Model

A new passenger enters the system when she makes a journey request to the ODT provider, which consists of a pickup time, pick-up location and drop-off location. We assume that each passenger wishes to be picked up as soon as possible after she makes her request, with maximum delay of ∆ minutes. The pick-up and drop-off locations are represented by elements from the set of vertices V in the directed graph G = (V, E), which models the underlying road network. The set of edges E in the graph represent direct routes between locations in V that can be traversed by the vehicles. Associated to each edge e ∈ E are a start and end location u, w ∈ V respectively; a cost c e ∈ [0, ∞) for a vehicle to traverse edge e; and a traversal time τ e ∈ Z + .

The cost of traversing an edge is incurred due to factors such as fuel consumption and vehicle wear and tear. We assume that the edge cost c e and traversal time τ e are computed offline by solving the shortest path problem between u and w in the underlying road network.

Each passenger has a maximum price she is prepared to pay for her journey, which is private and unknown to the provider. The maximum price is determined by the maximum pricerate that the passenger is prepared to pay (in, for example, euros per kilometer) and the distance the passenger seeks to travel. Let R i denote the distance that passenger i seeks to travel, then the total price she is willing to pay for her journey is p i,max = r i,max R i , where r i,max is the passenger's maximum price-rate. Since R i is known to both passenger i and the provider, it follows that the passenger's preferences are completely characterized by the maximum price-rate r i,max . As such, if a passenger is offered a journey with price-rate r i ≤ r i,max it will be accepted and if r i > r i,max the offer will be rejected (assuming that they can be picked up for the journey within ∆ minutes).

We model the maximum price-rate for each passenger as an independently and identically distributed (i.i.d) random variable, which captures differences in how much each passenger is prepared to pay. Following [START_REF]Market mechanism design for profitable on-demand transport services[END_REF], we assume that r i,max is beta distributed with probability density function (pdf)

f rmax (x) = 1 ρ max B(α r , β r ) x ρ max αr-1 1 - x ρ max βr-1 (1)
where B(α r , β r ) = Γ(αr)Γ(βr) Γ(αr+βr) is the beta function and Γ(•) is the gamma function. As such, the maximum price-rate is influenced by the three parameters α r , β r , ρ max , where α r , β r affect the shape of the pdf and ρ max determines the support of the pdf [0, ρ max ].

The choice of the beta distribution to model passenger price preferences can be justified by the flexibility arising from the three parameters and its tractability. We also remark that the beta distribution has also been applied to model revenue in economics (see, e.g., [START_REF] Parker | The generalised beta as a model for the distribution of earnings[END_REF]) and that the parameters can be readily estimated using via techniques such as maximum likelihood and method of moments [START_REF] Bury | Statistical Distributions in Engineering[END_REF]. Variations in the parameters can arise due to changes in perceived supply and demand (i.e., the number of available taxis and the number of passenger requests) or social, cultural and spatial-temporal differences (such as time of day) between passengers.

B. Driver Agent Model

Drivers also have preferences for the minimum payment they are prepared to receive for transporting passengers. Driver j's profit from transporting passenger i is given by

S j,i = (1 -η j )r i R i -c j,i (2)
where η j is the proportion of the passenger's payment sent to the provider and c j,i is the cost of transportation. In particular,

c j,i = κ j (R i + R j,i ) (3)
where κ j is the cost per kilometer incurred by the driver and R j,i denotes the distance from driver j's initial location to passenger i's pick-up location.

Let S j,min denote the minimum profit per minute driver j is prepared to receive for a journey. We assume that driver j is only willing to transport passenger i if

S j,i ≥ S j,min τ j,i (4)
where τ j,i is the duration of travel from driver j's initial location and passenger i's drop-off location. As such, both the journey distance and duration are accounted for by the driver.

As for each passenger's price-rate, we assume that S j,min is an i.i.d beta distributed random variable (albeit with different parameters) with pdf given by

f Smin (x) = 1 σ max B(α d , β d ) x σ max α d -1 1 - x σ max β d -1 (5)
where α d , β d are the shape parameters and the support is [0, σ max ]. These parameters are affected by variations in perceived supply and demand or spatial-temporal differences between drivers.

We assume that the provider is aware of which drivers are available and which are busy at all times. This information can either be obtained directly from driver reports or a notification from passengers being transported.

C. Provider Agent Model

The ODT provider runs the mechanism that prices and allocates passengers and drivers. In return, the provider receives a proportion of each passenger's payment. In particular, the provider receives η j r i R i for passenger i when served by driver j, which corresponds to the fraction of the passenger's payment not given to driver j in exchange for transportation.

To perform pricing and allocation, the provider exploits statistical knowledge of passenger preferences for the pricerate and driver preferences for their minimum profit. This statistical knowledge corresponds to the parameters α r , β r , ρ max and α d , β d , σ max which must be learned from historical transactions. When learned, such parameters will typically be imperfect due to, for example, limited data or non-stationarity of passenger preferences. To distinguish between the actual pdfs for the preferences, f rmax , f Smin , and the statistical knowledge of the provider, we denote the estimated pdfs as frmax with parameters αr , βr , ρmax and fSmin with parameters αd , βd , σmax , respectively.

In the following sections, we overview the evolution of existing ODT mechanisms and introduce a hybrid mechanism which exploits techniques from the theory of online mechanisms to obtain parameters for the preference pdfs.

III. MODELING EXISTING ODT MECHANISMS

In order to motivate the design of our hybrid mechanism, we overview existing mechanisms in ODT. We formalize each mechanism within the context of the model detailed in Section II, which allows us to form a basis for comparison with our proposed hybrid mechanism.

Historically, the dispatcher and Hackney carriage mechanisms were the first mechanisms used to price and allocate passengers in ODT systems. In the absence of smartphone apps, it was difficult for providers, drivers and passengers to effectively characterize the spatial-temporal properties of the system and to communicate with each other.

In the Hackney carriage mechanism, passengers communicate with drivers by hailing from the side of the road, which only allowed passengers to select from drivers within a distance of approximately 100 meters of their pick-up location. Passengers' prices are set by the driver based on a combination of experience, provider requirements, and regionspecific regulations. Payments to a provider (which is often some licensing authority) by drivers are set either in terms of a percentage commission for each journey or a fixed amount paid on a regular basis (e.g., monthly).

The limited choice of drivers for passengers to select is partly resolved by the dispatcher mechanism. In particular, passengers are able to call a provider who then forwards their request to a larger number of drivers within their region, often via a radio network. A driver is then selected based on a heuristic rule implemented by the provider. However, the heuristic does not usually include any information about the price the driver intends to offer the passenger as this information is not available to the provider. Pricing is therefore performed in a similar fashion to the Hackney carriage mechanism.

It is informative to formalize the pricing algorithm used in the Hackney carriage and dispatcher mechanisms in the case where the provider seeks to maximize its profit. Without historical data, the provider can set prices based only on average properties of the ODT system, including driver travel distances and durations, how drivers are selected, minimum profit targets, and maximum prices that passengers will pay.

An example of a model based on the average properties of the ODT system has been proposed in [START_REF] Yang | A multiperiod dynamic model of taxi services with endogenous service intensity[END_REF], [START_REF] Yang | Demand-supply equilibrium of taxi services in a network under competition and regulation[END_REF]. In this model, the average waiting time is given by

W = ω pN T -DL γ (6)
where ω depends on the density of taxi stands, p is the proportion of available taxis, N T is the total number of taxis, γ is the average number of passengers per journey, L is the average travel time, and D is the average number of passengers served by the whole taxi system. As such, pN T -DL γ represents the average number of available taxis. This kind of model forms the basis of optimization problems to maximize revenue and the number of served passengers [START_REF] Yang | A multiperiod dynamic model of taxi services with endogenous service intensity[END_REF], [START_REF] Yang | Demand-supply equilibrium of taxi services in a network under competition and regulation[END_REF]. In particular, the average monetary and time cost of a trip in time period i is given by

D i (F i , L i , W i ) = D i exp β F i γ + ψ 1 L i + ψ 2 W i (7)
where F i is the average fare price, L i is the average travel time, W i is the average waiting time given by ( 6), β > 0 is a sensitivity parameter, and ψ 1 , ψ 2 are parameters used to convert time costs into monetary costs. Often this approach is studied within the framework of multiperiod pricing [START_REF] Yang | A multiperiod dynamic model of taxi services with endogenous service intensity[END_REF], [START_REF] Borgs | Optimal multiperiod pricing with service guarantees[END_REF] however, it is not able to capture the individual private preferences of passengers and drivers. On the other hand, within our model detailed in Section II, the Hackney carriage and taxi mechanisms can be formalized as follows. Consider passenger i and driver j, with prices set via the optimization problem

max ri,ηj E Ri,Rj,i,τj,i,κj r i R i η j P S j,min τ j,i + κ j (R i + R j,i ) 1 -η j ≤ rR i ≤ r i,max R i (8)
Intuitively, this optimization problem maximizes the expected profit from each passenger request over all possible distances and duration R i , R j,i , τ j,i , κ j . To see this, observe that the probability that both passenger i and driver j accept their prices is given by

P (S j,min τ j,i ≤ (1 -η j )r i R i -κ j (R i + R j,i ), r i ≤ r i,max ) (9)
Since the provider receives a profit of η j r i R i , it follows by rearranging that the expected profit is precisely the objective in [START_REF] Dumas | The pickup and delivery problem with time windows[END_REF], where we have accounted for the probability that both the passenger and driver accept the prices (the provider receives nothing if one or both reject their offer).

In general, the problem in ( 8) cannot be solved directly due to the intractability of the distributions involved and limited knowledge of the distributions of S j,min and r i,max . As such, one approach to set prices is to decouple the passenger and driver pricing subproblems, which leads to the choices of

r H,i = arg max r E Ri [rR i P(r ≤ r i,max )] η H,j = arg max η E Ri,Rj,i,τj,i,κj ηP S j,min + κ j (R i + R j,i ) 1 -η ≤ r i R i (10)
As for [START_REF] Dumas | The pickup and delivery problem with time windows[END_REF], prices in [START_REF] Yang | A multiperiod dynamic model of taxi services with endogenous service intensity[END_REF] are averaged over distance and duration parameters. This means that the prices are not dynamically adjusted depending on the real-time state of the ODT system. We remark that a multiperiod model based on (6) has also been proposed in [START_REF] Gan | Optimizing efficiency in taxi systems: scaling-up and handling arbitrary constraints[END_REF], [START_REF] Gan | Optimal pricing for improving efficiency of taxi systems[END_REF], [START_REF] Gan | Game theoretic considerations for optimizing taxi system efficiency[END_REF], which also accounts for strategic behavior of drivers, and which considered two additional constraints, namely: the driver does not work for more than n w periods; and that the driver does not work continuously for more than n c periods. This leads to a noncooperative game model, where the Nash equilibrium [START_REF] Shoham | Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations[END_REF] is obtained via a bilevel optimization problem. Despite accounting for multi-period pricing and driver strategy constraints, it is important to note that the model still relies on the average behavior of passengers and drivers. This is in contrast with our model that accounts for the presence of private individual preferences of each passenger and driver.

With the introduction of smartphone apps, it is now possible to exploit large data sets to price and allocate passengers and drivers. One method is to use a posted-price mechanism approach for both passengers and drivers. In this two-sided posted-price mechanism, the provider sets a single price for all passengers and a single price (in, for example, euros/km) for all drivers in a given region at a given time. Moreover, the mechanism can also account for the locations of passengers and drivers as well as instantaneous supply (availability of drivers) and demand (number of passenger requests).

In contrast with the Hackney carriage and dispatcher mechanisms, the two-sided posted-price mechanism optimizes prices based on the instantaneous properties of the ODT system. In the case that the provider only considers its profits, a natural choice of prices is

r D,i = arg max r rR i P(r ≤ r max ) η D,j = arg max η ηP S j,min + κ j (R i + R j,i ) 1 -η ≤ r i R i (11)
Note that the key difference between ( 11) and ( 10) is the absence of expectations over distances and durations. This is due to the fact that the instantaneous and historical data available to the provider allows for the prices to take into account real-time properties of the ODT system. The quality of the solutions in [START_REF] Yang | Equilibrium properties of taxi markets with search frictions[END_REF] will depend on how effectively the provider has learned the distributions of r i,max and S j,min . All of the mechanisms so far have relied on posted-prices, where passengers and drivers can either accept or reject offers. For passengers, it is common to use a posted-price mechanism as each passenger does not make a sufficient number of requests to make informed choices for the bids that are required in auction-based approaches. Moreover, there is a concern that adopting an auction-based approach for passengers would mean that wealthier passengers are prioritized over others. As this is an undesirable feature for ODT services designed for the public, it rules out applying auctions to passenger pricing (with the possible exception of business focused services [START_REF] Egan | A double auction mechanism for on-demand transport networks[END_REF]).

On the other hand, drivers are paid based on a minimum profit criterion, raising the question of whether it is desirable to use auctions to determine driver payments and allocation. There are three reasons that suggest auctions may play a useful role for driver pricing and allocation. First, the twosided posted-price mechanism in [START_REF] Yang | Equilibrium properties of taxi markets with search frictions[END_REF] requires estimates of the pdf both for the maximum price-rate passengers are prepared to pay and the minimum profit drivers are willing to receive. If the provider has not been operating for long or is not using an efficient learning algorithm then the estimates may not be accurate. Here, it may be desirable for drivers to bid so that the provider can obtain accurate knowledge of their profit preferences. This is revealed in an auction, but not in posted-price mechanisms. Second, auctions often yield higher revenue than posted-price mechanisms when the pdf of the driver preferences has large weight in the tails [START_REF] Wang | Auctions versus posted-price selling[END_REF]. Thus, when there is large variation in driver preferences, an auction may lead to higher revenue for the provider. Third, an auction to price and allocate drivers has been implemented by Liftago 3 . Their success suggests that this approach can be practical. It is thus important to understand the mechanism's properties.

Although provider profit is not the only mechanism feature of interest-average passenger prices and driver profits also matter-it suggests that hybrid mechanisms where passengers are priced via a posted-price mechanism and drivers via an auction may play a useful role in ODT systems. To this end, in the following sections, we introduce an online hybrid mechanism (Section IV) and study its properties from the perspective 3 For more details on Liftago's hybrid mechanism see [START_REF] Mrkos | Liftago on-demand dataset and market formation algorithm based on machine learning[END_REF].

of the allocation of a single passenger request (Section V), followed by a system level evaluation (Section VII).

IV. THE HYBRID MECHANISM

In this section, we develop the pricing and allocation mechanism that is run by the provider. We call our approach a hybrid mechanism since passengers are priced by a postedprice mechanism and driver payments are determined by a single-sided auction. As such, it is neither a two-sided postedprice mechanism nor a classical double auction [START_REF] Mcafee | A dominant stategy double auction[END_REF]. Note that since a posted-price mechanism is used for the passengers, only one passenger at a time can be priced and allocated to one of a subset of all available drivers.

In practice, when there are multiple simultaneous requests, a subset of the available drivers must be selected for each passenger, a process known as market formation. As we focus on the pricing and allocation mechanism, we assume that only one passenger request arrives at a time and that all available drivers (without a passenger) can potentially be allocated.

In our hybrid mechanism, there are two phases for each passenger request. In the first, passengers are priced by an online posted-price mechanism. In the second phase, a driver is selected via an auction. We detail each phase corresponding to passenger i ≤ n (i.e., the i-th request) as follows.

A. Phase 1: Passenger Pricing

Phase 1 of the mechanism is run immediately after a passenger requests a journey. Let K ∈ N and define the price set P = { ρmax K , 2ρmax K , . . . , ρ max }. The price set consists of the possible price-rates that the provider can offer each passenger. Note that using a finite set of prices rates is consistent with current practice in Hackney carriage or dispatcher mechanisms.

Passenger i ≤ n is then priced according to the following online posted-price mechanism:

Algorithm 1 Passenger pricing.

Offer: The provider offers passenger i a price p i computed as follows.

• If 1 < i ≤ K, then set p i = R i iρmax K .
• Otherwise, set the price to be

p i = R i j * ρ max K (12)
where j * maximizes w j + 2 log i nj , w j = jρmax K , n j is the number of times a passenger has been offered the price w j , n j is the number of times a passenger offered price w j has accepted, and w j = w j n j /n j . Response: The passenger either accepts or rejects the offer.

Observe that the mechanism in Phase 1 is online, which means that prices are adapted as the number of transactions grows. In particular, Phase 1 is based on the online postedprice mechanism proposed in [START_REF] Kleinberg | The value of knowing a demand curve: bounds on regret for online posted-price auctions[END_REF], which exploits the UCB1 learning algorithm [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]. As such, the mechanism inherits desirable properties such as truthfulness and known bounds for the profit loss due to imperfect estimates of the pdf for the maximum price-rate of each passenger. We explore these properties further in Section V.

B. Phase 2: Driver Allocation and Payment

Phase 2 of our hybrid mechanism allocates a driver to the passenger and determines the payment they receive. Algorithm 2 describes this process for a request from passenger i.

Algorithm 2 Driver allocation and payment.

Driver Identification: The provider identifies those drivers able to reach passenger i within ∆ minutes.

Offer: Feasible drivers are informed how much passenger i paid for the service in Phase 1 and the distance R i , allowing them to compute their potential profit for transporting i. Driver Bidding: Each driver makes a sealed bid for the minimum payment they are willing to receive. The bid for driver j corresponds to η j and is only considered if η j ≥ 0. Allocation: The provider selects driver j with the highest bid η j , with ties broken at random..This driver receives profit

(1 -η * )r i R i -c j,i
, where η * is the value of the second highest bid. The provider receives a profit η * r i R i .

Observe that the mechanism in Phase 2 has low communication requirements. In particular, the driver identification step reduces the number of drivers that are allowed to bid. Moreover, the driver bidding step only requires each driver to make a single bid per passenger request, which is equivalent (in terms of communication requirements) to the two-sided posted-price mechanism of Section III. Phase 2's duration is short and the bandwidth required is low. Given the simple strategy in this phase, automating driver bids is also possible.

We also note that there is no guarantee that a driver will be found in Phase 2 who is willing to transport each passenger and is able to arrive within ∆ minutes of the request. This problem can be resolved by allowing the provider to retract the journey offer and refund any payment made by the passenger. However, this situation is undesirable and it is therefore important for the provider to give incentives to drivers to ensure that at least one driver is willing to transport each passenger. We explore variations of the mechanism to improve the proportion of passengers transported in Section VI.

C. Numerical Example

We provide an illustrative numerical example for our hybrid mechanism. Let p i be the price obtained for passenger i from the Offer step in Algorithm 1. This price depends on the distance, R i , of the journey and previous offers to other passengers. For concreteness, we assume that p i = 10 euros. Next, suppose that the passenger is willing to pay 11 euros for their journey. By the Response step in Algorithm 1, the passenger accepts. The provider then seeks to find a driver.

Suppose that two drivers are able to reach the passenger within a time, ∆, which in Section VII we take to be 10 minutes. The provider informs each driver that the passenger is willing to pay 10 euros for the journey. Each driver bids η j , j = 1, 2. For concreteness, we assume that η 1 = 0.6, η 2 = 0.4. Since η 1 > η 2 , driver 1 is allocated the journey and receives a profit of 6-c 1,i euros, where c 1,i is the cost for driver 1 to reach the pickup location of the passenger. The provider then receives 4 euros profit.

V. PROPERTIES OF THE HYBRID MECHANISM

In this section, we explore the properties of the hybrid mechanism. In Section V-A, we show that each phase our mechanism ensures that passengers and drivers have incentives to report truthfully. We then consider the effect of historical data on the profit the mechanism in Section V-B, which leads to a data-profit tradeoff. In Section V-C we derive bounds to relate the profit to the passenger preferences and imperfections in the provider's estimates.

Throughout this section, we compare the profits obtained via our hybrid mechanism to a mechanism which has perfect knowledge of the passenger preference distribution, which we denote by M * . In the mechanism M * , passenger i is priced via the optimization problem

r M,i = arg max r∈[0,ρmax] r ρmax r f rmax (x)dx (13)
To simplify notation, we define the expected gross profit based on a price-rate r as

J(r) = r ρmax r f rmax (x)dx (14)
For passenger i, the expected gross profit from our hybrid mechanism is denoted by J * H,i , while the expected gross profit from mechanism M * is denoted by J * M,i = J(r M,i ).

A. Truthful Reporting

As Phase 1 is based on an online posted-price mechanism and Phase 2 is based on a sealed-bid second-price auction, our hybrid mechanism inherits the truthful reporting properties of these mechanisms under no collusion. This ensures that passengers and drivers do not have any incentive to use reporting strategies that are not straightforward to characterize by the provider. In particular, the provider can use simulations to obtain more reliable estimates of its long-term profits, the profits of drivers and the prices that passengers will pay. These are important to verify the suitability of the mechanism.

We first consider passenger reports in Phase 1, which consist of the desired time of pick-up and the passenger's accept or reject response. Observe that in Phase 1, the price for passenger i does not depend on the time passenger i makes her request nor on whether they accept or reject the journey. As such, each passenger cannot influence its price by reporting an earlier or later pick-up time. Moreover, if a passenger untruthfully reports her accept or reject response, she will either receive a unwanted journey or miss out on an opportunity to receive a desirable journey. This means that passengers will report truthfully.

In Phase 2, only one passenger request is active in each hybrid mechanism run. Thus, the truthfulness of driver bids is inherited as a property of sealed-bid second-price auctions, which are themselves Vickrey auctions [START_REF] Shoham | Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations[END_REF]. It follows that the hybrid mechanism is truthful for both passengers and drivers.

B. Data-Profit Tradeoff

We now turn to the tradeoff between historical data available to the provider and the profit of the mechanism. In particular, we consider the sum expected gross profit after n passenger requests. Our first proposition provides an asymptotic scaling law for the expected loss of profit by the provider when using the hybrid mechanism rather than another mechanism:

E[L] = E n i=1 J * M,i - n i=1 J * H,i (15)
Proposition 1. Let K = (n/ log n)

1 4
and suppose that the parameters of the passenger price preferences satisfy α = 1 and β > 1. Then, E[L] satisfies

E[L] = O( n log n) ( 16
)
The proof of Proposition 1 relies on the following lemma.

Lemma 1. Suppose α = 1 and β > 1. Then the unique maxima of J(r) in ( 14) is

r * = ρ max 1 + β ( 17
)
Proof. The condition for a critical point is

∂ ∂r r ρmax r f (x)dx = 0 (18)
Applying the Leibniz rule and evaluating the integral yields

ρ max β 1 - u ρ max β -u 1 - u ρ max β-1 = 0 (19)
which has the solution

u = ρ max β + 1 . ( 20
)
We now show that the point u is the unique maximum of J(r). Without loss of generality, we focus on the case ρ max = 1 since this only affects the support. Observe that

1 r 1 B(1, β) (1 -x) β-1 dx - 1 B(1, β) r(1 -r) β-1 < 0 ⇔ 1 β (1 -r) -r < 0 ⇔ r > 1 1 + β which implies that J (r) < 0 for r > 1 1+β
. Using a similar argument, it follows that J (r) > 0 for r < 1 1+β . This implies that u is in fact the unique maximum for J(r).

We now complete the proof of Proposition 1.

Proof. Since J(r) has a unique maximum on [0, 1] it follows that we can apply [START_REF] Kleinberg | The value of knowing a demand curve: bounds on regret for online posted-price auctions[END_REF]Theorem 3.14], which states that

E[L] = O( √ n log n) when K = (n/ log n) 1 4
, from which Proposition 1 then follows. We note that the statement of Theorem 3.14 in [START_REF] Kleinberg | The value of knowing a demand curve: bounds on regret for online posted-price auctions[END_REF] corresponds to the case ρ max = 1; however, the result can be extended to ρ max ∈ R + .

We remark that Proposition 1 does not apply to every choice of α r , β r for the distribution of the maximum price-rate. However, it holds for a wide range of parameter choices where the tail of the density as r → ρ max is decaying. Moreover, a numerical study suggests that the result holds for all α, β. As passengers are typically less likely to pay for higher priced journeys, the choices of parameters in Proposition 1 are the most applicable to ODT systems.

A drawback of Proposition 1 is that it does not provide any information on the effect of passenger preferences on the expected loss. However, intuition suggests that the profit loss E[L] should be smaller for lower values of the variance for the maximum price-rate r i,max , which we verify next.

C. Influence of Preferences

While Proposition 1 provides insight into how the expected gross profit varies with the number of requests (corresponding to the available data), it does not indicate how passenger and driver preferences affect the performance of the mechanism.

Suppose passenger i is offered a price-rate r i by the hybrid mechanism in Phase 1, which is typically suboptimal. This offer can be interpreted in terms of the mechanism M * , where the price-rate is optimized using a pdf frmax with parameters α, β, ρ max . The expected gross profit loss due to the imperfect estimate frmax is then given by

E[L i ] = J * M,i -r i ρmax ri frmax (x)dx (21)
Due to the dependence on r i arising from the mechanism in Phase 1, it is not possible to obtain a closed-form expression for E[L i ]. As such, we focus on obtaining a bound to examine the effect of parameters for passenger preferences on the profit loss. We begin by considering the upper bound for the expected gross profit loss.

Proposition 2. Suppose that α = 1 and β > 1, then E[L i ] is given by [START_REF] Gan | Game theoretic considerations for optimizing taxi system efficiency[END_REF], where ψ is the digamma function.

Proof. Observe that

E[L i ] = r * ρmax r * f (x)dx -r i ρmax ri f (x)dx ≤ r * ρmax r * f (x) -r * ρmax r * f (x)dx ≤ r * ρmax 0 |f (x) -f (x)|dx (23)
Consider the change of variables y = x/ρ max , which yields

E[L i ] ≤ r * 1 0 | f (y) -f (y)|dy (24)
where f and f are beta pdfs with support [0, 1] and parameters α, β and α, β respectively. Note that the integral in ( 24) is twice the total variation. Applying Pinsker's inequality [START_REF] Cover | Elements of Information Theory[END_REF] to bound the total variation in terms of the Kullback-Leibler divergence, D KL , we obtain

E[L i ] ≤ 2D KL ( f , f ) (25)
which yields the desired result after evaluating the Kullback-Leibler divergence of beta distributed random variables.

In the special case that α = α = 1 and β, β ≈ 1, we can obtain further insight into the effect of imperfect knowledge

E[L i ] ≤ 2 log B(α, β) B(α, β) + (α -α)ψ(α) + (β -β)ψ(β) + ( α -α + β -β)ψ(α + β) (22)
of β. In particular, B(1, β) = 1 β and ψ(1 + β) = ψ(β) + 1 β . As such, the bound in Proposition 2 simplifies to

E[L i ] ≤ 2 log β β + β -β β ( 26
)
Since β, β ≈ 1, we obtain the approximation

E[L i ] 2 β -β + β -β β ( 27
)
from which it follows that

E[L i ] K|β -β| (28)
where is K is a constant depending only on β and not β. As such, the bound on E[L i ] approximately scales with the square root of the estimation error.

For providers, it is also of interest to understand how the mechanism performs in the presence of different passenger preferences using the mechanism M * . Suppose that the mechanism has perfect knowledge of passenger preferences. Let r * α,β be the optimal price-rate with parameters α, β. We then have the following result.

Proposition 3. Consider two sets of passenger parameters α, β and α , β such that α = α = 1 and β, β > 1. Then, the expected gross profit difference is given by

E[L D ] = ρ max β β (1 + β) β+1 - β β (1 + β ) 1+β (29)
Proof. Since α = α = 1 and β, β > 1, we can apply Lemma 1. In particular, the expected gross profit difference is -as required -given by

E[L D ] = r * 1,β ρmax r * 1,β f (x; 1, β)dx -r * 1,β ρmax r * 1,β f (x; 1, β )dx = ρ max β(1 + β)B(1, β) 1 - 1 1 + β β - ρ max β (1 + β )B(1, β ) 1 - 1 1 + β β = ρ max β β (1 + β) β+1 - β β (1 + β ) 1+β (30)
Observe from Proposition 3 that for large β, β , the expected gross profit difference satisfies E[L D ] ≈ 0.

VI. VARIATIONS OF THE HYBRID MECHANISM

The hybrid mechanism aims to maximize the provider's profit. However, this is not necessarily desirable, e.g., if the provider seeks to serve more passengers. Similarly, the provider may wish to modify the mechanism if there are insufficient drivers willing to bid above the reservation price in the auction, such as when driver costs are too high.

A key motivation for providers to modify the hybrid mechanism is to improve the efficiency, which is is a general notion in mechanism design. In the context of ODT it is natural to interpret the efficiency as the proportion of passengers that accept their offer and have a driver to transport them. That is, efficiency is the proportion of passengers able to successfully complete their desired journey and is denoted by E.

There are two modifications the provider can make to the hybrid mechanism, namely to either adjust the price-rate, or to introduce driver subsidies. In the remainder of this section, we detail these variations on the mechanism developed in Section IV and explore their impact on efficiency.

A. Adjusting the Price-Rate

In the ideal scenario where the provider has perfect knowledge of passenger preferences and has elicited the minimum profit each driver requires, the profit maximization problem that the provider aims to solve for each passenger i is

P * = max r min {Sj,min} R i r 1 - S j,min + κ j (R i + R j,i ) rR i × P(r ≤ r i,max ) (31)
This problem can also be written as

P * = max r rR i P(r ≤ r i,max ) -(S * + C * )P(r ≤ r i,max ) (32)
where S * is the minimum profit of the selected driver and C * is the corresponding travel cost. As such, the driver profit requirements regularize the optimization problem. In particular, the subtracted term results in a price-rate higher than the case where only passenger preferences are considered. We note that the problem in (32) cannot be solved directly as it is necessary to elicit the driver profit requirements, which in turn depend on the price-rate that the passenger is charged. For this reason, a mechanism such as our hybrid mechanism (as described in Section IV) is required. However, the problem in [START_REF] Wang | Pricing strategies for a taxi-hailing platform[END_REF] illustrates the important dependence of the price-rate on the efficiency (or equivalently the likelihood that both passengers and drivers are willing to accept the journey).

To gain further insight into the dependence of efficiency on the price-rate, consider the probability that at least one driver is willing to transport passenger at price-rate r. That is, for a given passenger i there exists at least one driver j such that

S j,min τ j,i + c(R i + R j,i ) ≤ rR i (33)
The probability this holds is equivalent to the efficiency E.

To explore the influence of journey parameters on the efficiency, consider driver j and define the random variable

X = S j,min τ j,i + κ j (R i + R j,i ) (34)
Since X has bounded support determined by S j,min , κ j , R i , R j,i , and τ j,i , we model X as a beta distributed random variable with parameters α X , β X . To justify this model, observe that for known R i , R j,i , τ j,i , κ j

S j,min = X -κ j (R i + R j,i ) τ j,i (35)
which is the beta distributed minimum driver profit (c.f., Sec. II).

With the definition of X, the optimization problem in (32) can be approximated as

P * approx = max r rR i P(r ≤ r i,max )Pr(X ≤ R i r) (36)
which corresponds to the optimal profit when the provider allows only one driver to transport passenger i. This optimization problem provides useful insights into the tradeoff between the expected provider profit per journey and the efficiency of the mechanism. Observe that as the price-rate increases, both the approximate profit and the efficiency lower bound increase before decreasing again for large price-rate r. Intuitively, no drivers will accept a journey at a low price-rate while no passengers will accept a journey at a very high price-rate. Fig. 1 illustrates the tradeoff between profit and efficiency. A key observation is that the optimal price-rate to maximize the approximate profit differs from the optimal price-rate to maximize the efficiency lower bound. Providers seeking to maximize efficiency will not in general choose the same pricerate as in the case of profit maximization. This is consistent with the differences between profit maximization and social planning objectives considered in auction design [START_REF] Wang | Auctions versus posted-price selling[END_REF].

In practice, the provider does not have perfect knowledge of the efficiency-profit tradeoff curve. However, the information obtained from early passenger requests can provide clues as to this curve. In particular, as the online mechanism in Phase 1 explores a range of prices, this data can also be used to construct an estimate of the efficiency-profit tradeoff curve.

B. Driver Subsidies

The efficiency of the hybrid mechanism is influenced by the requirement that each driver receive a minimum profit for each journey, which induces a loop in the profit-efficiency curve (as illustrated in Fig. 1). In particular, reducing the price-rate does not necessarily lead to improvements in the efficiency of the mechanism. This is due to the fact that reducing the pricerate can also reduce the probability that there exists a driver willing to transport each passenger.

An alternative method to improve the efficiency of the mechanism is to introduce subsidies. In particular, when no driver is able to serve a passenger profitably, the provider can compensate a driver that would otherwise not meet her minimum profit criterion. In this case, the provider pays the driver more than the price it charges the passenger.

While an unbounded subsidy can make every journey profitable for at least one driver, in general the subsidy must be bounded. This is to ensure that highly unprofitable passengers are not serviced so that the provider makes a long-term profit.

In the hybrid mechanism, subsidies are implemented by modifying the reservation price. Instead of requiring that η > 0 for each bid, the broker also accepts negative bids subject to the restriction that η > η res where η res < 0 is the new reservation price. This increases the efficiency of the mechanism as drivers with bids

η = 1 - S j,min + κ j (R i + R j,i ) rR i < 0 (37)
can still bid for a journey.

To ensure that the provider does not suffer a significant loss, the reservation price η res ∈ R is bounded. To evaluate the effect of the subsidy it is necessary to consider a system level evaluation which we describe next.

VII. SYSTEM LEVEL EVALUATION

Due to the complexity and spatial-temporal nonhomogeneity of ODT systems, to properly understand the behavior of any mechanism it must be evaluated at the system level. In particular, the mechanism must be evaluated with realistic demand profiles of passenger (i.e., pick-up and drop-off locations and times), time-varying locations of available drivers, and city road networks. In this section, we carry out a simulation-based system level evaluation of our hybrid mechanism and the variations detailed in Section VI. In Section VII-A, we provide a detailed description of our simulation setup. At a high-level, we consider an ODT provider based in the Hague and build our simulator by modifying the Mobility Testbed [START_REF] Čertický | Agent-based simulation testbed for on-demand transport services (demonstration)[END_REF], which provides realistic demand profiles for passengers. In Section VII-B, we detail the findings from our system level evaluation.

A. Simulation Setup

To evaluate our hybrid mechanism at the system level, we simulate the dynamics of the provider and passenger and driver agents. Our simulator is based on the multi-agent Mobility Testbed simulation tool for ODT systems. In contrast with other simulation tools 4 for transportation systems built from scratch (e.g., [START_REF] Fu | A simulation model for evaluating advanced dial-a-ride paratransit systems[END_REF]- [START_REF] Quadrifoglio | A simulation study of demand responsive transit system design[END_REF]) and those based on AnyLogic [START_REF] Banks | Discrete-event system simulation[END_REF], MATSIM or SUMO [START_REF] Orey | Empirical evaluation of a dynamic and distributed taxi-sharing system[END_REF], the Mobility Testbed allows for tracking and modifications of driver routes facilitating the analysis of routing, scheduling and pricing algorithms.

The Mobility Testbed was originally designed to evaluate dial-a-ride allocation algorithms [START_REF] Čertický | Agent-based simulation testbed for on-demand transport services (demonstration)[END_REF], [START_REF] Čertický | Agent-based simulation testbed for on-demand mobility services[END_REF]. As such, we make a number of modifications to incorporate taxi mechanisms and our hybrid mechanism, as well as more realistic driver behavior. We now describe the setup of our simulator.

We consider an ODT provider based in the Hague over a period of one day, with a total of 1000 passenger requests and 100 drivers (not all of whom are always available at a given time). The road network in the simulator is obtained from the OSM map of the Hague5 , from which journey distances are computed. The region of the city considered is shown in Fig. 2. Journey durations and passenger requests (pick-up and dropoff locations) are based on the realistic traffic and demand models instantiated in the Mobility Testbed [START_REF] Čertický | Agent-based simulation testbed for on-demand mobility services[END_REF]. We set the maximum waiting time of each passenger, ∆, to 10 minutes, thereby imposing restrictions on the drivers that can feasibly transport any passenger. As such, the driver locations when they are not transporting a passenger affect the proportion of passengers that are transported (the efficiency) and also the revenue of the ODT provider.

To account for how drivers choose their location when they are not transporting a passenger, we adopt a hill-climbing approach. In particular, each node in the road network is assigned a probability that a passenger will make a pick-up request at the node. To determine where each available driver will travel in the next time period, each node k is assigned a score which is equal to the sum of the probabilities associated to each node that can be reached from node k within ∆ minutes. Each available driver then travels to a neighboring node with the highest score and in the case of a tie, the driver selects nodes with equal score uniformly. To obtain the score for each node, we used a training set 1000 passenger requests before the simulation began (in a real system, such pre-training could be performed using existing data available to the ODT provider). The scores were then updated as the simulation progressed.

To evaluate our hybrid mechanism, we compared it with the dispatcher and two-sided posted-price mechanisms. In the dispatcher mechanism, passengers are offered a price-rate of 2 euros/km and the selected driver is the nearest feasible one. This driver is paid a 10% commission. If no feasible driver is found, then the passenger is not transported. The price-rate was selected as representative of real-world rates. In the online two-sided posted-price mechanism, passengers and drivers are priced using Phase 1 of our hybrid mechanism. For the drivers, the mechanism offers the nearest feasible driver the minimum acceptable profit.The full details for the online two-sided posted-price mechanism are provided in Algorithm 3, where similar to Phase 1 the parameter w p,j is the average passenger revenue from offering a price-rate ρ max j/K and n p,j corresponds to the number of times that price-rate ρ max j/K has been offered to passengers. For the drivers, we use a similar pricing scheme also based on UCB1, where w d,l is the average amount paid to drivers from offering a payment of σ max l/K and n d,l corresponds to the number of times that the payment σ max l/K has been offered to drivers.

i -κ k (R k,i +R i )-S k,i .
Next, we detail our findings for the performance of our hybrid mechanism and its variations, as well as these two baseline mechanisms used for comparison. A full summary of simulation parameters is provided in Table I.

B. Simulation Results

Before evaluating the performance of our proposed mechanism, we first consider the behavior of the dispatcher model with varying passenger prices. Fig. 3 plots the tradeoff between the average number of successful journeys and the average profit received by the provider. The tradeoff is obtained by varying the price-rate offered to each passenger. Observe that the shape of the curve is consistent with the efficiency-profit curve in Fig. 1, obtained via theoretical analysis. As such under the dispatcher model, it is not possible to simultaneously maximize the profit and the number of successful journeys. While it is not possible to simultaneously maximize profit and the number of successful journeys, it is feasible to sig- nificantly improve the profit using our proposed mechanism. Figures 4 and5 compare the average profit and success rate for each mechanism for a system with passenger and driver demand parameters α r = α d = 1, β d = 5. The parameter β r governs the shape of the beta distribution from which each passenger's maximum price-rate is drawn. A larger β r means that passengers are less likely to have a high maximum price-rate and can be interpreted as a demand parameter. In particular, when there is low demand for a journey each passenger is prepared to pay less.

Observe that the proposed mechanism yields a significantly higher average profit compared with the posted-price and dispatcher models. Moreover, the profit and success values depend on the passenger demand. In particular, observe that as the passenger demand parameter β r increases the profit reduces. This occurs as passengers are less likely to have a large maximum price-rate when β r is large. As already noted, the average profit for the hybrid mechanism is significantly higher than for the posted-price mechanism. On the other hand, the success rate for the hybrid mechanism and the posted-price mechanism are comparable. The success rate for the dispatcher mechanism is higher than for the hybrid and PP mechanisms, at the cost of a significantly lower average profit.

We now study the impact of subsidies introduced in Section VI-B for a choice of β r = 1. Table II shows the effect of introducing the subsidies. As expected, increasing the subsidy improves the success rate at the cost of the average profit. In particular, the profit loss corresponding to an improvement of approximately 80 passengers in the success rate is approximately 640 euros. However, a gain in 20 passengers corresponds to a profit loss of only 70 euros. This captures the intuition that there are diminishing gains in how many passengers can be reliably served.

VIII. CONCLUSIONS

The wide availability of data means that it is possible for ondemand transport providers to improve pricing and allocation of passengers and drivers. In this paper, we proposed a hybrid mechanism and studied its performance and sensitivity to data available to the provider from previous passenger requests. We show that the provider's revenue loss scales with √ n log n, where n is the number of passenger requests the provider has received. We also compared the performance of the hybrid mechanism-for realistic models of passengers and driverswith a two-sided posted-price mechanism and a mechanism based on the dispatcher taxi model. Our simulation results show that the success rate of our mechanism is comparable with an improvement in the average profit.

In future work, we intend to examine how interactions between multiple providers and passengers and drivers affect the mechanism, and what (if any) changes are required to function in such settings. We also intend to examine whether more sophisticated mechanisms for routing drivers without passengers can affect the latter's profits. Nir Oren is a Reader in Computing Science at the University of Aberdeen. His primary research area is in the field of multi-agent systems, and in particular reasoning, explanation and optimisation within such systems. To this end, Dr Oren has worked in areas such as formal argumentation theory, computational trust and policy based reasoning, as well as virtual organisation creation and on-demand transport.

Michal Jakob is an associate professor of computer science at Czech Technical University in Prague, Czechia. His primary research area is the application of artificial intelligence in transport and mobility, in particular related to mobility as a service and largescale electric mobility. He was the principal investigator of several large european research projects in the area of sustainable urban mobility. Michal has published over 50 scientific papers and is the principal Inventor on two international patents.

Fig. 1 .

 1 Fig. 1. Plot of the approximate profit (per km) in (36) versus the efficiency. Parameters: αp = 1, βp = 1, α d = 1, β d = 5, ρmax = σmax = 1, R i = 1.

Fig. 2 .

 2 Fig. 2. OSM map of the Hague considered in the simulation study.

Fig. 3 .

 3 Fig. 3. Empirical efficiency-profit curve obtained by varying the offered pricerate in the dispatcher mechanism.

Fig. 4 .

 4 Fig. 4. Effect of passenger preferences on the average profit for the proposed, posted-price (PP) and dispatcher mechanisms.

Fig. 5 .

 5 Fig. 5. Effect of passenger preferences on the success rate for the proposed, posted-price (PP) and dispatcher mechanisms.

Malcolm

  Egan received the Ph.D. in Electrical Engineering in 2014 from the University of Sydney, Australia. He is currently an Assistant Professor in CITI, a joint laboratory between INRIA, INSA Lyon and Université de Lyon.His research interests include information theory, statistical signal processing and mechanism design with applications in wireless and molecular communications, and intelligent transportation.

  Offer driver k the journey with minimum profit S k,i . if S k,i < τ k,i S k,min then Driver rejects offer, end algorithm.

Algorithm 3 Two-sided online posted-price mechanism.

Initialization: Passenger i requests a journey.

if 1 ≤ i ≤ K then Set p i = R i iρ max /K else Set p i = R i (w p,j * + 2 log i/n p,j * )

, where j * is chosen to maximize w p,j + 2 log i/n p,j . Offer passenger i the journey at price p i . if p i > p i,max then Passenger rejects offer, end algorithm. else Select closest feasible driver k.

if 1 ≤ i ≤ K then S k,i = τ k,i iσ max /K. else S k,i = -τ k,i (w d,l * + 2 log i/n d,l * )

, where l * is chosen to maximize w d,l + 2 log i/n d,l . else Successful transaction: passenger pays p i ; driver receives S k,i ; provider receives p

TABLE II EFFECT

 II OF SUBSIDIES ON THE AVERAGE PROFIT AND SUCCESS RATE.

	Subsidy Level (euros)	-1	-5	-10
	Hybrid Ave. Profit (euros)	3766 3394	3069
	Hybrid Ave. Success (/1000)	417	477	487

https://www.uber.com/

https://www.liftago.com/

For a detailed survey of simulation tools see[START_REF] Čertický | Agent-based simulation testbed for on-demand transport services (demonstration)[END_REF].

The Hague OSM map can be found in the Hague benchmark for the Mobility Testbed https://github.com/agents4its/mobilitytestbed/wiki/Benchmarks.

ACKNOWLEDGEMENTS

This work was partly funded by the Technology Agency of the Czech Republic (grant no. TE01020155). The authors acknowledge the support of the OP VVV MEYS funded project CZ.02.1.01/0.0/0.0/16 019/0000765 "Research Center for Informatics".