Games against nature

DOI10.1016/0022-0000(85)90045-5zbMath0583.68020OpenAlexW2019851160WikidataQ30047574 ScholiaQ30047574MaRDI QIDQ1069296

Publication date: 1985

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(85)90045-5

zbMATH Keywords

decision-making under uncertainty PSPACE games played against a disinterested opponent

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80) Decision theory for games (91A35)

Related Items

Quantum alternation ⋮ The polynomial hierarchy and a simple model for competitive analysis ⋮ A short certificate of the number of universal optimal strategies for stopping simple stochastic games ⋮ On the complexity of partially observed Markov decision processes ⋮ Solving H-horizon, stationary Markov decision problems in time proportional to log (H) ⋮ TETRIS IS HARD, EVEN TO APPROXIMATE ⋮ Minimum disclosure proofs of knowledge ⋮ Unnamed Item ⋮ Interactive foundations of computing ⋮ Exact stochastic constraint optimisation with applications in network analysis ⋮ Approximate counting in SMT and value estimation for probabilistic programs ⋮ A resolution proof system for dependency stochastic Boolean satisfiability ⋮ On counting propositional logic and Wagner's hierarchy ⋮ Sound and efficient closed-world reasoning for planning ⋮ Confidence-based reasoning in stochastic constraint programming ⋮ Quantum multi-prover interactive proof systems with limited prior entanglement. ⋮ The stochastic arrival problem ⋮ On the complexity of computational problems associated with simple stochastic games ⋮ Solving multistage quantified linear optimization problems with the alpha-beta nested Benders decomposition ⋮ Classifying the computational complexity of problems ⋮ Moving in a network under random failures: a complexity analysis ⋮ The cost of adaptivity in security games on graphs ⋮ On the Relationship between Hybrid Probabilistic Logic Programs and Stochastic Satisfiability ⋮ Stochastic Satisfiability Modulo Theories for Non-linear Arithmetic ⋮ Generalized Quantum Arthur--Merlin Games ⋮ Generalized Craig Interpolation for Stochastic Boolean Satisfiability Problems ⋮ The complexity of stochastic games ⋮ De Groot duality and models of choice: angels, demons and nature ⋮ Generalizations of Opt P to the polynomial hierarchy ⋮ Randomization for robot tasks: using dynamic programming in the space of knowledge states ⋮ Constraint-based analysis of concurrent probabilistic hybrid systems: an application to networked automation systems ⋮ Optimal node visitation in acyclic stochastic digraphs with multi-threaded traversals and internal visitation requirements ⋮ Computational complexity of stochastic programming problems ⋮ Engineering constraint solvers for automatic analysis of probabilistic hybrid automata ⋮ Challenges in Constraint-Based Analysis of Hybrid Systems ⋮ On sabotage games ⋮ Dot operators ⋮ APPSSAT: Approximate probabilistic planning using stochastic satisfiability ⋮ An application of quantum finite automata to interactive proof systems ⋮ From State-of-the-Art Static Fleet Assignment to Flexible Stochastic Planning of the Future ⋮ Scheduling Two-Point Stochastic Jobs to Minimize the Makespan on Two Parallel Machines ⋮ Interactive and probabilistic proof-checking ⋮ Scheduling Stochastic Jobs with a Two-Point Distribution on Two Parallel Machines ⋮ Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete. ⋮ Shortest paths without a map ⋮ Decision algorithms for multiplayer noncooperative games of incomplete information ⋮ Contingent planning under uncertainty via stochastic satisfiability ⋮ Computation of equilibria in noncooperative games

Cites Work