Games against nature

DOI10.1016/0022-0000(85)90045-5zbMATH Open0583.68020OpenAlexW2019851160WikidataQ30047574 ScholiaQ30047574MaRDI QIDQ1069296FDOQ1069296

Authors: Christos Papadimitriou 

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

Recommendations

• Probabilistic game automata
• Publication:4720789
• The complexity of stochastic games
• On the NP-completeness of finding an optimal strategy in games with common payoffs
• Games, complexity classes, and approximation algorithms.

zbMATH Keywords

PSPACEdecision-making under uncertaintygames 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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of computing the permanent
• Dynamic programming and stochastic control
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Alternation
• The polynomial-time hierarchy
• Title not available (Why is that?)
• Computational Complexity of Probabilistic Turing Machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of some two-person perfect-information games

Cited In (54)

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

This page was built for publication: Games against nature

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