Data-Driven Market Formation in On-Demand Transport

As on-demand transport providers (e.g., Uber) are adopting increasingly sophisticated mechanisms to allocate and price both passengers and drivers, new issues are arising. In a series of posts (starting here), I have been describing different aspects of these issues including the ways to allocate and price (the mechanism design) and also simulation tools to evaluate performance in realistic environments (capturing both the road network and the behavior of passengers and drivers).

In this post, I want to turn to a different aspect: the market formation problem.

Continue reading

A Simulation Tool for Market-Based On-Demand Transport

Update 2/11/2016: At present, there is new development of the testbed. If you are interested in specific features, you should contact Michal Čap.

A key challenge in understanding market-based on-demand transport services is that it is not just a local problem; i.e., the behavior of an individual market. Since there are usually a number of allocations going on at the same time and individual markets are changing over time another approach is required. In fact, a rigorous evaluation requires a study of how the on-demand transport interacts with the underlying transportation network and even other dynamics of the city as we alluded to in our working paper here.

The field of multiagent systems provides a good framework to study how markets behave when they are embedded in transportation networks. Within this framework, drivers, passengers and even providers are modeled as autonomous agents. This means that each driver, passenger and provider makes its own decisions based on their own preferences and the information that is available to them. Using the multiagent systems framework allows us to capture differences in the preferences of individual drivers, passengers and providers and also competition between them.

In recent papers (see here and our preprint here),  we studied how the mechanism performed on in the Hague with a realistic demand profile for passenger requests. The basis of our network-scale evaluation was a simulation tool: the mobility services testbed. This simulation tool was developed by Michal Certicky and Michal Jakob at the Czech Technical University in Prague.

The mobility services testbed provides an easy way of implementing different market mechanisms in the context of on-demand transport. You can get it from github here.

For an overview of other aspects of mechanisms for on-demand transport, see these posts:

Market-Based On-Demand Transport

If you are a company providing or a municipality supporting  on-demand transport services, there is an important decision that you must make: what should be the structure of the service? By structure, I mean how drivers and passengers can interact, or how payments are made. For instance, traditional taxi services differ in their structure from providers such as Uber.

In an earlier working paper (available here) and the post here, I discussed the differences between the main classes of on-demand transport services: hackney carriage; dispatcher; dial-a-ride; and market-based. However, the classification was limited in that it did not distinguish easily between services within a given class.

With the rise in market-based on-demand transport services (e.g., Uber), there is now a need to understand the different ways that these services can operate. And this is what I intend to describe here.

Continue reading

Mechanism design for on-demand transport

During 2014 – 2015, one of the key research problems I was working on was how to understand and design on-demand transport mechanisms. On-demand transport is about how an individual or group can get from point A to point B at a time of their choosing. Common examples are taxi services and now new services such as Uber.

Working in a computer science department, primarily with collaborators Michal Jakob and Nir Oren, I was concerned with how passenger journeys are allocated to drivers and how each journey was priced, together called a mechanism, from an algorithmic perspective. I.e., how can these allocations and pricing be done in a computationally efficient way so that passengers get to where they want to go on time, each driver can earn a living, and service providers (e.g., Uber) can make a profit.

The problem of choosing a mechanism is known in economics as the mechanism selection problem, and must account for a range of technical, social and financial issues. For example, can the available computing resources compute the allocation and pricing quickly enough? Or, are passengers or drivers prepared to bid for a journey (a key problem for auction-based approaches)?

We have explored the problem of mechanism selection in on-demand transport by first enumerating the possible mechanisms and evaluating their performance. We observed in this working paper that each approach (e.g., hackney carriages, taxi dispatcher models, and Uber-type approaches) can be differentiated by limitations on communication and financial exchanges.

After enumerating the possibilities, we have begun to explore how the different mechanisms perform in terms of metrics such as the proportion of passengers served, costs of journeys and provider profit. In particular, we have published work in:

(1) Malcolm Egan, Martin Schaefer, Michal Jakob, and Nir Oren, “A double auction mechanism for on-demand transport networks”, in the Proc. PRIMA 2015: Principles and Practice of Multi-Agent Systems,  (2015).

(2) Malcolm Egan, and Michal Jakob, “A profit-aware negotiation mechanism for on-demand transport services”, in the Proc. of the European Conference on Artificial Intelligence (ECAI), (2014)

and now

(3) Malcolm Egan and Michal Jakob, “Market mechanism design for profitable on-demand transport services”, accepted for Transportation Research Part B: Methodological.

A key feature of our article (3) is that we provide and justify an agent-based model for on-demand transport services that captures the preferences of passengers. This means that we do not assume that every passenger will accept whatever they are offered, which is commonly assumed in previous work on on-demand transport mechanisms.

The next step is to continue to study the mechanism selection problem by understanding the requirements and performance of other on-demand transport mechanisms. At the end of the day, we hope that this work will aid new providers and municipalities to decide the kinds of mechanisms they want to support to match the unique economic, social and technical features of their cities. We believe this will provide a means to meet the needs of passengers, drivers, and providers in each city in a sustainable way.

To read more, see the next posts in this series: