How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games
Listen
Radio episode about this paper
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.
Alessandro Zanardi, Pier Giuseppe Sessa, Nando Kaslin, Saverio Bolognani, Andrea Censi, Emilio Frazzoli
Swiss National Science Foundation
cs.RO, cs.AI, cs.GT
Submitted: 2022-10-24
Updated: 2022-10-24
Comments: Under review
Journal ref: IEEE Robotics and Automation Letters, 2023 8 (4), 2293 - 2300
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 81/100
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…
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
Summary
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. 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 α? to be the largest constant such that for all agents i and strategies γ ∈ ΓNE ∪ Γ? p. 4 We
define α
? ∈ R+ to be the largest constant such that for all
agents i and strategies γ ∈ ΓNE ∪ Γ
? In this work, we restrict the possible coupling costs among
the players to the ones involving distance. Therefore, the
overall cost for a player has the form Ji(γ) = J
prox
i
(γ) +
J
per
i
(γi) where the first term is a proximity cost–collision at
the limit–and the second term is a personal cost. In this work, we restrict the possible coupling costs among
the players to the ones involving distance. Therefore, the
overall cost for a player has the form Ji(γ) = J
prox
i
(γ) +
J
per
i
(γi) where the first term is a proximity cost–collision at
the limit–and the second term is a personal cost. We then show that
these bounds can be refined thanks to the particular cost
structure of driving games. The following theorem follows from [18] bounding the PoA
as a function of the degree of the polynomial load functions.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Empirical Assessment of Equilibrium Policies
We conduct an experimental case study to evaluate the inefficiency of several driving scenarios We compute equilibrium driving policies via multi-agent reinforcement learning and utilize a systematic approach to empirically approximate the associated PoAs The observed PoAs are within the derived, albeit conservative, bounds This suggests that agents in a driving game can reach very efficient outcomes (i.e., NE policies) in a decentralized fashion via independent learning
Conclusion and Outlook
We have considered the problem of bounding the inefficiency of equilibria in driving games The obtained PoA bounds are the first of their kind in the robotics literature and they open-up interesting related research questions First, there is still quite a gap between our theoretical and experimental setup, yet the reported evidence suggests that PoA bounds could perhaps be derived for such more complex case Second, in line with our theoretical bounds of Sec. IV, it would be interesting to observe how the empirical PoAs change as a function of game-dependent parameters Finally, it would be meaningful to study whether the obtained PoA bounds are tight
REFERENCES
[1] W. Wang, L. Wang, C. Zhang, C. Liu, and L. p. 7 REFERENCES
[1] W. Liu, and L. Liu, and L. Sun, “Social Interactions
for Autonomous Driving: A Review and Perspectives,” arXiv preprint
arXiv:2208.Where the paper says it
Where the paper says it
[8] A Zanardi, E. Mion, M. Bruschetta, S. p. 7 Zanardi, E. Bruschetta, S. How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games
Alessandro Zanardi∗
, Pier Giuseppe Sessa∗
, Nando Kaslin, Saverio Bolognani, Andrea Censi, Emilio Frazzoli ¨
Abstract— We consider the interaction among agents engaging in a driving task and we model it as general-sum game. How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in Urban Driving Games
Alessandro Zanardi∗
, Pier Giuseppe Sessa∗
, Nando Kaslin, Saverio Bolognani, Andrea Censi, Emilio Frazzoli ¨
Abstract— We consider the interaction among agents engaging in a driving task and we model it as general-sum game.Where the paper says it
Where the paper says it
Where the paper says it
[18] S. Aland, D. Dumrauf, M. p. 7 236–259, 3 2002. Dumrauf, M. Dumrauf, M. Gairing, B. Gairing, B. Monien, and F.Where the paper says it
Where the paper says it
Where the paper says it
[28] M. Zhou, J. Luo, J. Villella, Y. p. 7 1870–1881, 10 2019. Villella, Y. Villella, Y. Fadakar, Z.Where the paper says it
Where the paper says it
[30] D Ding, C.-Y Wei, K Zhang
--- Page 7 ---
Observation and Action Spaces: The observation space for each agent is a stacked vector including its own state and the one of all neighboring vehicles within a 50 meter radius More specifically, each state includes the position relative to the goal, the distance to the center of the current lane, the speed, the steering angle, and a list of heading errors Moreover it also includes the stacked states of the two most recent time steps
--- Page 8 ---
For each driving scenario and training run, we inspect convergence (in terms of social cost) and take the corresponding agents’ policies to represent an equilibrium (in case of decentralized training) or a social local optimum (when using centralized training) PoA is computed using the worstperforming equilibrium policy and the socially optimal one observed Interestingly we observe that from multiple decentralized training runs we obtain different “driving cultures” for the agents Two concrete examples are shown in Fig. 6 for the intersection scenario, where different training runs delivered different orders in which the vehicles learn to give each other the right of way For the merging scenarion two different policies are visualized in Fig. p. 6 6 for the
intersection scenario, where different training runs delivered
different orders in which the vehicles learn to give each other
the right of way. For the merging scenarion, two different
policies are visualized in Fig.Where the paper says it
--- Page 9 ---
We consider the class of (urban) driving games akin to [8] They are a particular subclass of general-sum games with few peculiarities Most importantly the cost-structure in a driving game allows to distinguish between joint and personal costs Joint costs depend on the state and actions of all the players, e.g., proximity Personal costs instead depend only on the states and actions of a specific player, e. p. 1 , proximity. Personal costs instead, depend only on the
states and actions of a specific player, e.Where the paper says it
--- Page 10 ---
In this work we restrict the possible coupling costs among the players to the ones involving distance Therefore the overall cost for a player has the form Ji(γ) = J prox i(γ) + J per i(γi) where the first term is a proximity cost–collision at the limit and the second term is a personal cost We further specify the allowed proximity costs to have two properties (i) To be integrable over the trajectory; (ii) To be monotonically increasing as the distance decreases
--- Page 11 ---
Definition 2 (Nash Equilibrium). A trajectory profile γ is a (pure) Nash equilibrium (NE) if ∀i ∈ A, ∀γ 0 i ∈ Γ i Ji(γ) ≤ Ji(γ 0 i, γ−i) We denote the set of NE outcomes as ΓNE ⊆ Γ
--- Page 12 ---
Definition 3 (Social Cost). The social cost C(γ) associated with a specific outcome γ of a game is defined as the sum over all the individual player costs: C(γ):= X i∈A Ji(γ) A game is more efficient if it results in a lower social cost
--- Page 13 ---
Definition 4 (Price of Anarchy). The Price of Anarchy (PoA) is the ratio between the highest social cost at a NE and the lowest social cost overall: PoA = maxγ∈ΓNE C(γ) minγ∈Γ C(γ) ∈ [1, ∞). p. 2 Definition 4 (Price of Anarchy). The Price of Anarchy (PoA)
is the ratio between the highest social cost at a NE and the
lowest social cost overall:
PoA =
maxγ∈ΓNE C(γ)
minγ∈Γ C(γ)
∈ [1, ∞).Where the paper says it
--- Page 14 ---
In general providing PoA bounds is a hard task since these must clearly depend on the specific game and players’ costs structure In the following we show that driving games can be naturally modeled as a particular type of congestion games and suitable PoA bounds can be derived inheriting – and refining– existing guarantees for such specific games’ structure
--- Page 15 ---
We formally show that driving games can be naturally modeled as a particular type of congestion games, where the agents compete for common resources – in this case portions of the road at specific time instances In this spirit we show that the games presented in Sec. II can be (re)modeled as congestion games which preserve the same key properties, allowing us to derive inefficiency bounds
--- Page 16 ---
Congestion games were first introduced in [25] as games where the agents’ strategy corresponds to selecting a subset of the available resources The use of each resource is penalized by a monotonic load function such that, the more players select that resource, the more cost they incur Hence the total cost for a player results in the sum over the load costs of the selected resources
--- Page 17 ---
In this spirit we show that augmenting the resource set along a new dimension that we name “proximity dimension” allows us to model various proximity costs that respect Property 1 The inclusion of the personal costs is instead straightforward (see end of this section) as already shown in the literature
--- Page 18 ---
Property 7. For any player i and others’ trajectories γ−i, consider any pair of feasible trajectories γ i, γ 0 i ∈ Γ i Then if δ(γ 0 i, γj, t) ≤ δ(γ i, γj, t), ∀t, ∀j 6= i it must hold J prox j(γ 0 i, γ−i) ≥ J prox j(γ i, γ−i), ∀j ∈ A
--- Page 19 ---
Personal cost: Following similar works on congestion games [27] we add a personal cost term to the overall cost for player i choosing strategy γ i: Ji(γ) = J cg i(γcg) + J per i(γi) First note that it was shown that such a game retains its exact potential game status, meaning a pure Nash Equilibrium is still guaranteed to exist Moreover as we more formally show in the next section the personal cost can only have a positive influence on the inefficiency bounds of the game
--- Page 20 ---
In this work we consider open-loop strategies, where the players commit to the whole trajectory
--- Page 21 ---
We recall existing PoA bounds for congestion games with polynomial load cost functions We then show that these bounds can be refined thanks to the particular cost structure of driving games
--- Page 22 ---
The following theorem follows from [18] bounding the PoA as a function of the degree of the polynomial load functions Fact 8. For a congestion games with polynomial resource load function with non-negative coefficients and degree at most d ∈ N, it holds PoA ≤ (k + 1)2d+1 − k d+1(k + 2)d (k + 1)d+1 − (k + 2)d + (k + 1)d − k d+1
--- Page 23 ---
Following our congestion game modeling Fact 8 provides a first (and crude) inefficiency guarantee which shows that the driving game becomes less and less efficient the higher is the maximum polynomial degree d We expect however that in practical scenarios d should be rather small (current proximity costs such as (1) assume d = 1) since the actual number of neighbouring cars should have a limited impact on the drivers’ risk
--- Page 24 ---
While Fact 8 provides a range of PoA guarantees depending on the degree d of the driving game we will see that these are quite conservative bounds since they depend only on the agents’ proximity cost J cg i and neglect the personal agents’ preferences Indeed we intuitively expect that in the limit 0 1 2 3 4 5 where the proximity costs J cg i become negligible compared to the personal ones J per i, the agents’ costs become more and more “decoupled” (since the J per i only depends on γi) and thus the game PoA should tend to 1
--- Page 25 ---
To exploit the relative importance between personal and proximity costs we define a main quantity α? Let ΓNE be the set of all NE and Γ? p. 4 Definition 9. Let ΓNE be the set of all NE and Γ
? =
arg minγ∈Γ C(γ) be the set of social optima strategies. We
define α
? We
define α
? ∈ R+ to be the largest constant such that for all
agents i and strategies γ ∈ ΓNE ∪ Γ
?Where the paper says it
Where the paper says it
Where the paper says it
--- Page 26 ---
Theorem 10. Consider driving games modeled as congestion games according to Section III, with polynomial resource load function with non-negative coefficients and degree at most d ∈ N, and α? p. 4 Theorem 10. Consider driving games modeled as congestion
games according to Section III, with polynomial resource
load function with non-negative coefficients and degree at
most d ∈ N. Moreover, consider α
? as per Def. as per Def. Then, PoA
is upper bounded by
(k + 1)2d+1 − k
d+1(k + 2)d + α
?Where the paper says it
Where the paper says it
Where the paper says it
--- Page 4 ---
We consider the problem of bounding the inefficiency of equilibria that emerge in driving games, quantified via the notion of PoA
--- Page 5 ---
We formally 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 We further refine the efficiency guarantees by exploiting the specific cost structure of driving games
--- Page 6 ---
We conduct an experimental case study to evaluate the inefficiency of several driving scenarios We compute equilibrium driving policies via multi-agent reinforcement learning and utilize a systematic approach to empirically approximate the associated PoAs
--- Page 7 ---
The obtained PoA bounds are the first of their kind in the robotics literature and they open-up interesting related research questions First there is still quite a gap between our theoretical and experimental setup, yet the reported evidence suggests that PoA bounds could perhaps be derived for such more complex case Second in line with our theoretical bounds of Sec.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Incorporate novel Price of Anarchy bounds into game-theoretical planners to provide guarantees on any equilibrium players might agree to play, rather than just selecting the most efficient one. This allows for self-interested agents without needing to estimate others’ degree of cooperativeness and eliminates the need for global coordination since decentralized and local solutions can still achieve satisfactory overall cost.
-
Develop analytical bounds that refine existing bounds on the Price of Anarchy by explicitly accounting for the relative trade-off between proximity costs and personal objectives such as comfort and progress. This provides a more nuanced understanding of efficiency in driving games compared to previous models that only considered joint or personal objectives separately.
-
Utilize the congestion game formulation, which models driving games as agents competing for spatio-temporal resources, to derive inefficiency bounds that naturally incorporate the specific cost structure of driving games. This approach allows leveraging existing Price of Anarchy bounds for congestion games while refining them with a dependence on the relative importance between personal and joint costs.
-
Implement a system capable of approximating the Price of Anarchy using MultiAgent Reinforcement Learning (MARL) trained on both centralized and decentralized paradigms, as suggested by the experimental setup. This allows for empirical assessment of efficiency gaps in various driving scenarios, providing evidence that equilibrium policies computed via decentralized learning have social costs comparable to the socially optimum one.
-
Design feedback strategies for autonomous agents using MARL that are capable of converging to qualitatively different equilibria (e.g., different driving
cultures
). This capability is valuable for understanding the topological differences between learned policies and their corresponding homotopic classes, which can be formally described using braid's theory.
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.
Sources
Related papers
- Rethinking Actions: Continuity-Aware Priors for World-Model Planning
- MOSAIC: Modular Obstacle and Spatial-Aware Framework for Manipulation In Cluttered Scenes
- SAGAS: Semantic-Aware Graph-Assisted Stitching for Offline Temporal Logic Planning
- DexSeed: Expanding Human Hand-Object Interactions into Robot Demonstrations for Dexterous Policy Learning
- LaST0.5: A Generalist World Action Model with Interaction-Centric Latent Reasoning
- CIALLO: Learning Shared Intent Representations for Cross-Embodiment Manipulation