Multiagent Graph Coloring: Pareto Efficiency, Fairness and Individual Rationality
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.
Cite
Text
Blum and Rosenschein. "Multiagent Graph Coloring: Pareto Efficiency, Fairness and Individual Rationality." AAAI Conference on Artificial Intelligence, 2008.Markdown
[Blum and Rosenschein. "Multiagent Graph Coloring: Pareto Efficiency, Fairness and Individual Rationality." AAAI Conference on Artificial Intelligence, 2008.](https://mlanthology.org/aaai/2008/blum2008aaai-multiagent/)BibTeX
@inproceedings{blum2008aaai-multiagent,
title = {{Multiagent Graph Coloring: Pareto Efficiency, Fairness and Individual Rationality}},
author = {Blum, Yaad and Rosenschein, Jeffrey S.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2008},
pages = {24-29},
url = {https://mlanthology.org/aaai/2008/blum2008aaai-multiagent/}
}