Abstract
This paper introduces Combinatorial Games with Incomplete Information (CGII), a minimalist mathematical framework designed to bridge the gap between perfect-information games and complex extensive-form games (EFGs). By isolating initial state uncertainty from mid-game hidden actions, we demonstrate that the mere existence of hidden initial knowledge makes these games just as computationally difficult to solve as general EFGs. Our results show that public actions do not simplify game-theoretic solutions when initial knowledge is asymmetric.
Introduction
In game theory, a distinction is often made between perfect information (where all actions and states are visible) and imperfect information (where some elements are hidden). A more subtle category is incomplete information, where players may lack knowledge about the underlying "world" or ruleset they are operating within. For example, a Poker player does not know the opponent's hand, which fundamentally changes the strategic consequences of every public bet.
Standard models like Extensive-Form Games (EFGs) typically conflate hidden actions, mid-game stochastic events (chance nodes), and knowledge gaps. This entanglement makes it difficult to pinpoint exactly which features drive computational hardness. The authors propose the CGII formalism as a "minimalist" model to test if a game remains difficult when mid-game luck and hidden moves are removed, leaving only initial uncertainty about the state of the world.
The CGII Framework
The CGII model is defined by three primary components:
- An Aumann Model: A set of possible "worlds." At the start, "Nature" picks one world, and players receive partial information (signals) about which one was chosen.
- A Public Tree: A game tree where every move made by a player is visible to everyone else. There are no hidden moves or mid-game dice rolls.
- Reward Functions: The payoff at the end of the game depends on both the path taken in the tree and the actual world picked by Nature.
By treating mid-game randomness as something that can be "folded" into the initial state—where Nature picks a world containing the results of all future stochastic events—CGII can represent any EFG while maintaining a cleaner structure of public actions.
Complexity Analysis
To analyze the difficulty of these games, the authors categorized teams based on their "degree of ignorance":
- Complete Information (CI): Players know exactly which world they are in.
- Single-Agent Incomplete Information (SA-II): A team acting as a single entity with a specific knowledge gap.
- Multi-Agent Incomplete Information (MA-II): A team of players who have different pieces of the puzzle and cannot see each other's private info.
Using computational complexity theory, including reductions from SAT and Vertex Cover, the researchers mapped the difficulty of calculating the "maxmin value"—the best possible score a team can guarantee for itself. They found that even with public actions, the complexity remains high. For instance, the problem is NP-hard for SA-II vs. CI scenarios.
The Interrogation Game Gadget
A key technical contribution is the "interrogation game" gadget. This construction demonstrates how coordination can be enforced even when all actions are public. It forces teammates to "prove" they are coordinating based on private information without revealing that information to the opponent, analogous to a cryptographic one-time pad.
This gadget illustrates that the "hardness" of games like Bridge stems almost entirely from the initial uncertainty of the cards, rather than the secrecy of the physical act of playing a card. When a team has different pieces of private information (MA-II), the complexity jumps to $\Sigma^P_2$-complete for pure strategies and $\Delta^P_2$-complete for mixed strategies.
Conclusion and Future Work
The paper establishes that for every level of observability, the CGII model matches the complexity of the more general EFG model. This justifies using CGII as a cleaner framework for studying game AI and strategy.
While the current work focuses on binary actions and zero-sum outcomes, future research will aim to extend these results to more complex action spaces and general-sum games. Additionally, the authors suggest that the next step is building practical AI using this "public action" perspective to solve high-complexity problems in real-world domains.
Summary updated