Approximation methods for infinite Bayesian Stackelberg games: modeling distributional payoff uncertainty

Game theory is fast becoming a vital tool for reasoning about complex real-world security problems, including critical infrastructure protection. The game models for these applications are constructed using expert analysis and historical data to estimate the values of key parameters, including the preferences and capabilities of terrorists. In many cases, it would be natural to represent uncertainty over these parameters using continuous distributions (such as uniform intervals or Gaussians). However, existing solution algorithms are limited to considering a small, finite number of possible attacker types with different payoffs. We introduce a general model of infinite Bayesian Stackelberg security games that allows payoffs to be represented using continuous payoff distributions. We then develop several techniques for finding approximate solutions for this class of games, and show empirically that our methods offer dramatic improvements over the current state of the art, providing new ways to improve the robustness of security game models.

• Publication year

  2011

• Venue

  Adaptive Agents and Multi-Agent Systems

• Publication date

  2011-05-02

• Fields of study

  Mathematics, Computer Science, Political Science

• Identifiers
  DOI 10.1017/CBO9780511973031.011
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Security and Game Theory: IRIS – A Tool for Strategic Security Allocation in Transportation Networks

  2011cited by this paper
• Quality-bounded solutions for finite Bayesian Stackelberg games: scaling up

  2011cited by this paper
• Adversarial Uncertainty in Multi-Robot Patrol

  2009cited by this paper
• Computing Bayes-Nash Equilibria through Support Enumeration Methods in Bayesian Two-Player Strategic-Form Games

  2009cited by this paper
• Effective solutions for real-world Stackelberg games: when agents must deal with human uncertainties

  2009cited by this paper
• Leader-follower strategies for robotic patrolling in environments with arbitrary topologies

  2009influential reference
• Computing optimal randomized resource allocations for massive security games

  2009influential reference
• Security Games with Incomplete Information

  2009cited by this paper
• Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport

  2008cited by this paper
• Game Theoretical Insights in Strategic Patrolling: Model and Algorithm in Normal-Form

  2008cited by this paper
• Approximation of Bayesian Nash Equilibrium

  2008cited by this paper
• Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games

  2008cited by this paper
• Choosing What to Protect

  2007influential reference
• Robust game theory

  2006cited by this paper
• Computing the optimal strategy to commit to

  2006cited by this paper
• Game strategies in network security

  2005cited by this paper
• Monte Carlo approximation in incomplete information, sequential auction games

  2005cited by this paper
• Computing Best-Response Strategies in Infinite Games of Incomplete Information

  2004cited by this paper
• A game theoretic approach to decision and analysis in network intrusion detection

  2003cited by this paper
• Terrorism & Game Theory

  2003cited by this paper
• Evolutionarily Stable Strategies and Game Dynamics

  1978cited by this paper
• Quantal Choice Analysis: A Survey

  1976cited by this paper
• Games with Incomplete Information Played by 'Bayesian' Players, Part III. The Basic Probability Distribution of the Game

  1968cited by this paper
• Games And Decisions

  1958influential reference
• Marktform und Gleichgewicht

  1935cited by this paper

• Designing policies for transition-independent multiagent systems that are robust to communication loss

  2025cites this paper
• Randomization to Reduce Terror Threats at Large Venues

  2025cites this paper
• A survey on bilevel optimization under uncertainty

  2023cites this paper
• Social Choice for Social Good: Proposals for Democratic Innovation from Computer Science

  2022cites this paper
• Robust Solutions for Multi-Defender Stackelberg Security Games

  2022cites this paper
• Convergence of Bayesian Nash Equilibrium in Infinite Bayesian Games under Discretization

  2021cites this paper
• An extended area-partition-involved collaborative patrolling game in chemical clusters considering attackers’ bounded rationality and parameter uncertainty

  2021cites this paper
• Evaluating Attacker Risk Behavior in an Internet of Things Ecosystem

  2021cites this paper
• A decision support framework for security resource allocation under ambiguity

  2020cites this paper
• Finding Equilibrium in Multi-Agent Games with Payoff Uncertainty

  2020cites this paper
• Exploiting Bounded Rationality in Risk-Based Cyber Camouflage Games

  2020cites this paper
• Privacy Computing: Concept, Computing Framework And Future Development Trends

  2019cites this paper
• Cyber Camouflage Games for Strategic Deception

  2019cites this paper
• General-Sum Cyber Deception Games under Partial Attacker Valuation Information

  2019cites this paper
• Adversarial Robustness of Similarity-Based Link Prediction

  2019cites this paper
• Security Games with Interval Uncertainty

  2019influential citation
• Integrating the API SRA methodology and game theory for improving chemical plant protection

  2018cites this paper
• Designing the Game to Play: Optimizing Payoff Structure in Security Games

  2018cites this paper
• Decision Making in Multiagent Systems: A Survey

  2018cites this paper
• Stackelberg Security Games ( SSG ) Basics and Application Overview

  2018cites this paper
• Solving Stackelberg security Markov games employing the bargaining Nash approach: Convergence analysis

  2018cites this paper
• Applying game theory for adversarial risk analysis in chemical plants

  2018cites this paper
• Single Plant Protection: Playing the Chemical Plant Protection Game with Distribution-Free Uncertainties

  2018cites this paper
• Economic Consequences of Terrorism and Natural Disasters: The Computable General Equilibrium Approach

  2017cites this paper
• Validating Terrorism Risk Assessment Models – Lessons Learned from 11 Models

  2017cites this paper
• Economically Optimal Variable Tag Length Message Authentication

  2017cites this paper
• Economic Resilience to Terrorism and Natural Hazards

  2017cites this paper
• Achieving multiple objectives with limited resources: Using utility theory and control theory

  2017cites this paper
• Organizational Decision Processes

  2017cites this paper
• Multi-objective Decision Making: Expected Utility vs. Some Widely Used (and Flawed) Methods

  2017cites this paper
• Playing Repeated Security Games with No Prior Knowledge

  2016cites this paper
• Defender–Attacker Decision Tree Analysis to Combat Terrorism

  2016cites this paper
• Joint cost-sharing and multi-relay selection for two-way relay networks using a pricing game

  2016cites this paper
• Preserving Location Privacy in Radio Networks Using a Stackelberg Game Framework

  2016cites this paper
• Gradient Methods for Stackelberg Games

  2016cites this paper
• Relay selection for energy harvesting relay networks using a repeated game

  2016cites this paper
• Moving Target Defense for Web Applications using Bayesian Stackelberg Games: (Extended Abstract)

  2016cites this paper
• Abstraction Methods for Solving Graph-Based Security Games

  2016influential citation
• Towards Selecting the Best Abstraction for a Patrolling Game

  2015cites this paper
• Discretization of Continuous Action Spaces in Extensive-Form Games

  2015cites this paper
• Passivity-Based Distributed Strategies for Stochastic Stackelberg Security Games

  2015cites this paper
• Quantifying mixed uncertainties in cyber attacker payoffs

  2015cites this paper
• Learning to Play Stackelberg Security Games

  2015cites this paper
• Commitment Without Regrets: Online Learning in Stackelberg Security Games

  2015cites this paper
• Combining Online Learning and Equilibrium Computation in Security Games

  2015cites this paper
• Stackelberg Security Games (SSG) Basics and Application Overview

  2015cites this paper
• Decision and Game Theory for Security

  2015influential citation
• Persistent patrolling in the presence of adversarial observers

  2014cites this paper
• Human Adversaries in Security Games: Integrating Models of Bounded Rationality and Fast Algorithms

  2014cites this paper
• Stop the compartmentalization: unified robust algorithms for handling uncertainties in security games

  2014cites this paper
• Learning Optimal Commitment to Overcome Insecurity

  2014cites this paper
• Regret-Based Optimization and Preference Elicitation for Stackelberg Security Games with Uncertainty

  2014cites this paper
• Lazy Defenders Are Almost Optimal against Diligent Attackers

  2014cites this paper
• Thwarting Adversaries with Unpredictability: Massive-scale Game-Theoretic Algorithms for Real-world Security Deployments

  2013cites this paper
• Security games with contagion: handling asymmetric information

  2013cites this paper
• Security games with interval uncertainty

  2013influential citation
• A Deployed Quantal Response-Based Patrol Planning System for the U.S. Coast Guard

  2013influential citation
• Bayesian Security Games for Controlling Contagion

  2013cites this paper
• Efficient Evolutionary Dynamics with Extensive-Form Games

  2013cites this paper
• Computational Game Theory for Security : Progress and Challenges ∗

  2013cites this paper
• PROTECT in the Ports of Boston, New York and Beyond: Experiences in Deploying Stackelberg Security Games with Quantal Response

  2013cites this paper
• Security Games Applied to Real-World : Research Contributions and Challenges Report Title

  2013cites this paper
• Improving resource allocation strategies against human adversaries in security games: An extended study

  2013cites this paper
• Security Games Applied to Real-World: Research Contributions and Challenges

  2013cites this paper
• An Ambiguity Aversion Framework of Security Games under Ambiguities

  2013cites this paper
• Protecting networks against diffusive attacks: game-theoretic resource allocation for contagion mitigation

  2013influential citation
• Financial Cryptography and Data Security

  2012influential citation
• Getting Started on a Real-World Challenge Problem in Computational Game Theory and Beyond

  2012cites this paper
• Developing Algorithms and Soft ware Assistants for Security Domains

  2012cites this paper
• A unified method for handling discrete and continuous uncertainty in Bayesian Stackelberg games

  2012influential citation
• PROTECT: a deployed game theoretic system to protect the ports of the United States

  2012influential citation
• The human element: addressing human adversaries in security domains

  2012cites this paper
• Game Theory for Security: A Real-World Challenge Problem for Multiagent Systems and Beyond

  2012cites this paper
• Playing repeated Stackelberg games with unknown opponents

  2012cites this paper
• PROTECT: An Application of Computational Game Theory for the Security of the Ports of the United States

  2012cites this paper
• Game theory for security: Key algorithmic principles, deployed systems, lessons learned

  2012cites this paper
• Addressing uncertainty in stackelberg games for security: models and algorithms

  2012cites this paper
• An Overview of Recent Application Trends at the AAMAS Conference: Security, Sustainability and Safety

  2012cites this paper
• PROTECT - A Deployed Game Theoretic System for Strategic Security Allocation for the United States Coast Guard

  2012cites this paper
• Efficient Approximation for Security Games with Interval Uncertainty

  2012cites this paper
• Security and Game Theory: Evaluating Deployed Decision-Support Systems for Security: Challenges, Analysis, and Approaches

  2011cites this paper
• Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness

  2011cites this paper
• GUARDS and PROTECT: next generation applications of security games

  2011cites this paper
• Security and Game Theory - Algorithms, Deployed Systems, Lessons Learned

  2011cites this paper
• Quality-bounded solutions for finite Bayesian Stackelberg games: scaling up

  2011cites this paper
• A Value Model for Evaluating Homeland Security Decisions

  2011cites this paper
• Game Theory for Security: An Important Challenge for Multiagent Systems

  2011cites this paper