Rey, David; Levin, Michael W.; Dixit, Vinayak V. Online incentive-compatible mechanisms for traffic intersection auctions. (English) Zbl 1487.90224 Eur. J. Oper. Res. 293, No. 1, 229-247 (2021). Summary: We present novel online mechanisms for traffic intersection auctions in which users bid for priority service. We assume that users at the front of their lane are requested to declare their delay cost, i.e. value of time, and that users are serviced in decreasing order of declared delay cost. Since users are expected to arrive dynamically at traffic intersections, static pricing approaches may fail to estimate user expected waiting time accurately, and lead to non-strategyproof payments. To address this gap, we propose two Markov chain models to determine the expected waiting time of participants in the auction. Both models take into account the probability of future arrivals at the intersection. In a first model, we assume that the probability of future arrivals is uniform across lanes of the intersection. This queue-based model only tracks the number of lower- and higher-bidding users on access lanes, and the number of empty lanes. The uniformness assumption is relaxed in a second, lane-based model which accounts for lane-specific user arrival probabilities at the expense of an extended state space. We then design a mechanism to determine incentive-compatible payments in the dynamic sense. The resulting online mechanisms maximize social welfare in the long run. Numerical experiments on a four-lane traffic intersection are reported and compared to a static incentive-compatible mechanism. Our findings show that static incentive-compatible mechanisms may lead users to misreport their delay costs. In turn, the proposed online mechanisms are shown to be incentive-compatible in the dynamic sense. MSC: 90B22 Queues and service in operations research 91B26 Auctions, bargaining, bidding and selling, and other market models Keywords:auctions/bidding; incentive-compatibility; online mechanism design; Markov chain; traffic intersection PDFBibTeX XMLCite \textit{D. Rey} et al., Eur. J. Oper. Res. 293, No. 1, 229--247 (2021; Zbl 1487.90224) Full Text: DOI arXiv References: [1] Altché, F.; De La Fortelle, A., Analysis of optimal solutions to robot coordination problems to improve autonomous intersection management policies, Proceedings of the IEEE intelligent vehicles symposium (IV), 86-91 (2016), IEEE [2] Bergemann, D.; Välimäki, J., The dynamic pivot mechanism, Econometrica, 78, 2, 771-789 (2010) · Zbl 1229.91206 [3] Bergemann, D.; Välimäki, J., Dynamic mechanism design: An introduction, Journal of Economic Literature, 57, 2, 235-274 (2019) [4] Bradford, R. M., Pricing, routing, and incentive compatibility in multiserver queues, European Journal of Operational Research, 89, 2, 226-236 (1996) · Zbl 0913.90103 [5] Carlino, D.; Boyles, S. D.; Stone, P., Auction-based autonomous intersection management, Proceedings of the 16th International IEEE conference on intelligent transportation systems (ITSC 2013), 529-534 (2013), IEEE [6] Censi, A.; Bolognani, S.; Zilly, J. G.; Mousavi, S. S.; Frazzoli, E., Today me, tomorrow thee: Efficient resource allocation in competitive settings using karma games, Proceedings of the IEEE intelligent transportation systems conference (ITSC), 686-693 (2019), IEEE [7] Chen, R.; Hu, J.; Levin, M. W.; Rey, D., Stability-based analysis of autonomous intersection management with pedestrians, Transportation Research Part C: Emerging Technologies, 114, 463-483 (2020) [8] Clarke, E. H., Multipart pricing of public goods, Public Choice, 17-33 (1971) [9] De La Fortelle, A.; Qian, X., Autonomous driving at intersections: combining theoretical analysis with practical considerations, Proceedings of the ITS world congress (2015) [10] Dolan, R. J., Incentive mechanisms for priority queuing problems, The Bell Journal of Economics, 421-436 (1978) [11] Down, D. G.; Lewis, M. E., Dynamic load balancing in parallel queueing systems: Stability and optimal control, European Journal of Operational Research, 168, 2, 509-519 (2006) · Zbl 1101.90017 [12] Dresner, K.; Stone, P., Multiagent traffic management: A reservation-based intersection control mechanism, Proceedings of the third international joint conference on autonomous agents and multiagent systems-volume 2, 530-537 (2004), IEEE Computer Society [13] Dresner, K.; Stone, P., A multiagent approach to autonomous intersection management, Journal of Artificial Intelligence Research, 31, 591-656 (2008) [14] Fajardo, D.; Au, T.-C.; Waller, S.; Stone, P.; Yang, D., Automated intersection control: Performance of future innovation versus current traffic signal control, Transportation Research Record: Journal of the Transportation Research Board, 2259, 223-232 (2011) [15] Groves, T.; Loeb, M., Incentives and public inputs, Journal of Public economics, 4, 3, 211-226 (1975) [16] Hassin, R., Rational queueing (2016), CRC Press · Zbl 1348.90003 [17] Hassin, R.; Haviv, M., To queue or not to queue: Equilibrium behavior in queueing systems, 59 (2003), Springer Science & Business Media · Zbl 1064.60002 [18] Jiang, Y.; Li, S.; Shamo, D. E., A platoon-based traffic signal timing algorithm for major-minor intersection types, Transportation Research Part B: Methodological, 40, 7, 543-562 (2006) [19] Kakade, S. M.; Lobel, I.; Nazerzadeh, H., Optimal dynamic mechanism design and the virtual-pivot mechanism, Operations Research, 61, 4, 837-854 (2013) · Zbl 1291.91082 [20] Kittsteiner, T.; Moldovanu, B., Priority auctions and queue disciplines that depend on processing time, Management Science, 51, 2, 236-248 (2005) · Zbl 1232.90151 [21] Levin, M. W.; Rey, D., Conflict-point formulation of intersection control for autonomous vehicles, Transportation Research Part C: Emerging Technologies, 85, 528-547 (2017) [22] Li, Z.; Chitturi, M.; Zheng, D.; Bill, A.; Noyce, D., Modeling reservation-based autonomous intersection control in Vissim, Transportation Research Record: Journal of the Transportation Research Board, 2381, 81-90 (2013) [23] Lin, D., Jabari, S. E., 2020. Pay for intersection priority: A free market mechanism for connected vehicles. arXiv preprint https://arxiv.org/abs/2001.01813. [24] Lioris, J.; Pedarsani, R.; Tascikaraoglu, F. Y.; Varaiya, P., Platoons of connected vehicles can double throughput in urban roads, Transportation Research Part C: Emerging Technologies, 77, 292-305 (2017) [25] Lloret-Batlle, R.; Jayakrishnan, R., Envy-minimizing pareto efficient intersection control with brokered utility exchanges under user heterogeneity, Transportation Research Part B: Methodological, 94, 22-42 (2016) [26] Malikopoulos, A. A.; Cassandras, C. G.; Zhang, Y. J., A decentralized energy-optimal control framework for connected automated vehicles at signal-free intersections, Automatica, 93, 244-256 (2018) · Zbl 1400.93010 [27] Mendelson, H.; Whang, S., Optimal incentive-compatible priority pricing for the m/m/1 queue, Operations research, 38, 5, 870-883 (1990) · Zbl 0723.90023 [28] Mierendorff, K., Optimal dynamic mechanism design with deadlines, Journal of Economic Theory, 161, 190-222 (2016) · Zbl 1369.91071 [29] Mirheli, A.; Tajalli, M.; Hajibabai, L.; Hajbabaie, A., A consensus-based distributed trajectory control in a signal-free intersection, Transportation research part C: emerging technologies, 100, 161-176 (2019) [30] Monteil, J.; Bouroche, M.; Leith, D. J., \( \mathcal{L}_2\) and \(\mathcal{L}_\infty\) stability analysis of heterogeneous traffic with application to parameter optimization for the control of automated vehicles, IEEE Transactions on Control Systems Technology, 27, 3, 934-949 (2018) [31] Naor, P., The regulation of queue size by levying tolls, Econometrica: journal of the Econometric Society, 15-24 (1969) · Zbl 0172.21801 [32] Niroumand, R.; Tajalli, M.; Hajibabai, L.; Hajbabaie, A., Joint optimization of vehicle-group trajectory and signal timing: Introducing the white phase for mixed-autonomy traffic stream, Transportation Research Part C: Emerging Technologies, 116 (2020) [33] Pavan, A.; Segal, I.; Toikka, J., Dynamic mechanism design: A myersonian approach, Econometrica, 82, 2, 601-653 (2014) · Zbl 1419.91147 [34] Rey, D.; Levin, M. W., Blue phase: Optimal network traffic control for legacy and autonomous vehicles, Transportation Research Part B: Methodological, 130, 105-129 (2019) [35] Sayin, M. O.; Lin, C.-W.; Shiraishi, S.; Shen, J.; Başar, T., Information-driven autonomous intersection control via incentive compatible mechanisms, IEEE Transactions on Intelligent Transportation Systems, 20, 3, 912-924 (2018) [36] Schepperle, H.; Böhm, K., Agent-based traffic control using auctions, Proceedings of the international workshop on cooperative information agents, 119-133 (2007), Springer [37] Vasirani, M.; Ossowski, S., A market-inspired approach for intersection management in urban road traffic networks, Journal of Artificial Intelligence Research, 43, 621-659 (2012) · Zbl 1237.90058 [38] Vickrey, W., Counterspeculation, auctions, and competitive sealed tenders, The Journal of finance, 16, 1, 8-37 (1961) [39] Wong, T. W.; Saxena, N.; Dixit, V. V., A study of route choice behavior of drivers in autonomous vehicles, Proceedings of the transportation research board 97th annual meeting (2018), Transportation Research Board [40] Wu, Y.; Chen, H.; Zhu, F., Dcl-aim: Decentralized coordination learning of autonomous intersection management for connected and automated vehicles, Transportation Research Part C: Emerging Technologies, 103, 246-260 (2019) [41] Zhang, Y.; Malikopoulos, A. A.; Cassandras, C. G., Decentralized optimal control for connected automated vehicles at intersections including left and right turns, Proceedings of the IEEE 56th annual conference on decision and control (CDC), 4428-4433 (2017), IEEE [42] Zhang, Y. J.; Malikopoulos, A. A.; Cassandras, C. G., Optimal control and coordination of connected and automated vehicles at urban traffic intersections, Proceedings of the American control conference (ACC), 6227-6232 (2016), IEEE This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.