Sequence-Form Algorithm for Computing Stackelberg Equilibria in Extensive-Form Games

Kód výsledku v 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>

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

Sequence-Form Algorithm for Computing Stackelberg Equilibria in Extensive-Form Games

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Sequence-Form Algorithm for Computing Stackelberg Equilibria in Extensive-Form Games

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F12%2F2054" target="_blank" >GAP202/12/2054: Bezpečnostní hry v extenzivní formě</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

—

Počet stran výsledku

7

Strana od-do

805-811

Název nakladatele

AAAI Press

Místo vydání

Menlo Park

Místo konání akce

Hyatt Regency in Austin, Texas

Datum konání akce

25. 1. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—