Finite State Machines Play Extensive-Form Games

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00348090" target="_blank" >RIV/68407700:21230/20:00348090 - isvavai.cz</a>

Výsledek na webu

<a href="https://dl.acm.org/doi/abs/10.1145/3391403.3399517" target="_blank" >https://dl.acm.org/doi/abs/10.1145/3391403.3399517</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Finite State Machines Play Extensive-Form Games

Popis výsledku v původním jazyce

Finite state machines are a well-known representation of strategies in (in)finitely repeated or stochastic games. Actions of players correspond to states in the machine and the transition between machine-states are caused by observations in the game. For extensive-form games (EFGs), machines can act as a formal grounding for abstraction methods used for solving large EFGs and as a domain-independent approach for generating sufficiently compact abstractions. We show that using machines of a restricted size in EFGs can both (i) reduce the theoretical complexity of computing some solution concepts, including Strong Stackelberg Equilibrium (SSE), (ii) as well as bring new practical algorithms that compute near-optimal equilibria considering only a fraction of strategy space. Our contributions include (1) formal definition and theoretical characterization of machine strategies in EFGs, (2) formal definitions and complexity analysis for solution concepts and their computation when restricted to small classes of machines, (3) new algorithms for computing SSE in general-sum games and Nash Equilibrium in zero-sum games that both directly use the concept of machines. Experimental results on two different domains show that the algorithms compute near-optimal strategies and achieve significantly better scalability compared to previous state-of-the-art algorithms.

Název v anglickém jazyce

Finite State Machines Play Extensive-Form Games

Popis výsledku anglicky

Finite state machines are a well-known representation of strategies in (in)finitely repeated or stochastic games. Actions of players correspond to states in the machine and the transition between machine-states are caused by observations in the game. For extensive-form games (EFGs), machines can act as a formal grounding for abstraction methods used for solving large EFGs and as a domain-independent approach for generating sufficiently compact abstractions. We show that using machines of a restricted size in EFGs can both (i) reduce the theoretical complexity of computing some solution concepts, including Strong Stackelberg Equilibrium (SSE), (ii) as well as bring new practical algorithms that compute near-optimal equilibria considering only a fraction of strategy space. Our contributions include (1) formal definition and theoretical characterization of machine strategies in EFGs, (2) formal definitions and complexity analysis for solution concepts and their computation when restricted to small classes of machines, (3) new algorithms for computing SSE in general-sum games and Nash Equilibrium in zero-sum games that both directly use the concept of machines. Experimental results on two different domains show that the algorithms compute near-optimal strategies and achieve significantly better scalability compared to previous state-of-the-art algorithms.

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

<a href="/cs/project/GJ19-24384Y" target="_blank" >GJ19-24384Y: Výpočet rovnovážných strategií v dynamických hrách</a><br>

Návaznosti

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

Rok uplatnění

2020

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

EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

ISBN

978-1-4503-7975-5

ISSN

—

e-ISSN

—

Počet stran výsledku

25

Strana od-do

509-533

Název nakladatele

Association for Computing Machinery

Místo vydání

—

Místo konání akce

Virtual On-line

Datum konání akce

13. 7. 2020

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

WRD - Celosvětová akce

Kód UT WoS článku

—