Combinatorial Games with Incomplete Information

Combinatorial Games with Incomplete Information

Junkang Li, Bruno Zanuttini, Véronique Ventos

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 2895-2903. https://doi.org/10.24963/ijcai.2024/321

Games with incomplete information model multi-agent interaction in which players do not have common knowledge of the game they play. We propose a minimal generalisation of combinatorial games to incorporate incomplete information, called combinatorial game with incomplete information (CGII). The most important feature of CGIIs is that all actions are public, which allows better visualisation of each player's knowledge and incomplete information. To further motivate the study of this new formalism, we show that computing optimal strategies for CGIIs has the same computational complexity as for general extensive-form games.
Keywords:
Game Theory and Economic Paradigms: GTEP: Noncooperative games
Uncertainty in AI: UAI: Sequential decision making