About: Determinacy and Optimal Strategies in Infinite-state Stochastic Reachability Games

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Determinacy and Optimal Strategies in Infinite-state Stochastic Reachability Games Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://www.sciencedirect.com/science/article/pii/S030439751200967X
Description	We consider perfect-information reachability stochastic games for 2 players on countable graphs. Such a game is strongly determined if, whenever we fix an inequality ~E{>,>=} and a threshold p, either Player Max has a strategy which forces the value of the game to satisfy ~p against any strategy of Player Min, or Min has a strategy which forces the opposite against any strategy of Max. One of our results shows that whenever one of the players has an optimal strategy in every state of a game, then this game is strongly determined. This significantly generalises, e.g., recent results on finitely-branching reachability games. For strong determinacy, our methods are substantially different, based on which player has the optimal strategy, because the roles of the players are not symmetric. We also do not restrict the branching of the games, and where we provide an extension of results for finitely-branching games, we had to overcome significant complications and employ new methods as well. We consider perfect-information reachability stochastic games for 2 players on countable graphs. Such a game is strongly determined if, whenever we fix an inequality ~E{>,>=} and a threshold p, either Player Max has a strategy which forces the value of the game to satisfy ~p against any strategy of Player Min, or Min has a strategy which forces the opposite against any strategy of Max. One of our results shows that whenever one of the players has an optimal strategy in every state of a game, then this game is strongly determined. This significantly generalises, e.g., recent results on finitely-branching reachability games. For strong determinacy, our methods are substantially different, based on which player has the optimal strategy, because the roles of the players are not symmetric. We also do not restrict the branching of the games, and where we provide an extension of results for finitely-branching games, we had to overcome significant complications and employ new methods as well. (en)
Title	Determinacy and Optimal Strategies in Infinite-state Stochastic Reachability Games Determinacy and Optimal Strategies in Infinite-state Stochastic Reachability Games (en)
skos:prefLabel	Determinacy and Optimal Strategies in Infinite-state Stochastic Reachability Games Determinacy and Optimal Strategies in Infinite-state Stochastic Reachability Games (en)
skos:notation	RIV/00216224:14330/13:00080195!RIV15-MSM-14330___
http://linked.open...avai/riv/aktivita	I
http://linked.open...avai/riv/aktivity	I
http://linked.open...iv/cisloPeriodika	1
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Brožek, Václav
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	68807
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/13:00080195
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Stochastic games; Reachability; Determinacy; Optimal strategies (en)
http://linked.open.../riv/klicoveSlovo	Determinacy Optimal strategies Stochastic games Reachability
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[68F8041F307C]
http://linked.open...i/riv/nazevZdroje	Theoretical Computer Science
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	1 (xsd:int)
http://linked.open...UplatneniVysledku	2013
http://linked.open...v/svazekPeriodika	493
http://linked.open...iv/tvurceVysledku	Brožek, Václav
http://linked.open...ain/vavai/riv/wos	000321410000007
issn	0304-3975
number of pages	18 (xsd:int)
http://bibframe.org/vocab/doi	10.1016/j.tcs.2012.10.038
http://localhost/t...ganizacniJednotka	14330

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software