Online Cost-Sharing Mechanism Design for Demand-Responsive Transport Systems

Demand-responsive transport (DRT) systems provide flexible transport services for passengers who request door-to-door rides in shared-ride mode without fixed routes and schedules. DRT systems face interesting coordination challenges. For example, one has to design cost-sharing mechanisms for offering fare quotes to potential passengers so that all passengers are treated fairly. The main issue is how the operating costs of the DRT system should be shared among the passengers (given that different passengers cause different amounts of inconvenience to the other passengers), taking into account that DRT systems should provide fare quotes instantaneously without knowing future ride request submissions. We determine properties of cost-sharing mechanisms that make DRT systems attractive to both the transport providers and passengers, namely online fairness, immediate response, individual rationality, budget balance, and ex-post incentive compatibility. We propose a novel cost-sharing mechanism, which is called Proportional Online Cost Sharing (POCS), which provides passengers with upper bounds on their fares immediately after their ride request submissions despite missing knowledge of future ride request submissions, allowing them to accept their fare quotes or drop out. We examine how POCS satisfies these properties in theory and computational experiments.