How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games
This work addresses the inefficiency of selfish driving behaviors in multi-agent systems, providing theoretical bounds that are incremental improvements over existing results.
The paper tackles the problem of inefficient equilibria in urban driving games by modeling them as congestion games, obtaining refined bounds on the Price of Anarchy based on parameters like proximity costs and personal objectives. It shows that efficient equilibria can emerge even with closed-loop policies trained via decentralized multi-agent reinforcement learning.
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.