Complexity and Approximations in Robust Coalition Formation via Max-Min k-Partitioning

Coalition formation is beneficial to multi-agent systems, especially when the value of a coalition depends on the relationship among its members. However, an attack can significantly damage a coalition structure by disabling agents. Therefore, getting prepared in advance for such an attack is particularly important. We study a robust k-coalition formation problem modeled by max-min k-partition of a weighted graph. We show that this problem is Σ P 2-complete, which holds even for k = 2 and arbitrary weights, or k = 3 and non-negative weights. We also propose the Iterated Best Response (IBR) algorithm which provides a run-time absolute bound for the approximation error and can be generalized to the max-min optimization version of any Σ P 2-complete problem. We tested IBR on fairly large instances of both synthetic graphs and real life networks, yielding near optimal results in a reasonable time.