Equivalence of games with probabilistic uncertainty and partial-observation games

DOI10.1007/978-3-642-33386-6_30MaRDI QIDQ4649310zbMATH OpenOpenAlexFDO

Authors Krishnendu Chatterjee, Martin Chmelík, Rupak Majumdar

Publication date 21 November 2012

Published in Automated Technology for Verification and Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.4140

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Stochastic games, stochastic differential games (91A15) Applications of game theory (91A80) Synthesis problems (93B50)

Abstract: We introduce games with probabilistic uncertainty, a natural model for controller synthesis in which the controller observes the state of the system through imprecise sensors that provide correct information about the current state with a fixed probability. That is, in each step, the sensors return an observed state, and given the observed state, there is a probability distribution (due to the estimation error) over the actual current state. The controller must base its decision on the observed state (rather than the actual current state, which it does not know). On the other hand, we assume that the environment can perfectly observe the current state. We show that our model can be reduced in polynomial time to standard partial-observation stochastic games, and vice-versa. As a consequence we establish the precise decidability frontier for the new class of games, and for most of the decidable problems establish optimal complexity results.

Recommendations

• A survey of partial-observation stochastic parity games
• scientific article; zbMATH DE number 5954369
• Partial-observation stochastic reachability and parity games
• The complexity of partial-observation stochastic parity games with finite-memory strategies
• Algorithms for Omega-Regular Games with Imperfect Information

Cited in

(3)

• Joint receipt and certainty equivalents of gambles
• A survey of partial-observation stochastic parity games
• Objection and Counter-Objection Equilibrium In Differential Game Under Uncertainty

This page was built for publication: Equivalence of games with probabilistic uncertainty and partial-observation games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4649310)