Computation of Stackelberg equilibria of finite sequential games

Branislav Bosanski; Simina Branzei; Kristoffer Arnsfelt Hansen; Peter Bro Miltersen; Troels Bjerre Lund

doi:10.1145/3133242

Computation of Stackelberg equilibria of finite sequential games

Branislav Bosanski
, Simina Branzei
, Kristoffer Arnsfelt Hansen
, Peter Bro Miltersen
, Troels Bjerre Lund

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Abstract

The Stackelberg equilibrium is a solution concept that describes optimal strategies to commit to: Player 1 (the leader) first commits to a strategy that is publicly announced, then Player 2 (the follower) plays a best response to the leader’s choice. We study the problem of computing Stackelberg equilibria in finite sequential (i.e., extensive-form) games and provide new exact algorithms, approximation algorithms, and hardness results for finding equilibria for several classes of such two-player games.

Original language	English
Article number	23
Journal	ACM Transactions on Economics and Computation
Volume	5
Issue number	4
ISSN	2167-8375
DOIs	https://doi.org/10.1145/3133242
Publication status	Published - 2017

Keywords

Stackelberg equilibrium
Extensive-form games
Optimal strategies
Sequential games
Algorithmic game theory

Access to Document

10.1145/3133242

1507.07677Accepted author manuscript, 407 KB

https://arxiv.org/pdf/1507.07677

Cite this

@article{089077f4a16f420293e339bd15571235,

title = "Computation of Stackelberg equilibria of finite sequential games",

abstract = "The Stackelberg equilibrium is a solution concept that describes optimal strategies to commit to: Player 1 (the leader) first commits to a strategy that is publicly announced, then Player 2 (the follower) plays a best response to the leader{\textquoteright}s choice. We study the problem of computing Stackelberg equilibria in finite sequential (i.e., extensive-form) games and provide new exact algorithms, approximation algorithms, and hardness results for finding equilibria for several classes of such two-player games.",

keywords = "Stackelberg equilibrium, Extensive-form games, Optimal strategies, Sequential games, Algorithmic game theory, Stackelberg equilibrium, Extensive-form games, Optimal strategies, Sequential games, Algorithmic game theory",

author = "Branislav Bosanski and Simina Branzei and Hansen, \{Kristoffer Arnsfelt\} and Miltersen, \{Peter Bro\} and Lund, \{Troels Bjerre\}",

year = "2017",

doi = "10.1145/3133242",

language = "English",

volume = "5",

journal = "ACM Transactions on Economics and Computation",

issn = "2167-8375",

publisher = "Association for Computing Machinery",

number = "4",

}

TY - JOUR

T1 - Computation of Stackelberg equilibria of finite sequential games

AU - Bosanski, Branislav

AU - Branzei, Simina

AU - Hansen, Kristoffer Arnsfelt

AU - Miltersen, Peter Bro

AU - Lund, Troels Bjerre

PY - 2017

Y1 - 2017

N2 - The Stackelberg equilibrium is a solution concept that describes optimal strategies to commit to: Player 1 (the leader) first commits to a strategy that is publicly announced, then Player 2 (the follower) plays a best response to the leader’s choice. We study the problem of computing Stackelberg equilibria in finite sequential (i.e., extensive-form) games and provide new exact algorithms, approximation algorithms, and hardness results for finding equilibria for several classes of such two-player games.

AB - The Stackelberg equilibrium is a solution concept that describes optimal strategies to commit to: Player 1 (the leader) first commits to a strategy that is publicly announced, then Player 2 (the follower) plays a best response to the leader’s choice. We study the problem of computing Stackelberg equilibria in finite sequential (i.e., extensive-form) games and provide new exact algorithms, approximation algorithms, and hardness results for finding equilibria for several classes of such two-player games.

KW - Stackelberg equilibrium

KW - Extensive-form games

KW - Optimal strategies

KW - Sequential games

KW - Algorithmic game theory

KW - Stackelberg equilibrium

KW - Extensive-form games

KW - Optimal strategies

KW - Sequential games

KW - Algorithmic game theory

U2 - 10.1145/3133242

DO - 10.1145/3133242

M3 - Journal article

SN - 2167-8375

VL - 5

JO - ACM Transactions on Economics and Computation

JF - ACM Transactions on Economics and Computation

IS - 4

M1 - 23

ER -

Computation of Stackelberg equilibria of finite sequential games

Abstract

Keywords

Access to Document

Fingerprint

Cite this