Dynamic bidding for merging in algorithmic traffic

Drivers have different valuations of time, and yet, the way road traffic is currently managed almost never gives priority to vehicles that are willing to pay more to move faster. The reason for this economic inefficiency is that, currently, there is no platform to bid or trade in real-time for priority movement on the road. However, algorithmic driving and 5G-based inter-vehicle communication technologies promise to change this situation, and the question of a fair and practical mechanism to incorporate drivers' willingness-to-pay takes on importance. Any such mechanism has to satisfy the computational requirements of a real-time bidding mechanism, so complicated and protracted negotiations are unlikely to be feasible. In this paper we study the design of such a mechanism in a mandatory-merging scenario: a single driver on the blocked-lane of a two-lane highway has to merge into a dense platoon of cars on the free lane. Driver time-valuations are private, with common beliefs about their distribution. We study a bidding mechanism where the blocked-lane driver offers to pay each of the free-lane drivers, sequentially from tail to head of the platoon. The driver is allowed to merge to a certain position only if all drivers up to that point have accepted their offers. Hence, the mechanism imposes no negative externalities on free-lane drivers. We show that the optimal bids can be computed via a simple dynamic programming recursion, we examine the social welfare of the mechanism, and we contrast it to a head-to-tail mechanism as well as to a "partial-information social optimum." Finally, we propose fast approximate dynamic programming algorithms, which lead to bids that are very close to the optimal ones, making them suitable for practical implementation