Trip auctions for fair ridesharing trips

Dynamic trip pricing methods are commonly used by ridesharing companies (eg. Uber, Lyft) to manage customer behaviour and to incentivise driver participation. These methods have been described as an [economist's dream](http://freakonomics.com/podcast/uber-economists-dream/), given their unique ability to capture the dynamics of balance between supply and demand in urban transportation.

With funding from EPSRC and the A.G. Leventis Foundation, we have been developing pricing techniques for ridesharing platforms that can guarantee fairness in trip assignment, and are quick to adapt to changes in demand. Given recent concerns regarding the increase of traffic delays due to ridesharing, our ultimate objective was to incentivise the use of shared rides.

Our algorithms were tested using Delos, the urban mobility modelling platform developed by TSL, which demonstrated that simulated ridesharing platforms are able to increase revenue yields, reduce customer waiting times and increase the utilisation of vehicel fleets. Preliminary outcomes of our work were presented in the 21st IEEE Conference on Intelligent Transportation Systems (ITSC)

Over the course of our research we identified double auctions as a suitable alternative to area-wide surge pricing, given their ability to maximise the social welfare of the allocation process. To test this approach, we performed numerical experiments using the publicly available New York taxi trip dataset and a simulated platform capable of providing shared trips, in place of conventional taxis.

Our model assumes a quasi-online matching process with a request accumulation window with a length that varies according to current demand levels. Shared trip requests are pooled and are matched using our algorithms, which then proceed to perform trip assignments and circulate pickup instruction to drivers.

To reduce the length of our matching window, we employ pre-matching, where we create a network of compatible rider-to-rider and driver-to-rider bids and discard incompatible combinations. This approach can be seen as a form of 3D matching, as it constructs a series of driver-rider-rider combinations that maximises social welfare. The resulting matching problem isntances are solved using efficient local search algorithms.