Mechanism Design for Ridesharing

Speaker: Dengji Zhao

Affiliation: University of Southampton

Time: Friday 10/10/2014 from 13:30 to 14:30

Venue: Access Grid UWS. Presented from Penrith (Y239), accessible from Parramatta (EB.1.32) and Campbelltown (26.1.50).

Abstract: This talk will present a novel market-based system for ridesharing, where commuters are matched based on their declared travel constraints, the number of available seats (which could be zero), and their costs. Based on this information, the system then designates commuters to be either drivers or riders, finds appropriate matches, and calculates rewards for drivers and payments for riders. We show that, for this system, the well-known Vickrey-Clarke-Groves (VCG) mechanism is incentive compatible (IC), individually rational (IR) and efficient (i.e., minimizing cost), but results in a very high deficit, thus requiring large subsidies. We therefore investigate alternative mechanisms. We first consider mechanisms with fixed prices and show that no such mechanism can be both efficient and IC. Thus, we propose an inefficient IC mechanism but which has deficit control. We then consider a VCG mechanism with two-sided reserve prices. We show that this mechanism is IC and IR for a certain range of reserve prices, and we analyse the deficit bounds and how these can be controlled. We furthermore show that the deficit can be controlled even further by limiting the (costly) detours taken by the drivers when computing the allocations, thereby trading off efficiency and deficit. Since both fixed prices and reserve prices are determined independently of commuters' trip information and therefore might affect the efficiency significantly, we investigate another type of mechanisms based on McAfee's trade reduction, which is truthful and almost efficient with flexible deficit control.

Biography: Dr Dengji Zhao is a research fellow at University of Southampton working with the inaugural Regius Professor of Computer Science Prof. Nick Jennings. He received double PhD degrees in Computer Science from University of Western Sydney and University of Toulouse in 2012. Before he moved to Southampton, he was a postdoctoral researcher at Kyushu University working with Prof. Makoto Yokoo. His research focuses on computational aspects of microeconomics, especially game theory and mechanism design.