Research map / Multi-agent systems and games / Human-AI and goal-conditioned
A Logical Analysis of Hanabi
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formalizes the card game Hanabi in an extended epistemic logic of observation (EL-O) with common knowledge for arbitrary groups, adds a special reasoning action, and gives a finite semantics (H-EL-O) with NP-complete satisfiability.
Problem
Modeling Hanabi's epistemic reasoning is intractable in standard multi-agent dynamic epistemic logic (DEL), and EL-O lacks common knowledge for arbitrary agent groups and finite semantics for it.
Approach
Generalizes EL-O common knowledge to arbitrary agent groups via observability operators, introduces a special reasoning action that delegates deductions agents cannot express in EL-O, and shows that modal depth 2 suffices so Hanabi can be simulated under a finite NP-complete semantics.
Key results
- Defines H-EL-O, a finite semantics over subsets of atoms of modal depth at most 2, and proves its satisfiability problem is NP-complete (Proposition 11).
- Shows that Hanabi states can be encoded using only atoms of modal depth at most 2 (Proposition 4), giving formal grounds for the depth-2 heuristic in Hanabi literature.
- Proves that the action semantics tau^H correctly simulates the infinite-semantics evolution of Hanabi knowledge (Proposition 10).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use finite H-EL-O semantics for the Hanabi formalization | EL-O formalization of Hanabi · Hanabi knowledge evolution | satisfiability complexity: NP-complete | Helped |
| Restrict the representation to modal depth 2 | Hanabi formalization in EL-O · Hanabi knowledge evolution | maximum modal depth: 2 | Helped |
Surprising findings
- Standard multi-agent DEL with common knowledge is 2EXPTIME-complete, making direct Hanabi modeling impractical.
Limitations
- Does not address how agents choose actions or reason about action outcomes; planning left for future work.
- Last round of the game (empty stack) is not modeled.
- Formal correspondence with standard S5 and DEL is stated as future work.
Experimental setup
Baselines: standard multi-agent DEL heuristic and reinforcement learning Hanabi systems
Builds on: EL-O (Perrotin 2021) dynamic epistemic logic STRIPS-like actions
Closest papers by meaning
- Sparks of Cooperative Reasoning: LLMs as Strategic Hanabi Agents (ICML 2026 · similarity 0.88)
- Towards Epistemic-Doxastic Planning with Observation and Revision (AAAI 2024 · similarity 0.86)
- Numina-Lean-Agent: An Open and General Agentic Reasoning System for Formal Mathematics (ICML 2026 · similarity 0.85)
- On Alternating-Time Temporal Logic, Hyperproperties, and Strategy Sharing (AAAI 2024 · similarity 0.84)
- GTBench: Uncovering the Strategic Reasoning Capabilities of LLMs via Game-Theoretic Evaluations (NeurIPS 2024 · similarity 0.83)
- A Minimal Agent for Automated Theorem Proving (ICML 2026 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.