Lower bounds for multiplayer noncooperative games of incomplete information

DOI10.1016/S0898-1221(00)00333-3zbMath0991.91007OpenAlexW1973302434MaRDI QIDQ5948765

No author found.

Publication date: 12 November 2001

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0898-1221(00)00333-3

zbMATH Keywords

algorithmsgame theoryincomplete informationalternationblindfoldcomplexity theory

Mathematics Subject Classification ID

Noncooperative games (91A10) Hierarchical games (including Stackelberg games) (91A65) Games in extensive form (91A18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (41)

Propositional logics of dependence ⋮ Specification and Verification of Multi-Agent Systems ⋮ Hierarchical information and the synthesis of distributed strategies ⋮ Consensus Game Acceptors ⋮ Preprocessing for DQBF ⋮ Compositional and symbolic synthesis of reactive controllers for multi-agent systems ⋮ Imperfect information in reactive modules games ⋮ Solving dependency quantified Boolean formulas using quantifier localization ⋮ The Computational Complexity of Portal and Other 3D Video Games ⋮ Modal Inclusion Logic: Being Lax is Simpler than Being Strict ⋮ Connectivity games over dynamic networks ⋮ A resolution proof system for dependency stochastic Boolean satisfiability ⋮ Complexity of planning for connected agents in a partially known environment ⋮ Soundness of \(\mathcal{Q}\)-resolution with dependency schemes ⋮ Cooperating in video games? Impossible! Undecidability of team multiplayer games ⋮ Parameterized complexity of propositional inclusion and independence logic ⋮ Henkin quantifiers and Boolean formulae: a certification perspective of DQBF ⋮ Unnamed Item ⋮ Complexity results for modal dependence logic ⋮ Unnamed Item ⋮ Linear Programming Tools for Analyzing Strategic Games of Independence-Friendly Logic and Applications ⋮ Consensus Game Acceptors and Iterated Transductions ⋮ Complexity of fixed-size bit-vector logics ⋮ Complexity of validity for propositional dependence logics ⋮ Partial-order Boolean games: informational independence in a logic-based model of strategic interaction ⋮ Infinite games with finite knowledge gaps ⋮ On the computational consequences of independence in propositional logic ⋮ Building strategies into QBF proofs ⋮ Expressivity and Complexity of Dependence Logic ⋮ Unnamed Item ⋮ Dependency Schemes for DQBF ⋮ Lifting QBF Resolution Calculi to DQBF ⋮ Reinterpreting dependency schemes: soundness meets incompleteness in DQBF ⋮ Model Checking and Validity in Propositional and Modal Inclusion Logics ⋮ The (D)QBF Preprocessor HQSpre – Underlying Theory and Its Implementation1 ⋮ Uniform strategies, rational relations and jumping automata ⋮ Decision algorithms for multiplayer noncooperative games of incomplete information ⋮ Computation of equilibria in noncooperative games ⋮ Davis and Putnam meet Henkin: solving DQBF with resolution ⋮ Certified DQBF solving by definition extraction ⋮ DQBDD: an efficient BDD-based DQBF solver

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of two-player games of incomplete information
• On alternation
• The polynomial-time hierarchy
• On the complexity of some two-person perfect-information games
• Decision algorithms for multiplayer noncooperative games of incomplete information
• N by N Checkers is Exptime Complete
• Alternating Pushdown and Stack Automata
• Alternation bounded auxiliary pushdown automata
• Provably Difficult Combinatorial Games
• GO Is Polynomial-Space Hard
• Alternation
• A Combinatorial Problem Which Is Complete in Polynomial Space
• On the Computational Complexity of Algorithms
• Computational Complexity and the Existence of Complexity Gaps

This page was built for publication: Lower bounds for multiplayer noncooperative games of incomplete information