TY - JOUR

T1 - A unifying framework for iterative approximate best-response algorithms for distributed constraint optimization problems

AU - Chapman, Archie C.

AU - Rogers, Alex

AU - Jennings, Nicholas R.

AU - Leslie, David S.

PY - 2011/12/1

Y1 - 2011/12/1

N2 - Distributed constraint optimization problems (DCOPs) are important in many areas of computer science and optimization. In a DCOP, each variable is controlled by one of many autonomous agents, who together have the joint goal of maximizing 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 analyzing 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 non-cooperative 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.

AB - Distributed constraint optimization problems (DCOPs) are important in many areas of computer science and optimization. In a DCOP, each variable is controlled by one of many autonomous agents, who together have the joint goal of maximizing 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 analyzing 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 non-cooperative 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.

U2 - 10.1017/S0269888911000178

DO - 10.1017/S0269888911000178

M3 - Journal article

VL - 26

SP - 411

EP - 444

JO - Knowledge Engineering Review

JF - Knowledge Engineering Review

SN - 0269-8889

IS - 04

ER -