Solution Concepts in Hierarchical Games with Applications to Autonomous Driving

Atrisha Sarkar, Krzysztof Czarnecki

Abstract

Autonomous vehicle (AV) motion planning is increasingly viewed as a multi-agent problem. However, the standard assumption of complete rationality is often unrealistic for human drivers. This paper explores bounded rationality through a behavioral game theoretic lens, adapting metamodels like Quantal level-k and Nash equilibrium with quantal errors. We formalize these concepts within a hierarchical game framework—separating strategic maneuvers from tactical trajectories. Using a large-scale naturalistic dataset of human driving at a busy urban intersection, we evaluate these models. Our results indicate that modeling behavior as a Pure Strategy Nash Equilibrium (PNE) with quantal errors at the maneuver level, combined with bounds sampling at the trajectory level, provides the most accurate fit to real-world data.

Introduction

Traditional AV motion planners often treat the environment as static or assume other agents are perfectly rational actors. In reality, driving is a symbiotic multi-agent interaction where one driver's actions directly influence another's. To bridge the gap between mathematical models and human behavior, we must account for "bounded rationality"—the idea that humans have limited cognitive resources and make probabilistic errors. This paper proposes a hierarchical game structure to maintain computational efficiency while capturing the nuances of human decision-making.

The Hierarchical Game Framework

The proposed framework decomposes the complex task of driving into two distinct levels:

  1. Level 1 (Maneuvers): A high-level strategic game where agents choose from discrete actions (e.g., "proceed," "yield," "turn").
  2. Level 2 (Trajectories): A lower-level tactical game where agents select specific continuous paths and velocity profiles to execute their chosen maneuvers.
Hierarchical game structure showing the mapping between high-level maneuvers and low-level trajectory payoffs.

This hierarchy allows for different solution concepts at each level. For example, strategic reasoning might occur at the maneuver level, while the trajectory level focuses on smooth execution and safety constraints. This separation significantly reduces the computational complexity compared to solving a single continuous differential game.

Modeling Bounded Rationality

We evaluate several behavioral models to find which best reflects human driving:

  • Quantal Level-k (QLk): Agents reason in levels. Level-0 acts non-strategically, while Level-1 best-responds to a belief that others are Level-0.
  • QLkR (Rule-following): A variation where Level-0 agents are assumed to strictly follow traffic rules, reflecting the social contract of the road.
  • PNE-QE: Pure Strategy Nash Equilibrium with Quantal Errors, which assumes agents aim for equilibrium but occasionally make sub-optimal choices based on a probability distribution.

Empirical Evaluation

The models were tested using the Waterloo Multi-Agent Traffic Dataset, which contains high-fidelity trajectory data from a busy urban intersection. The dataset includes approximately 4,000 agents and 44,000 decision points, focusing on complex right-turning and left-turning scenarios.

Aerial view of the urban intersection used for data collection, showing vehicle trajectories and agent IDs.

Key Results and Discussion

Our analysis reveals several critical insights into human driving behavior:

  • Model Performance: The PNE-QE model at the maneuver level, paired with bounds sampling (S(1+B)) for trajectories, provided the best fit to naturalistic data. Bounds sampling considers both normative paths and physical limits, capturing the range of human tactical choices.
  • The Power of Rule-Following: Models that assume others follow basic traffic rules (Level-0 as rule-followers) significantly outperformed those assuming random behavior. This suggests humans navigate intersections primarily by expecting others to adhere to the law, simplifying their own strategic calculations.
  • Predictive Accuracy: The rule-based model achieved 78% accuracy in predicting maneuvers, closely followed by QLkR at 75%. Both significantly outperformed traditional, perfectly rational Nash Equilibrium models.
  • Situational Sensitivity: Human "rationality" is not static. Drivers become more predictable and adhere closer to optimal strategies during high-stakes situations, such as when a traffic light is about to turn red.

Conclusion

Moving beyond the "perfectly rational" assumption is vital for safe and natural AV integration. By employing a hierarchical game framework and behavioral models like PNE-QE, we can better predict human maneuvers and trajectories. Our findings highlight that modeling human behavior as a combination of strategic maneuver selection and rule-based tactical execution provides a robust path forward for autonomous motion planning.

Summary updated

Abstract

With autonomous vehicles (AV) set to integrate further into regular human traffic, there is an increasing consensus of treating AV motion planning as a multi-agent problem. However, the traditional game theoretic assumption of complete rationality is too strong for the purpose of human driving, and there is a need for understanding human driving as a \emph{bounded rational} activity through a behavioral game theoretic lens. To that end, we adapt three metamodels of bounded rational behavior; two based on Quantal level-k and one based on Nash equilibrium with quantal errors. We formalize the different solution concepts that can be applied in the context of hierarchical games, a framework used in multi-agent motion planning, for the purpose of creating game theoretic models of driving behavior. Furthermore, based on a contributed dataset of human driving at a busy urban intersection with a total of ~4k agents and ~44k decision points, we evaluate the behavior models on the basis of model fit to naturalistic data, as well as their predictive capacity. Our results suggest that among the behavior models evaluated, modeling driving behavior as pure strategy NE with quantal errors at the level of maneuvers with bounds sampling of actions at the level of trajectories provides the best fit to naturalistic driving behavior, and there is a significant impact of situational factors on the performance of behavior models.
BibTeX
@misc{sarkar2020solution,
  author = {Atrisha Sarkar and Krzysztof Czarnecki},
  title = {{Solution Concepts in Hierarchical Games with Applications to Autonomous Driving}},
  year = {2020},
  eprint = {2009.10033},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.10033},
}
Figure