%0 Conference Paper
%B CP 2004 Workshop on Distributed Constraint Reasoning (DCR-04)
%D 2004
%T DCOP Games for Multi-Agent Coordination
%A Jonathan P. Pearce
%A Rajiv T. Maheswaran
%A Tambe, Milind
%X 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
%B CP 2004 Workshop on Distributed Constraint Reasoning (DCR-04)
%G eng