Distributed Algorithms for DCOP: A Graphical Game-Based Approach


Rajiv T. Maheswaran, Jonathan P. Pearce, and Milind Tambe. 2004. “Distributed Algorithms for DCOP: A Graphical Game-Based Approach .” In 17th International Conference on Parallel and Distributed Computing Systems (PDCS-2004).


This paper addresses the application of distributed constraint optimization problems (DCOPs) to large-scale dynamic environments. We introduce a decomposition of DCOP into a graphical game and investigate the evolution of various stochastic and deterministic algorithms. We also develop techniques that allow for coordinated negotiation while maintaining distributed control of variables. We prove monotonicity properties of certain approaches and detail arguments about equilibrium sets that offer insight into the tradeoffs involved in leveraging efficiency and solution quality. The algorithms and ideas were tested and illustrated on several graph coloring domains.
See also: 2004