A unifying framework for iterative approximate best-response algorithms for distributed constraint optimization problems
OA Location
Author(s)
Chapman, A
Rogers, A
Jennings, NR
Leslie, D
Type
Journal Article
Abstract
Distributed constraint optimisation problems (DCOPs) are important in many areas of computer science and optimisation. In a DCOP, each variable is controlled by one of many autonomous agents, who together have the joint goal of maximising a global objective function. A wide variety of techniques have been explored to solve such problems, and here we focus on one of the main families, namely iterative approximate best?response algorithms used as local search algorithms for DCOPs. We define these algorithms as those in which, at each iteration, agents communicate only the states of the variables under their control to their neighbours on the constraint graph, and that reason about their next state based on the messages received from their neighbours. These algorithms include the distributed stochastic algorithm and stochastic coordination algorithms, the maximum?gain messaging algorithms, the families of fictitious play and adaptive play algorithms, and algorithms that use regret?based heuristics. This family of algorithms is commonly employed in real world systems, as they can be used in domains where communication is difficult or costly, where it is appropriate to trade timeliness off against optimality, or where hardware limitations render complete or more computationally intensive algorithms unusable. However, until now, no overarching framework has existed for analysing this broad family of algorithms, resulting in similar and overlapping work being published independently in several different literatures. The main contribution of this paper, then, is the development of a unified analytical framework for studying such algorithms. This framework is built on our insight that when formulated as noncooperative games, DCOPs form a subset of the class of potential games. This result allows us to prove convergence properties of iterative approximate best?response algorithms developed in the computer science literature using game theoretic methods (which also shows that such algorithms can also be applied to the more general problem of finding Nash equilibria in potential games), and, conversely, also allows us to show that many game?theoretic algorithms can be used to solve DCOPs. By so doing, our framework can assist system designers by making the pros and cons of, and the synergies between, the various iterative approximate best?response DCOP algorithm components clear.
Date Issued
2011-11-25
Date Acceptance
2011-11-25
Citation
Knowledge Engineering Review, 2011, 26 (4), pp.411-444
ISSN
1469-8005
Publisher
Cambridge University Press
Start Page
411
End Page
444
Journal / Book Title
Knowledge Engineering Review
Volume
26
Issue
4
Copyright Statement
© 2011 Cambridge University Press. This paper has been accepted for publication and will appear in a revised form, subsequent to peer-review and/or editorial input by Cambridge University Press.
Identifier
http://eprints.soton.ac.uk/268172/
Subjects
Science & Technology
Technology
Computer Science, Artificial Intelligence
Computer Science
COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE
FICTITIOUS PLAY
STOCHASTIC APPROXIMATIONS
DIFFERENTIAL-INCLUSIONS
SENSOR NETWORKS
POWER-CONTROL
GAMES
COORDINATION
CONVERGENCE
BREAKOUT
Artificial Intelligence & Image Processing
0801 Artificial Intelligence And Image Processing
1702 Cognitive Science
Publication Status
Published