Martin Schmid, Matej Moravčík, and Milan Hladík. Bounding the support size in extensive form games with imperfect information. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, pp. 784–790, AAAI Press, Palo Alto, California, 2014.
[PDF] [gzipped postscript] [postscript] [HTML]
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.
@inProceedings{SchmMor2014,
author = "Martin Schmid and Matej Morav{\v{c}}\'{\i}k and Milan Hlad\'{\i}k",
title = "Bounding the support size in extensive form games with imperfect information",
booktitle = "Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence",
publisher = "AAAI Press",
address = "Palo Alto, California",
pages = "784-790",
year = "2014",
doi = "10.1609/aaai.v28i1.8813",
issn = "2159-5399",
isbn = "978-1-57735-661-5",
url = "https://ojs.aaai.org/index.php/AAAI/article/view/8813",
bib2html_dl_pdf = "https://ojs.aaai.org/index.php/AAAI/article/view/8813/8672",
bib2html_dl_html = "http://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8416/8501",
abstract = "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.",
keywords = "Extensive form games, Game theory, Poker, Linear programming",
}
Generated by bib2html.pl (written by Patrick Riley ) on Mon Apr 15, 2024 08:26:42