How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games

summary

The gist

We consider the interaction among agents engaging in a driving task and we model it as general-sum game This work studies the (in)efficiency of any equilibrium players might agree to play More…

In short

This work models driving games as congestion games to bound their Price of Anarchy (PoA). By incorporating the specific cost structure of driving—separating joint proximity costs from personal objectives like comfort—the authors derive novel, refined PoA bounds. Empirical results using reinforcement learning confirm that decentralized learning policies achieve social costs close to the optimum.

Key concepts

General-Sum Game
A mathematical framework used to model interactions between multiple agents where the total payoff (or cost) is a sum of individual payoffs. In driving games, this represents how all drivers' decisions collectively affect everyone's experience.
Congestion Game
A specific type of game where agents compete for shared resources, and the cost incurred by an agent depends on how many other agents are using that resource. Driving is modeled as competing for spatio-temporal road space.
Price of Anarchy (PoA)
A measure quantifying the inefficiency of a system's equilibrium. It is calculated as the ratio between the highest social cost found in any Nash Equilibrium and the lowest possible social cost achievable by a socially optimal strategy.

Terminology used across episodes

This episode discusses

The paper

How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games · Read on arXiv

Alessandro Zanardi, Pier Giuseppe Sessa, Nando Kaslin, Saverio Bolognani, Andrea Censi, Emilio Frazzoli

Swiss National Science Foundation

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.

DOI: 10.1109/LRA.2023.3251845

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: I'm Rosa.

Dev: And I'm Dev, here with Taro.

Rosa: We're looking at the paper: "How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games".

Dev: Here's the gist of the paper. We consider the interaction among agents engaging in a driving task and we model it as general-sum game This work studies 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 Modeling Driving Games as Congestion Games We show that driving games can be naturally modeled as a particular type of congestion games, where the agents compete for spatio-temporal resources This allows us to leverage existing PoA bounds for congestion games and apply them to our class of driving games The formulation involves a discretization of the road in both space (i.e.

Rosa: a 2D grid) and time, defining spatio temporal resources as R Each trajectory γi can be mapped to a corresponding strategy γcg i ⊆ R by its spatio-temporal occupancy The load an agent can put on a resource is binary, and the resulting load on resource r is defined as lr(γcg i) = i∈A 1r∈γcg i Refining Efficiency Guarantees We further refine the efficiency guarantees by exploiting the specific cost structure of driving games We derive a novel and improved efficiency bound which depends on the relative importance between personal and joint costs This bound is derived by exploiting the specific cost structure of driving games which consists of joint but also personal objectives We define a main quantity α?

Dev: to be the largest constant such that for all agents i and strategies γ ∈ ΓNE ∪ Γ?, J per i(γi) ≥ α?

Rosa: · J cg i(γcg) Theorem 10 provides an upper bound on PoA that depends on the degree d of the polynomial load functions and the relative importance parameter α?

Title and authors: Rosa: So we're diving into this paper now, "How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games." We're looking at how they frame the problem and who wrote it.

Dev: The authors are Zanardi, Sessa, Kaslin, Bolognani, Censi, and Frazzoli. They bring expertise from game theory and robotics into this study.

Taro: I wonder what that means for us in terms of real-world testing outside the lab where things get messy.

Rosa: It means they're looking at how different driving cultures emerge when agents learn through decentralized training, which is something we see in our own experiments with multi-agent reinforcement learning.

Dev: The paper focuses on bounding the inefficiency of any equilibrium, not just finding the socially optimal one, which is a key distinction from earlier work like that mentioned in eighteen <ref:2210.13064#pg1>.

Taro: So they're giving us guarantees on how bad *any* chosen equilibrium can be, which is useful for safety when you can't coordinate everything perfectly.

Rosa: Right. They formalize the concept of social cost, which is the sum of all individual player costs, and then define Price of Anarchy as the ratio between the highest social cost at a Nash Equilibrium and the lowest social cost possible overall.

The paper's summary: Dev: Now for what they actually did in "How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games." They show that driving games can be naturally modeled as a specific type of congestion game where agents compete for spatio-temporal resources.

Rosa: That's the central modeling step, and it’s crucial because it lets them leverage established PoA bounds for congestion games and apply them directly to our class of driving games.

Taro: So they're taking a known mathematical structure—congestion games—and mapping the physical reality of driving onto that structure using things like 2D grids for space and time.

Dev: They define the load an agent puts on a resource based on its trajectory, where the load is binary, meaning you either occupy a resource or you don't.

Rosa: And then they introduce a way to map each driving trajectory onto a strategy in this congestion game by looking at its spatio-temporal occupancy. That’s how they connect the physical movement to the game structure.

Taro: So, it’s not just saying "driving is like this," it's giving us a formal mapping between the actual driving behavior and the mathematical constraints of a congestion game.

Dev: And then they refine these bounds by exploiting the specific cost structure of driving games, which has both joint costs—things that depend on everyone—and personal costs—things that only depend on one player.

The paper's improvements: Rosa: What they do next is the real refinement. They show that they can derive a novel and improved efficiency bound by looking at the trade-off between those joint costs and those personal objectives, like comfort or progress.

Dev: They introduce this quantity alpha, which is defined as the largest constant such that for any agent and any strategy in an equilibrium or a socially optimal strategy set, the personal cost for that agent is at least alpha times the joint cost.

Taro: That sounds like they are explicitly accounting for how much more important personal comfort objectives are compared to just minimizing the overall traffic congestion.

Rosa: Exactly. They then use this alpha to create Theorem ten which gives an upper bound on the Price of Anarchy that depends on the degree of the polynomial load functions and that relative importance parameter alpha.

Dev: This is a big step because it takes those general congestion game bounds and makes them specific to driving games by incorporating how much personal goals matter.

Taro: It’s interesting because they start with a very conservative bound based only on proximity costs, and then this new theorem incorporates the personal cost structure to tighten it up.

Conclusion: Rosa: So to wrap up, the paper shows that driving games can be modeled as congestion games, which allows them to use existing PoA bounds, but they refine those by incorporating the specific joint and personal costs of driving.

Dev: The main result is Theorem ten which provides a new upper bound on the Price of Anarchy depending on the degree of the polynomial load function and that relative importance parameter alpha.

Taro: From my side, it’s interesting that even with these bounds, they still have a gap between what’s theoretically guaranteed and what we actually see in practice when agents use learned policies.

Rosa: That's true. They mention that while the theoretical setup involves open-loop strategies where players commit to their whole trajectory, they observe efficient equilibria even when agents use closed-loop policies trained via decentralized learning.

Dev: So, the implication is that these new bounds offer a way to understand the inefficiency of any equilibrium without needing perfect global coordination.

Taro: It opens up some interesting questions for future work about how those empirical PoAs change as we vary those game-dependent parameters, like the degree of the load function or alpha.

Rosa: And another big question is whether these derived bounds are actually tight in real driving scenarios, which would be a really important test for this whole framework.

More episodes

← Home