How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games
- 3 March 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Robotics and Automation Letters
- Vol. 8 (4) , 2293-2300
Abstract
We consider the interaction among agents engaging in a driving task and we model it as general-sum game. This class of games exhibits a plurality of different equilibria posing the issue of equilibrium selection. While selecting the most efficient equilibrium (in term of social cost) is often impractical from a computational standpoint, in this work we study the (in)efficiency of any equilibrium players might agree to play. More specifically, we bound the equilibrium inefficiency by modeling driving games as particular type of congestion games over spatio-temporal resources. We obtain novel guarantees that refine existing bounds on the Price of Anarchy (PoA) as a function of problem-dependent game parameters. For instance, the relative trade-off between proximity costs and personal objectives such as comfort and progress. Although the obtained guarantees concern open-loop trajectories, we observe efficient equilibria even when agents employ closed-loop policies trained via decentralized multi-agent reinforcement learning.Keywords
All Related Versions
Funding Information
- Swiss National Science Foundation funder NCCR Automation (51NF40_80545)
This publication has 24 references indexed in Scilit:
- Human-robot interaction for truck platooning using hierarchical dynamic games2019
- Congestion Games With Player-Specific Utility Functions and Its Application to NFV NetworksIEEE Transactions on Automation Science and Engineering, 2019
- Autonomous agents modelling other agents: A comprehensive survey and open problemsArtificial Intelligence, 2018
- A generalized Nash equilibrium approach for optimal control problems of autonomous carsOptimal Control Applications and Methods, 2017
- Planning for Autonomous Cars that Leverage Effects on Human Actions2016
- Exact Price of Anarchy for Polynomial Congestion GamesSIAM Journal on Computing, 2011
- Worst-case equilibriaComputer Science Review, 2009
- Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions2003
- How bad is selfish routing?Journal of the ACM, 2002
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973