Graphical Models in Local, Asymmetric Multi-Agent Markov Decision Processes
In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-04). Pages 956--963. July 2004.Copyright © 2004 ACM.
Abstract
In multi-agent MDPs, it is generally necessary to consider the joint state space of all agents, making the size of the problem and the solution exponential in the number of agents. However, often interactions between the agents are only local, which suggests a more compact problem representation. We consider a subclass of multi-agent MDPs with local interactions where dependencies between agents are asymmetric, meaning that agents can affect others in a unidirectional manner. This asymmetry, which often occurs in domains with authority-driven relationships between agents, allows us to make better use of the locality of agents' interactions. We present and analyze a graphical model of such problems and show that, for some classes of problems, it can be exploited to yield significant (sometimes exponential) savings in problem and solution size, as well as in computational efficiency of solution algorithms.
BibTex
@inproceedings{ dolgov04graphMMDP,
paperID = "AAMAS-04",
month = "July",
author = "Dmitri A. Dolgov and Edmund H. Durfee",
booktitle = "Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-04)",
address = "New York",
title = "Graphical Models in Local, Asymmetric Multi-Agent {Markov} Decision Processes",
pages = "956--963",
year = "2004"
}
Download:
[This is a slightly revised version of the paper that appeared in AAMAS-04.]
[pdf]
[ps.gz]