Algorithms for Finding Approximate Formations in Games
Abstract
Many computational problems in game theory, such as finding Nash equilibria, are algorithmically hard to solve. This limitation forces analysts to limit attention to restricted subsets of the entire strategy space. We develop algorithms to identify rationally closed subsets of the strategy space under given size constraints. First, we modify an existing family of algorithms for rational closure in two-player games to compute a related rational closure concept, called formations, for n-player games. We then extend these algorithms to apply in cases where the utility function is partially specified, or there is a bound on the size of the restricted profile space. Finally, we evaluate the performance of these algorithms on a class of random games.
Cite
Text
Jordan and Wellman. "Algorithms for Finding Approximate Formations in Games." AAAI Conference on Artificial Intelligence, 2010. doi:10.1609/AAAI.V24I1.7635Markdown
[Jordan and Wellman. "Algorithms for Finding Approximate Formations in Games." AAAI Conference on Artificial Intelligence, 2010.](https://mlanthology.org/aaai/2010/jordan2010aaai-algorithms/) doi:10.1609/AAAI.V24I1.7635BibTeX
@inproceedings{jordan2010aaai-algorithms,
title = {{Algorithms for Finding Approximate Formations in Games}},
author = {Jordan, Patrick R. and Wellman, Michael P.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2010},
pages = {798-804},
doi = {10.1609/AAAI.V24I1.7635},
url = {https://mlanthology.org/aaai/2010/jordan2010aaai-algorithms/}
}