Multiagent Graph Coloring: Pareto Efficiency, Fairness and Individual Rationality

Yaad Blum, Jeffrey S. Rosenschein

We consider a multiagent extension of single-agent graph coloring. Multiple agents hold disjoint autonomous subgraphs of a global graph, and every color used by the agents in coloring the graph has associated cost. In this multiagent graph coloring scenario, we seek a minimum legal coloring of the global graph's vertices, such that the coloring is also Pareto efficient, socially fair, and individual rational. We analyze complexity of individual-rational solutions in special graph classes where classical coloring algorithms are known. Multiagent graph coloring has application to a wide variety of multiagent coordination problems, including multiagent scheduling.

Subjects: 7.1 Multi-Agent Systems; 15.2 Constraint Satisfaction

Submitted: Apr 15, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.