Computation of Stackelberg Equilibria of Finite Sequential Games

Branislav Bosanski; Simina Branzei; Kristoffer Arnsfelt Hansen; Peter Bro Miltersen; Troels Bjerre Sørensen

doi:10.1007/978-3-662-48995-6_15

Computation of Stackelberg Equilibria of Finite Sequential Games

Branislav Bosanski, Simina Branzei, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen

Algorithms

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › 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 Stackelberg equilibria in finite sequential (i.e., extensive-form) games and provide new exact algorithms, approximate algorithms, and hardness results for finding equilibria for several classes of such two-player games.

Original language	English
Title of host publication	LNCS 9470 - Web and Internet Economics : 11th International Conference, WINE 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings
Editors	Evangelos Markakis, Guido Schäfer
Publisher	Springer
Publication date	9 Dec 2015
Pages	201-215
ISBN (Print)	978-3-662-48994-9
ISBN (Electronic)	978-3-662-48995-6
DOIs	https://doi.org/10.1007/978-3-662-48995-6_15
Publication status	Published - 9 Dec 2015
Event	Web and Internet Economics: 11th International Conference - CWI, Amsterdam, Netherlands Duration: 9 Dec 2015 → 15 Dec 2015 http://event.cwi.nl/wine2015/

Conference

Conference	Web and Internet Economics
Location	CWI
Country/Territory	Netherlands
City	Amsterdam
Period	09/12/2015 → 15/12/2015
Internet address	http://event.cwi.nl/wine2015/

Series	Lecture Notes in Computer Science
ISSN	0302-9743

Keywords

Stackelberg equilibrium
Sequential games
Extensive-form games
Algorithm design
Game theory

Access to Document

10.1007/978-3-662-48995-6_15

1507.07677 Computation of Stackelberg Equilibria of Finite Sequential GamesAccepted author manuscript, 407 KB

https://arxiv.org/pdf/1507.07677.pdf

Cite this

Bosanski, B., Branzei, S., Hansen, K. A., Miltersen, P. B., & Sørensen, T. B. (2015). Computation of Stackelberg Equilibria of Finite Sequential Games. In E. Markakis, & G. Schäfer (Eds.), LNCS 9470 - Web and Internet Economics: 11th International Conference, WINE 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings (pp. 201-215). Springer. https://doi.org/10.1007/978-3-662-48995-6_15

Bosanski, Branislav ; Branzei, Simina ; Hansen, Kristoffer Arnsfelt et al. / Computation of Stackelberg Equilibria of Finite Sequential Games. LNCS 9470 - Web and Internet Economics: 11th International Conference, WINE 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings. editor / Evangelos Markakis ; Guido Schäfer. Springer, 2015. pp. 201-215 (Lecture Notes in Computer Science).

@inproceedings{96538eb689964fd49eebc63c723cd874,

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 Stackelberg equilibria in finite sequential (i.e., extensive-form) games and provide new exact algorithms, approximate algorithms, and hardness results for finding equilibria for several classes of such two-player games.",

keywords = "Stackelberg equilibrium, Sequential games, Extensive-form games, Algorithm design, Game theory, Stackelberg equilibrium, Sequential games, Extensive-form games, Algorithm design, Game theory",

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

year = "2015",

month = dec,

day = "9",

doi = "10.1007/978-3-662-48995-6_15",

language = "English",

isbn = "978-3-662-48994-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "201--215",

editor = "Evangelos Markakis and Guido Sch{\"a}fer",

booktitle = "LNCS 9470 - Web and Internet Economics",

address = "Germany",

note = "Web and Internet Economics : 11th International Conference, WINE 2015 ; Conference date: 09-12-2015 Through 15-12-2015",

url = "http://event.cwi.nl/wine2015/",

}

Bosanski, B, Branzei, S, Hansen, KA, Miltersen, PB & Sørensen, TB 2015, Computation of Stackelberg Equilibria of Finite Sequential Games. in E Markakis & G Schäfer (eds), LNCS 9470 - Web and Internet Economics: 11th International Conference, WINE 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings. Springer, Lecture Notes in Computer Science, pp. 201-215, Web and Internet Economics, Amsterdam, Netherlands, 09/12/2015. https://doi.org/10.1007/978-3-662-48995-6_15

Computation of Stackelberg Equilibria of Finite Sequential Games. / Bosanski, Branislav; Branzei, Simina; Hansen, Kristoffer Arnsfelt et al.
LNCS 9470 - Web and Internet Economics: 11th International Conference, WINE 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings. ed. / Evangelos Markakis; Guido Schäfer. Springer, 2015. p. 201-215 (Lecture Notes in Computer Science).

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

TY - GEN

T1 - Computation of Stackelberg Equilibria of Finite Sequential Games

AU - Bosanski, Branislav

AU - Branzei, Simina

AU - Hansen, Kristoffer Arnsfelt

AU - Miltersen, Peter Bro

AU - Sørensen, Troels Bjerre

PY - 2015/12/9

Y1 - 2015/12/9

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 Stackelberg equilibria in finite sequential (i.e., extensive-form) games and provide new exact algorithms, approximate 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 Stackelberg equilibria in finite sequential (i.e., extensive-form) games and provide new exact algorithms, approximate algorithms, and hardness results for finding equilibria for several classes of such two-player games.

KW - Stackelberg equilibrium

KW - Sequential games

KW - Extensive-form games

KW - Algorithm design

KW - Game theory

KW - Stackelberg equilibrium

KW - Sequential games

KW - Extensive-form games

KW - Algorithm design

KW - Game theory

U2 - 10.1007/978-3-662-48995-6_15

DO - 10.1007/978-3-662-48995-6_15

M3 - Article in proceedings

SN - 978-3-662-48994-9

T3 - Lecture Notes in Computer Science

SP - 201

EP - 215

BT - LNCS 9470 - Web and Internet Economics

A2 - Markakis, Evangelos

A2 - Schäfer, Guido

PB - Springer

T2 - Web and Internet Economics

Y2 - 9 December 2015 through 15 December 2015

ER -

Bosanski B, Branzei S, Hansen KA, Miltersen PB, Sørensen TB. Computation of Stackelberg Equilibria of Finite Sequential Games. In Markakis E, Schäfer G, editors, LNCS 9470 - Web and Internet Economics: 11th International Conference, WINE 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings. Springer. 2015. p. 201-215. (Lecture Notes in Computer Science). doi: 10.1007/978-3-662-48995-6_15

Computation of Stackelberg Equilibria of Finite Sequential Games

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this