PaperlayerView exact revision on arXiv

Source-linked AI summary

Open problem: Computing Bayes-Nash equilibrium in simple security games

Vincent Conitzer

arXiv:2610.08796v1cs.GT

TL;DR

The paper poses the question of whether Bayesian simple security games admit polynomial-time Bayes-Nash equilibrium computation. It describes a seemingly fast algorithm but cannot prove that it always runs in polynomial time, leaving the question open.

  • Problem

    The paper asks whether a Bayes-Nash equilibrium can be computed in polynomial time for Bayesian simple security games.

    Source: §1 · p. 1

  • Method

    The authors describe a complicated, seemingly fast algorithm for computing Bayes-Nash equilibrium in these games.

    Source: §2 · p. 1

  • Results

    The algorithm's polynomial-time guarantee is unproved, so whether it always runs in polynomial time remains unresolved.

    Source: §2 · p. 1, §1 · p. 1

  • Takeaways & Limitations

    The games' Bayes-Nash equilibria satisfy interchangeability, so equilibrium selection is not an issue.

    Source: §2 · p. 1

Abstract

from arXiv · show

This is an open problem originally posed during the program "Economics and Computation" held in the Fall 2015 semester at the Simons Institute for the Theory of Computing. It asks whether a (Bayes-)Nash equilibrium can be computed in polynomial time for Bayesian simple security games.

1 The problem

Bayesian simple security games specify targets, attacker types with probabilities, and utilities that depend on whether a target is defended. The open problem asks whether a Bayes-Nash equilibrium can be computed in polynomial time.

1 The problem

  • The game specifies targets, attacker types with a probability distribution, and utilities for the defender and attacker.Source: §1 · p. 1
  • The defender assigns resources to a subset of r targets, then the attacker learns his type and chooses a target to attack.Source: §1 · p. 1
  • Utilities depend on whether the attacked target received a defensive resource.Source: §1 · p. 1
  • The open problem is whether a Bayes-Nash equilibrium can be computed in polynomial time for Bayesian simple security games.Source: §1 · p. 1

2 Further background

The background contrasts equilibrium computation in security games with the usual normal-form setting. It describes an algorithm for Bayes-Nash equilibrium whose polynomial-time guarantee is unknown.

2 Further background

  • In the structured security-game setting, the usual normal-form complexity picture seems reversed: Stackelberg mixed strategies are NP-hard, while the Bayes-Nash algorithm's polynomial-time guarantee is unproved.Source: §2 · p. 1
  • The described Bayes-Nash algorithm is complicated and seemingly fast, but the authors cannot prove whether it always runs in polynomial time.Source: §2 · p. 1
  • For a simpler non-Bayesian variant with multiple attacker resources, a similar algorithm solves the problem in polynomial time.Source: §2 · p. 1
  • The games' Bayes-Nash equilibria satisfy interchangeability, so equilibrium selection is not an issue.Source: §2 · p. 1
Loading 2610.08796v1…