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

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › 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.

Originalsprog	Engelsk
Artikelnummer	23
Tidsskrift	ACM Transactions on Economics and Computation
Vol/bind	5
Udgave nummer	4
ISSN	2167-8375
DOI	https://doi.org/10.1145/3133242
Status	Udgivet - 2017

Emneord

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

Adgang til dokumentet

10.1145/3133242

1507.07677Accepteret manuskript, 407 KB

https://arxiv.org/pdf/1507.07677

Citationsformater

@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

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater