Sequential bidding for merging in algorithmic traffic

Problem Definition: We consider the problem of resolving ad-hoc unpredictable congestion in environments where customers have private time valuations. We investigate the design of fair, efficient, budget-balanced and implementable bidding mechanisms for observable queues. Our primary motivation comes from merging in algorithmic traffic, i.e., a driver wishing to merge in a relatively dense platoon of vehicles in a coordinated and efficient way, using inter-vehicle communication and micro-payments, akin to an arriving customer trading for position in a single-server observable queue. Methodology/Results: We analyze the performance of a mechanism where the queue-joiner makes sequential, take-it-or-leave-it bids from tail to head of a platoon (T2H), with the condition that the vehicle can advance to the next position only if it wins the bid. This mechanism is designed so it is implementable, balances the budget, and imposes no negative externalities. We compare this with head-to-tail bidding (H2T), which favors the merging driver but potentially causes uncompensated externalities. Assuming i.i.d. time valuations, we obtain the optimal bids, value functions, and expected social welfare in closed form in both mechanisms. Moreover, if the time valuation of the merging driver is not high, we show that the expected social welfare of T2H is close to a partial-information social optimum, and that the expected social welfare of H2T is lower than that of T2H as long as the platoon is not too short. Managerial Implications: Our findings suggest that mechanisms based on sequential, take-it-orleave-it bids from tail to head of an observable queue have good social welfare performance, even if the corresponding bids are not chosen optimally, as long as the time valuation of the arriving customer is not high. Nevertheless, the tension between individual incentives and social welfare seems hard to resolve, highlighting the role of platforms to enforce the cooperation of involved parties.