Computation of Stackelberg Equilibria of Finite Sequential Games

Branislav Bosanský; Simina Brânzei; Kristoffer Arnsfelt Hansen; Troels Bjerre Lund; Peter Bro Miltersen

doi:10.1145/3133242

Computation of Stackelberg Equilibria of Finite Sequential Games

Branislav Bosanský, Simina Brânzei, Kristoffer Arnsfelt Hansen, Troels Bjerre Lund, Peter Bro Miltersen

Department of Computer Science

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › 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	A C M Transactions on Economics and Computation
Volume	5
Issue	4
Pages (from-to)	23:1-23:24
Number of pages	24
ISSN	2167-8375
DOIs	https://doi.org/10.1145/3133242
Publication status	Published - 22 Dec 2017

Keywords

Algorithmic game theory
Extensive-form correlated equilibrium
Extensive-form games
Finite sequential games
Stackelberg equilibrium
COMPLEXITY
Extensive-Form Correlated Equilibrium
extensive-form games
stackelberg equilibrium
finite sequential games

Access to Document

10.1145/3133242

Cite this

@article{2d1b35f8f28d41f8abd315de90165bc5,

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'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 = "Algorithmic game theory, Extensive-Form Correlated Equilibrium, extensive-form games, finite sequential games, stackelberg equilibrium, Algorithmic game theory, Extensive-form correlated equilibrium, Extensive-form games, Finite sequential games, Stackelberg equilibrium, COMPLEXITY, Extensive-Form Correlated Equilibrium, extensive-form games, stackelberg equilibrium, finite sequential games",

author = "Branislav Bosansk{\'y} and Simina Br{\^a}nzei and Hansen, {Kristoffer Arnsfelt} and Lund, {Troels Bjerre} and Miltersen, {Peter Bro}",

year = "2017",

month = dec,

day = "22",

doi = "10.1145/3133242",

language = "English",

volume = "5",

pages = "23:1--23:24",

journal = "A C M Transactions on Economics and Computation",

issn = "2167-8375",

publisher = "ACM",

number = "4",

}

Computation of Stackelberg Equilibria of Finite Sequential Games. / Bosanský, Branislav; Brânzei, Simina; Hansen, Kristoffer Arnsfelt et al.
In: A C M Transactions on Economics and Computation, Vol. 5, No. 4, 23, 22.12.2017, p. 23:1-23:24.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

TY - JOUR

T1 - Computation of Stackelberg Equilibria of Finite Sequential Games

AU - Bosanský, Branislav

AU - Brânzei, Simina

AU - Hansen, Kristoffer Arnsfelt

AU - Lund, Troels Bjerre

AU - Miltersen, Peter Bro

PY - 2017/12/22

Y1 - 2017/12/22

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 - Algorithmic game theory, Extensive-Form Correlated Equilibrium, extensive-form games, finite sequential games, stackelberg equilibrium

KW - Algorithmic game theory

KW - Extensive-form correlated equilibrium

KW - Extensive-form games

KW - Finite sequential games

KW - Stackelberg equilibrium

KW - COMPLEXITY

KW - Extensive-Form Correlated Equilibrium

KW - extensive-form games

KW - stackelberg equilibrium

KW - finite sequential games

U2 - 10.1145/3133242

DO - 10.1145/3133242

M3 - Journal article

SN - 2167-8375

VL - 5

SP - 23:1-23:24

JO - A C M Transactions on Economics and Computation

JF - A C M 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