Publication - Approximately Solving Sequential Games with Incomplete Information

Authors: Mostafa, Hala; Lesser, Victor
Title: Approximately Solving Sequential Games with Incomplete Information
Abstract: Games of incomplete information are notorious for their difficulty which usually makes finding an exact solution intractable. The problem is even harder when the game has multiple stages and sequential decision-making is required. Some efforts have therefore addressed the issue of finding approximate equilibria for various classes of games, but these have mostly been restricted to 1-stage games. We propose an anytime search algorithm for calculating epsilon-Bayes-Nash equilibria in sequential games of incomplete information. Our algorithm first collapses the game tree by making “obvious” decisions and backing up values wherever possible. It then searches the space of strategy profiles by iteratively improving a random starting point until either the desired level of stability is reached or no further improvement is possible, in which case the point is randomly perturbed and the process repeats. We identify a continuum of measures for the stability of a strategy profile that vary in their accuracy and ease of calculation. We use one such measure to obtain results of the performance of our algorithm on randomly generated game trees and compare it to the Quantal Response Equilibria algorithm. We also present results of both algorithms on games derived from random instances of the database view maintenance problem. These experimental results demonstrate our algorithm’s attractive anytime behavior which allows it to find good-enough solutions to large games within reasonable amounts of time.
Keywords: Contingency, Search, Uncertainty
Publication: Proceedings of the AAMAS’08 Workshop on Multi-Agent Sequential Decision Making in Uncertain Multi-Agent Domains, pp. 92 - 106
Editor: Shen, J.; Varakantham, P.; Maheswaran, R.
Location: Estoril, Portugal
Publisher: IFAAMAS
Date: 2008
Sources: PDF: /Documents/mostafa_AAMAS08WS.pdf
Reference: Mostafa, Hala; Lesser, Victor. Approximately Solving Sequential Games with Incomplete Information. Proceedings of the AAMAS’08 Workshop on Multi-Agent Sequential Decision Making in Uncertain Multi-Agent Domains, Shen, J.; Varakantham, P.; Maheswaran, R., ed., IFAAMAS, pp. 92-106. 2008.
bibtex: 
@inproceedings{Hala-454,
  author    = "Hala Mostafa and Victor Lesser",
  title     = "{Approximately Solving Sequential Games with
               Incomplete Information}",
  booktitle = "Proceedings of the AAMAS’08 Workshop on
               Multi-Agent Sequential Decision Making in
               Uncertain Multi-Agent Domains",
  editor    = "J. Shen and P. Varakantham and R. Maheswaran",
  publisher = "IFAAMAS",
  pages     = "92-106",
  year      = "2008",
  address   = "Estoril, Portugal",
  url       = "http://mas.cs.umass.edu/paper/454",
}