C-Link: A Hierarchical Clustering Approach to Large-scale Near-optimal Coalition Formation

Farinelli, Alessandro; Bicego, Manuele; Ramchurn, Sarvapali D.; Zucchelli, Mauro

C-Link: A Hierarchical Clustering Approach to Large-scale Near-optimal Coalition Formation

Alessandro Farinelli, Manuele Bicego, Sarvapali D. Ramchurn, Mauro Zucchelli

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 106-111.

Abstract

Coalition formation is a fundamental approach to multi-agent coordination. In this paper we address the specific problem of coalition structure generation, and focus on providing good-enough solutions using a novel heuristic approach that is based on data clustering methods. In particular, we propose a hierarchical agglomerative clustering approach (C-Link), which uses a similarity criterion between coalitions based on the gain that the system achieves if two coalitions merge. We empirically evaluate C-Link on a synthetic benchmark data-set as well as in collective energy purchasing settings. Our results show that the C-link approach performs very well against an optimal benchmark based on Mixed-Integer Programming, achieving solutions which are in the worst case about 80% of the optimal (in the synthetic data-set), and 98% of the optimal (in the energy data-set). Thus we show that C-Link can return solutions for problems involving thousands of agents within minutes.

Alessandro Farinelli, Manuele Bicego, Sarvapali D. Ramchurn, and Mauro Zucchelli. 2013. C-Link: A Hierarchical Clustering Approach to Large-scale Near-optimal Coalition Formation. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 106–111. https://ijcai.org/proceedings/2013/27

@inproceedings{ijcai2013p27,
  title     = {C-Link: A Hierarchical Clustering Approach to Large-scale Near-optimal Coalition Formation},
  author    = {Farinelli, Alessandro and Bicego, Manuele and Ramchurn, Sarvapali D. and Zucchelli, Mauro},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {106--111},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/27},
}

TY  - CPAPER
TI  - C-Link: A Hierarchical Clustering Approach to Large-scale Near-optimal Coalition Formation
AU  - Farinelli, Alessandro
AU  - Bicego, Manuele
AU  - Ramchurn, Sarvapali D.
AU  - Zucchelli, Mauro
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 106
EP  - 111
UR  - https://ijcai.org/proceedings/2013/27
ER  -