Publication - Planning for Weakly-Coupled Partially Observable Stochastic Games

Authors:	Guo, AnYuan; Lesser, Victor
Title:	Planning for Weakly-Coupled Partially Observable Stochastic Games
Abstract:	Partially observable stochastic games (POSGs) provide a general framework for modeling multi-agent decision making problems in which each agent has a limited view of the state. While elegant and expressive, this model has been shown to be intractable in the general case. Many real world problems exhibit additional structure that can be leveraged for computational gain. In this paper, we study a class of problems in which the agents are largely independent but may interact by constraining each other's actions. We show that the problem of finding a Nash equilibrium where all agents have expected utility at least k is NP-hard. Then, we present an exact algorithm that performs iterated elimination of dominated strategies by pruning actions based on easy-to-compute bounds. This algorithm can find solutions to problems an order of magnitude larger than those which can be solved by general purpose algorithms.
Keywords:	Planning
Publication:	Proceedings of the 19th International Joint Conference on Artificial Intelligence, pp. 1715 - 1716
Location:	Edinburgh, Scotland
Date:	July 2005
Sources:	PDF: /Documents/Guo_IJCAI05_abs.pdf
Notes:	(Extended abstract.)
Reference:	Guo, AnYuan; Lesser, Victor. Planning for Weakly-Coupled Partially Observable Stochastic Games. Proceedings of the 19th International Joint Conference on Artificial Intelligence, pp. 1715-1716. July 2005. (Extended abstract.)
`bibtex`:	@inproceedings{Guo-400, author = "AnYuan Guo and Victor Lesser", title = "{Planning for Weakly-Coupled Partially Observable Stochastic Games}", booktitle = "Proceedings of the 19th International Joint Conference on Artificial Intelligence", pages = "1715-1716", month = "July", year = "2005", address = "Edinburgh, Scotland", url = "http://mas.cs.umass.edu/paper/400", }