Sequential bidding for merging in algorithmic traffic

File Description SizeFormat 
bidding_MSOM_2nd_rev_version to share.pdfFile embargoed until 01 January 10000759.91 kBAdobe PDF    Request a copy
Title: Sequential bidding for merging in algorithmic traffic
Authors: Talluri, K
Markakis, M
Tikhonenko, D
Item Type: Journal Article
Abstract: 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.
Date of Acceptance: 22-Jul-2022
ISSN: 1523-4614
Publisher: Institute for Operations Research and Management Sciences
Journal / Book Title: Manufacturing and Service Operations Management
Copyright Statement: Copyright reserved
Keywords: Operations Research
0102 Applied Mathematics
1503 Business and Management
1505 Marketing
Publication Status: Accepted
Embargo Date: This item is embargoed until publication
Appears in Collections:Imperial College Business School