Incremental Strategy Generation for 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%2F18%3A00322880" target="_blank" >RIV/68407700:21230/18:00322880 - isvavai.cz</a>

Výsledek na webu

<a href="http://delivery.acm.org/10.1145/3220000/3219219/p151-cerny.pdf?ip=147.32.83.147&id=3219219&acc=ACTIVE%20SERVICE&key=D6C3EEB3AD96C931%2E9BD1EC80ACA8C1C5%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35&__acm__=1536327681_de8d11458a98df57c4dc2419c033adca" target="_blank" >http://delivery.acm.org/10.1145/3220000/3219219/p151-cerny.pdf?ip=147.32.83.147&id=3219219&acc=ACTIVE%20SERVICE&key=D6C3EEB3AD96C931%2E9BD1EC80ACA8C1C5%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35&__acm__=1536327681_de8d11458a98df57c4dc2419c033adca</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3219166.3219219" target="_blank" >10.1145/3219166.3219219</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Incremental Strategy Generation for Stackelberg Equilibria in Extensive-Form Games

Popis výsledku v původním jazyce

Dynamic interaction appears in many real-world scenarios where players are able to observe (perhaps imperfectly) the actions of another player and react accordingly. We consider the baseline representation of dynamic games - the extensive form - and focus on computing Stackelberg equilibrium (SE), where the leader commits to a strategy to which the follower plays a best response. For one-shot games (e.g., security games), strategy-generation (SG) algorithms offer dramatic speed-up by incrementally expanding the strategy spaces. However, a direct application of SG to extensive-form games (EFGs) does not bring a similar speed-up since it typically results in a nearly-complete strategy space. Our contributions are twofold: (1) for the first time we introduce an algorithm that allows us to incrementally expand the strategy space to find a SE in EFGs; (2) we introduce a heuristic variant of the algorithm that is theoretically incomplete, but in practice allows us to find exact (or close-to optimal) Stackelberg equilibrium by constructing a significantly smaller strategy space. Our experimental evaluation confirms that we are able to compute SE by considering only a fraction of the strategy space that often leads to a significant speed-up in computation times.

Název v anglickém jazyce

Incremental Strategy Generation for Stackelberg Equilibria in Extensive-Form Games

Popis výsledku anglicky

Dynamic interaction appears in many real-world scenarios where players are able to observe (perhaps imperfectly) the actions of another player and react accordingly. We consider the baseline representation of dynamic games - the extensive form - and focus on computing Stackelberg equilibrium (SE), where the leader commits to a strategy to which the follower plays a best response. For one-shot games (e.g., security games), strategy-generation (SG) algorithms offer dramatic speed-up by incrementally expanding the strategy spaces. However, a direct application of SG to extensive-form games (EFGs) does not bring a similar speed-up since it typically results in a nearly-complete strategy space. Our contributions are twofold: (1) for the first time we introduce an algorithm that allows us to incrementally expand the strategy space to find a SE in EFGs; (2) we introduce a heuristic variant of the algorithm that is theoretically incomplete, but in practice allows us to find exact (or close-to optimal) Stackelberg equilibrium by constructing a significantly smaller strategy space. Our experimental evaluation confirms that we are able to compute SE by considering only a fraction of the strategy space that often leads to a significant speed-up in computation times.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

V - Vyzkumna aktivita podporovana z jinych verejnych zdroju

Rok uplatnění

2018

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 2018 ACM Conference on Economics and Computation

ISBN

978-1-4503-5829-3

ISSN

—

e-ISSN

—

Počet stran výsledku

18

Strana od-do

151-168

Název nakladatele

ACM

Místo vydání

New York

Místo konání akce

Ithaca

Datum konání akce

18. 6. 2018

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

WRD - Celosvětová akce

Kód UT WoS článku

—