Bounding the Support Size in Extensive Form Games with Imperfect Information


  • Martin Schmid Charles University in Prague
  • Matej Moravcik Charles University in Prague
  • Milan Hladik Charles University in Prague



Game theory, Nash equilibrium, Support, Poker


It is a well known fact that in extensive form games with perfect information, there is a Nash equilibrium with support of size one. This doesn't hold for games with imperfect information, where the size of minimal support can be larger. We present a dependency between the level of uncertainty and the minimum support size. For many games, there is a big disproportion between the game uncertainty and the number of actions available. In Bayesian extensive games with perfect information, the only uncertainty is about the type of players. In card games, the uncertainty comes from dealing the deck. In these games, we can significantly reduce the support size. Our result applies to general-sum extensive form games with any finite number of players.




How to Cite

Schmid, M., Moravcik, M., & Hladik, M. (2014). Bounding the Support Size in Extensive Form Games with Imperfect Information. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1).



AAAI Technical Track: Game Theory and Economic Paradigms