Incremental Strategy Generation for Stackelberg Equilibria in Extensive-Form Games

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Incremental Strategy Generation for Stackelberg Equilibria in Extensive-Form Games
Original language description
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.
Czech name
—
Czech description
—

Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

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

Article name in the collection
Proceedings of the 2018 ACM Conference on Economics and Computation
ISBN
978-1-4503-5829-3
ISSN
—
e-ISSN
—
Number of pages
18
Pages from-to
151-168
Publisher name
ACM
Place of publication
New York
Event location
Ithaca
Event date
Jun 18, 2018
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)