A column generation approach to the coalition formation problem in multi-agent systems

A column generation approach to the coalition formation problem in multi-agent systems

0.00 Avg rating0 Votes
Article ID: iaor2005736
Country: United Kingdom
Volume: 31
Issue: 10
Start Page Number: 1635
End Page Number: 1653
Publication Date: Sep 2004
Journal: Computers and Operations Research
Authors: ,
Keywords: Set partitioning, column generation
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.