Decentralised Coalition Formation Methods for Multi-Agent Systems

Riley, Luke Decentralised Coalition Formation Methods for Multi-Agent Systems. PhD thesis, University of Liverpool.

Text RileyLuk_May2015_2012139.pdf - Unspecified Available under License Creative Commons Attribution. Download (1MB)

Abstract

Coalition formation is a process whereby agents recognise that cooperation with others can occur in a mutually beneficial manner and therefore the agents can choose appropriate temporary groups (named coalitions) to form. The benefit of each coalition can be measured by: the goals it achieves; the tasks it completes; or the utility it gains. Determining the set of coalitions that should form is difficult even in centralised cooperative circumstances due to: (a) the exponential number of different possible coalitions; (b) the ``super exponential'' number of possible sets of coalitions; and (c) the many ways in which the agents of a coalition can agree to distribute its gains between its members (if this gain can be transferred between the agents). The inherent distributed and potentially self-interested nature of multi-agent systems further complicates the coalition formation process. How to design decentralised coalition formation methods for multi-agent systems is a significant challenge and is the topic of this thesis. The desirable characteristics for these methods to have are (among others): (i) a balanced computational load between the agents; (ii) an optimal solution found with distributed knowledge; (iii) bounded communication costs; and (iv) to allow coalitions to form even when the agents disagree on their values. The coalition formation methods presented in this thesis implement one or more of these desirable characteristics. The contribution of this thesis begins with a decentralised dialogue game that utilise argumentation to allow agents to reason over and come to a conclusion on what are the best coalitions to form, when the coalitions are valued qualitatively. Next, the thesis details two decentralised algorithms that allow the agents to complete the coalition formation process in a specific coalition formation model, named characteristic function games. The first algorithm allows the coalition value calculations to be distributed between the agents of the system in an approximately equal manner using no communication, where each agent assigned to calculate the value of a coalition is included in that coalition as a member. The second algorithm allows the agents to find one of the most stable coalition formation solutions, even though each agent has only partial knowledge of the system. The final contribution of this thesis is a new coalition formation model, which allows the agents to find the expected payoff maximising coalitions to form, when each agent may disagree on the quantitative value of each coalition. This new model introduces more risk to agents valuing a coalition higher than the other agents, and so encourages pessimistic valuations.

Item Type:	Thesis (PhD)
Additional Information:	Date: 2015-05-27 (completed)
Subjects:	?? QA75 ??
Depositing User:	Symplectic Admin
Date Deposited:	08 Sep 2015 10:24
Last Modified:	17 Dec 2022 01:30
DOI:	10.17638/02012139
URI:	https://livrepository.liverpool.ac.uk/id/eprint/2012139