Research map / Learning theory and algorithms / Submodular and game algorithms
Opponent-Model Search in Games with Incomplete Information
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.
Proposes exact minimax-style algorithms for computing maxmin and robust strategies in two-player zero-sum games with incomplete information (vector games) given various forms of opponent models, plus a recursive level-k opponent-modelling framework.
Problem
Computing optimal and robust strategies for MAX in zero-sum extensive-form games with incomplete information (where MAX does not know MIN's type) when knowledge about opponent models is available.
Approach
Generalises minimax with situational values (vector sets) to handle opponent models as probabilistic, lexicographic, or nondeterministic, uses non-normalised belief states to propagate Bayesian information, and adds a probability of opponent deviation via annotated vectors; recursive level-k models are built on top.
Key results
- Proposes exact algorithms: probabilistic and lexicographic opponent models solved by a single minimax pass with belief states in O(mt|T|) time, while nondeterministic opponent models with pure strategies are NP-complete.
- Mixed-maxmin LP extended with opponent-model separation oracle; on the running example MAX's optimal strategy is (l, R) for p_inf <= 5/8, otherwise uniform.
- Recursive level-k framework reproduces the bridge deal example where MAX at level 2 chose f over the maxmin strategy nf.
Surprising findings
- Pure maxmin is NP-hard to compute for vector games, and nondeterministic opponent models make pure maxmin NP-complete even with perfect information for MAX and two opponent models.
Limitations
- Pure maxmin with nondeterministic opponent models is exponential in the worst case (NP-complete).
- Assumes explicit extensive-form trees and behaviour-strategy opponent models; no compact game representations.
- Evaluated only on small illustrative examples and an abstract bridge deal rather than large-scale experiments.
Experimental setup
Metrics: maxmin value (expected payoff)
Baselines: best-defence model mixed maxmin pure maxmin
Builds on: minimax algorithm Koller and Megiddo linear programming for maxmin Ginsberg pure maxmin algorithm cognitive hierarchy model best-defence model
Closest papers by meaning
- Subgame solving without common knowledge (NeurIPS 2021 · similarity 0.88)
- Safe and Robust Subgame Exploitation in Imperfect Information Games (ICML 2024 · similarity 0.86)
- Opponent Modeling based on Subgoal Inference (NeurIPS 2024 · similarity 0.85)
- State-Constrained Zero-Sum Differential Games with One-Sided Information (ICML 2024 · similarity 0.85)
- Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions (NeurIPS 2024 · similarity 0.85)
- Mastering Board Games by External and Internal Planning with Language Models (ICML 2025 · similarity 0.84)
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.