Publication - Exploiting Structure To Efficiently Solve Loosely Coupled Stochastic Games

Authors: Mostafa, Hala; Lesser, Victor
Title: Exploiting Structure To Efficiently Solve Loosely Coupled Stochastic Games
Abstract: This paper is concerned with sequential decision making by self-interested agents when their decision processes are largely independent. This situation can be formulated as a stochastic game which would traditionally be represented in extensive form (a single game tree), a representation that fails to exploit the loose coupling in the game. We propose a new representation for 2-agent loosely coupled stochastic games that allows exploiting the sparsity and structure of agent interactions while still being able to capture a general stochastic game. We provide analytical and experimental results to show the representational and computational savings we obtain compared to extensive form in settings with different degrees of coupling. Our second contribution is a compact formulation of our problem as a Multi-Agent Influence Diagram, a first step towards the goal of solving problems with more than two agents. Finally, we investigate the challenges that need to be resolved to meet this goal.
Keywords: Communication, Coordination, Distributed MDP, Multi-Agent Systems, Uncertainty
Publication: AAMAS 2010 Workshop on Multi-agent Sequential Decision-Making in Uncertain Domains, pp. 46 - 53
Location: Toronto, Canada
Date: 2010
Sources: PDF: /Documents/main.pdf
Reference: Mostafa, Hala; Lesser, Victor. Exploiting Structure To Efficiently Solve Loosely Coupled Stochastic Games. AAMAS 2010 Workshop on Multi-agent Sequential Decision-Making in Uncertain Domains, pp. 46-53. 2010.
bibtex: 
@article{Mostafa-492,
  author    = "Hala Mostafa and Victor Lesser",
  title     = "{Exploiting Structure To Efficiently Solve Loosely
               Coupled Stochastic Games}",
  journal   = "AAMAS 2010 Workshop on Multi-agent Sequential
               Decision-Making in Uncertain Domains",
  pages     = "46-53",
  year      = "2010",
  address   = "Toronto, Canada",
  url       = "http://mas.cs.umass.edu/paper/492",
}