טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentShoham Eran
SubjectMulti-Agent Coalition Re-Formation and League Ranking
DepartmentDepartment of Industrial Engineering and Management
Supervisor Dr. Onn Shehory


Abstract

Mechanisms for coalition formation usually take as their input a set of unallocated agents and assign them to coalitions. When coalitions already exist but their competence is not satisfactory it is sometimes possible to draw agents from existing coalitions and to use them to form new, hopefully more competent, coalitions. The competence of the resultant re-formed coalitions is unknown and thus must be evaluated. The naïve process of doing so requires matching each re-formed coalition against all the others. Hence, even for a small number of existing coalitions consisting of a few agents each, the number of matches within the new re-formed league that the naïve process should handle might be restrictively large.

Therefore, other, more efficient mechanisms for both evaluating competence and locating superior coalitions are required. In this work we provide such a mechanism, which is based on an iterative ranking scheme with a reduced complexity. The mechanism iteratively selects a coalition, either a re-formed or an existing one, and uses it as a reference for the ranking. With respect to this reference, the competences of all the other examined coalitions are quantified. The coalitions are then ranked according to these values. We have experimentally tested the ranking scheme in several domains, via thousands of trials: in sets of re-formed coalitions as well as sets of existing coalitions; in coalitions of human agents as well as in simulated coalitions and in sets of different sizes.  The results show that our algorithm is applicable for all of the coalition types examined, and suggest applicability for other domains as well. We also examined a wide range of domains for comparing the ranking scheme to other well-known mechanisms for top coalition search. Almost always, our algorithm yielded better ranking than other mechanisms, placing better coalitions at the top rank.