Multiagent Graph Coloring: Pareto Efficiency, Fairness and Individual Rationality

Yaad Blum, Jeffrey S. RosenscheinAAAI 2008

Multiagent Graph Coloring: Pareto Efficiency, Fairness and Individual Rationality

The classic graph coloring problem—assigning colors to vertices such that no two adjacent nodes share the same color—is a cornerstone of computer science. However, in Multiagent Systems (MAS), the problem evolves. When different agents "own" distinct parts of a global graph and face individual costs or preferences for colors, the goal shifts from simple feasibility to economic efficiency. This paper explores the intersection of graph theory and social choice to define what makes a multiagent coloring "good."

The Economic Framework

In a multiagent setting, a globally valid coloring must satisfy three key economic criteria to be considered acceptable by self-interested participants:

  1. Individual Rationality (IR): No agent should be forced to use more colors than the chromatic number ($\chi$) of their own local subgraph. Essentially, participation in the global system shouldn't leave an agent worse off than if they solved their local problem in isolation.
  2. Pareto Efficiency: A coloring is Pareto efficient if no other valid coloring exists that improves the utility of one agent without diminishing the utility of another.
  3. Social Fairness: The "coordination cost"—the extra burden or color usage required to satisfy edges between different agents' subgraphs—should be distributed equitably.
Figure 1: An example of a partitioned graph where agents (H, T, and E) own specific subgraphs, illustrating the constraints imposed by cross-agent edges.

Structural Analysis: Cycles and Split Graphs

The authors investigate how graph topology influences the existence of economically viable solutions.

Cycles and Floating Agents

In cycle graphs ($C_n$), the primary obstacle to individual rationality is the presence of "floating agents"—those whose nodes are not connected to each other within the cycle but are separated by nodes belonging to other agents. If these agents are "blocked" by a third party, they may be unable to share colors efficiently, leading to an "irrational" partition where the global constraints force an agent to use more colors than their local chromatic number.

Figure 3: A cycle graph partition demonstrating how local constraints and agent placements propagate globally, potentially leading to irrationality.

Split Graphs and Cooperative Vertices

For split graphs—which consist of a central clique and an independent set—the authors identify a "cooperative vertex" condition. If every agent possesses at least one node in the central clique that is not connected to their own "boundary" nodes in the independent set, an individually rational solution is guaranteed to exist.

Computational Complexity

The transition from two agents to many agents introduces a significant "complexity jump." While finding an IR coloring for two agents on an odd cycle is computationally easy, the problem becomes NP-Complete as the number of agents grows proportionally to the number of vertices. Conversely, for split graphs meeting the cooperative vertex condition, an IR coloring can be found efficiently in $O(|V| + |E|)$ time.

Conclusion and Future Directions

This research provides a rigorous foundation for multiagent graph coloring, highlighting that some partitions are inherently "irrational." Future work remains to address the assumption of agent benevolence through mechanism design, preventing agents from misreporting their preferences. Additionally, moving from a centralized decision-maker to decentralized, distributed algorithms would better reflect the nature of many real-world multiagent systems.

Summary updated

BibTeX
@inproceedings{blum2008multiagent,
  author = {Yaad Blum and Jeffrey S. Rosenschein},
  title = {{Multiagent Graph Coloring: Pareto Efficiency, Fairness and Individual Rationality}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}

Loading related content...

Figure