A Column generation approach to coalition formation in multi-agent systems

Abstract

ÖZET ÇOK AJANLI SİSTEMLERDE KOALİSYON KURMA PROBLEMİNİN SÜTUN ÜRETME YÖNTEMİ İLE ÇÖZÜMÜ Bu çalışmanın amacı çok ajanlı sistemlerdeki koalisyon kurma problemini analiz edip çözüm üretmektir. Seçilen koalisyon kurma probleminin hedefi çok ajanlı sistem dahilindeki koalisyon yapılarının toplam değerini arttırmaktır. Toplumsal refahın en- iyilenmesi amaçlanan problemde her bir koalisyonun değeri sadece katılımcı elemanlara dayanmaktadır. Koalisyon üyelerinin ikili ilişkileri koalisyon değerini belirlemektedir. Bu çalışmada sütun üretme tekniğine dayalı bir algoritma yazılmış, daha sonra algoritmanın paralel makinelerde çalışan versiyonu geliştirilmiştir. Seri ve paralel algo ritmalar ikili ilişki değerlerinin ortalamasının pozitif, sıfır veya negatif olduğu üç farklı ortamda işletilmiş ve denenmiştir. Son olarak, paralel sütun üretme tekniğinin etkin olduğu koalisyon ortamları deney sonuçlan dikkate alınarak bulunmuştur.

IV ABSTRACT A COLUMN GENERATION APPROACH TO COALITION FORMATION IN MULTI- AGENT SYSTEMS The goal of this study is to analyze and solve coalition formation problem in multi-agents systems. The coalition formation problem is based on social welfare max imizing criteria, which aims to increase total value of coalition structures in a multi- agent system. The value of each coalition depends only on the participating members. Binary relationships of coalition members define the value of a coalition. In this study an algorithm based on column generation technique is proposed and it is extended to a parallel algorithm. The proposed algorithms are implemented and tested in three types of environments, where expected binary relationship values are positive, zero or negative. Based on the test results, the coalition environments where parallel column generation technique is feasible, are identified.