---
title: "Near-Optimal Anytime Coalition Structure Generation"
authors:
  - "Talal Rahwan"
  - "Sarvapali D. Ramchurn"
  - "Viet Dung Dang"
  - "Nicholas R. Jennings"
doi: ""
url: "https://ijcai.org/proceedings/2007/381"
pdf: "https://ijcai.org/proceedings/2007/0381.pdf"
venue: "Proceedings of the Twentieth International Joint Conference on Artificial Intelligence"
year: 2007
pages: "2365-2370"
track: ""
keywords:
---

# Near-Optimal Anytime Coalition Structure Generation

Talal Rahwan, Sarvapali D. Ramchurn, Viet Dung Dang, Nicholas R. Jennings

*Proceedings of the Twentieth International Joint Conference on Artificial Intelligence*, pages 2365-2370.

## Abstract

Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best set of agents that should articipate in a given team. To this end, in this paper, we present a novel, anytime algorithm for coalition structure generation that is faster than previous anytime algorithms designed for this purpose. Our algorithm can generate solutions that either have a tight bound from the optimal or are optimal (depending on the objective) and works by partitioning the space in terms of a small set of elements that represent structures which contain coalitions of particular sizes. It then performs an online heuristic search that prunes the space and only considers valid and non-redundant coalition structures. We empirically show that we are able to find solutions that are, in the worst case, 99% efficient in 0.0043% of the time to find the optimal value by the state of the art dynamic programming (DP) algorithm (for 20 agents), using 33% less memory.