Finite State Machines Play Extensive-Form Games

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Finite State Machines Play Extensive-Form Games

Original language description

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.

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)

Project

<a href="/en/project/GJ19-24384Y" target="_blank" >GJ19-24384Y: Computing Equilibrium Strategies in Dynamic Games</a><br>

Continuities

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

Publication year

2020

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

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

ISBN

978-1-4503-7975-5

ISSN

—

e-ISSN

—

Number of pages

25

Pages from-to

509-533

Publisher name

Association for Computing Machinery

Place of publication

—

Event location

Virtual On-line

Event date

Jul 13, 2020

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—