Sequence-Form Algorithm for Computing Stackelberg Equilibria in Extensive-Form Games
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F15%3A00235170" target="_blank" >RIV/68407700:21230/15:00235170 - isvavai.cz</a>
Result on the web
<a href="http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9610" target="_blank" >http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9610</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Sequence-Form Algorithm for Computing Stackelberg Equilibria in Extensive-Form Games
Original language description
Stackelberg equilibrium is a solution concept prescribing for a player an optimal strategy to commit to, assuming the opponent knows this commitment and plays the best response. Although this solution concept is a cornerstone of many security applications, the existing works typically do not consider situations where the players can observe and react to the actions of the opponent during the course of the game. We extend the existing algorithmic work to extensive-form games and introduce novel algorithmfor computing Stackelberg equilibria that exploits the compact sequence-form representation of strategies. Our algorithm reduces the size of the linear programs from exponential in the baseline approach to linear in the size of the game tree. Experimental evaluation on randomly generated games and a security-inspired search game demonstrates significant improvement in the scalability compared to the baseline approach.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GAP202%2F12%2F2054" target="_blank" >GAP202/12/2054: Security Games in Extensive Form</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference
ISBN
978-1-57735-698-1
ISSN
2159-5399
e-ISSN
—
Number of pages
7
Pages from-to
805-811
Publisher name
AAAI Press
Place of publication
Menlo Park
Event location
Hyatt Regency in Austin, Texas
Event date
Jan 25, 2015
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—