"Multiagent Graph Coloring:
Pareto Efficiency, Fairness and Individual Rationality"

Speaker: Yaad Blum, The Hebrew University
Date: Wednesday, 2 July 2008
Time: 9am
Place: Ross 201

Abstract:

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.