A column generation approach to the coalition formation problem in multi-agent systems
Computers and Operations Research, cilt.31, sa.10, ss.1635-1653, 2004 (Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 31 Sayı: 10
- Basım Tarihi: 2004
- Doi Numarası: 10.1016/s0305-0548(03)00112-6
- Dergi Adı: Computers and Operations Research
- Derginin Tarandığı İndeksler: Scopus
- Sayfa Sayıları: ss.1635-1653
- Anahtar Kelimeler: Coalition formation, Column generation, Parallel algorithm, Set partitioning
- Boğaziçi Üniversitesi Adresli: Evet
Özet
The goal of this paper is to provide a computational study of the coalition formation problem in multi-agent systems. The coalition formation problem, as formulated here, is based on social welfare maximizing criteria, which aims to increase the total value of coalition structures in a multi-agent system. Value of each coalition depends only on the participating members. Pairwise relationships of coalition members determine the value of a coalition. In this study, the problem is formulated as a set partitioning problem and a column generation approach is proposed to solve it. Assuming that the coalition forming agents have computational capabilities, the algorithm is also extended to a parallel algorithm where all agents share the computational burden of coming up with a coalition. The proposed algorithms are implemented and tested in three types of environments, where expected pairwise relationship values are positive, zero or negative. Based on the test results, we highlight the coalition environments where parallel column generation technique is viable. © 2003 Elsevier Ltd. All rights reserved.