DCOP Games for Multi-Agent Coordination


Jonathan P. Pearce, Rajiv T. Maheswaran, and Milind Tambe. 2004. “DCOP Games for Multi-Agent Coordination .” In CP 2004 Workshop on Distributed Constraint Reasoning (DCR-04).


Many challenges in multi-agent coordination can be modeled as distributed constraint optimization problems (DCOPs) but complete algorithms do not scale well nor respond effectively to dynamic or anytime environments. We introduce a transformation of DCOPs into graphical games that allows us to devise and analyze algorithms based on local utility and prove the monotonicity property of a class of such algorithms. The game-theoretic framework also enables us to characterize new equilibrium sets corresponding to a given degree of agent coordination. A key result in this paper is the discovery of a novel mapping between finite games and coding theory from which we can determine a priori bounds on the number of equilibria in these sets, which is useful in choosing the appropriate level of coordination given the communication cost of an algorithm
See also: 2004