D 2009

Continuous-Time Stochastic Games with Time-Bounded Reachability

BRÁZDIL, Tomáš, Vojtěch FOREJT, Jan KRČÁL, Jan KŘETÍNSKÝ, Antonín KUČERA et. al.

Basic information

Original name

Continuous-Time Stochastic Games with Time-Bounded Reachability

Authors

BRÁZDIL, Tomáš (203 Czech Republic), Vojtěch FOREJT (203 Czech Republic, belonging to the institution), Jan KRČÁL (203 Czech Republic, belonging to the institution), Jan KŘETÍNSKÝ (203 Czech Republic, belonging to the institution) and Antonín KUČERA (203 Czech Republic, guarantor)

Edition

Dagstuhl, Germany, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), p. 61-72, 12 pp. 2009

Publisher

Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

RIV identification code

RIV/00216224:14330/09:00038704

Organization unit

Faculty of Informatics

ISBN

978-3-939897-13-2

ISSN

UT WoS

000315361200003

Keywords in English

continuous time games; reachability

Tags

Tags

International impact, Reviewed

Abstract

ORIG CZ

V originále

We study continuous-time stochastic games with time-bounded reachability objectives. We show that each vertex in such a game has a value (i.e., an equilibrium probability), and we classify the conditions under which optimal strategies exist. Finally, we show how to compute optimal strategies in finite uniform games, and how to compute e-optimal strategies in finitely-branching games with bounded rates (for finite games, we provide detailed complexity estimations).

In Czech

V článku se studují stochastické hry se spojitým časem. Je dokázáno, že pro časově omezenou dosažitelnost existuje rovnovážná hodnota hry a jsou klasifikovány podmínky, za kterých existují optimální strategie.

Links

MSM0021622419, plan (intention)
Name: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
1M0545, research and development project
Name: Institut Teoretické Informatiky
Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science