Riley, Luke, Atkinson, Katie 
ORCID: 0000-0002-5683-4106, Dunne, Paul ORCID: 0000-0002-6033-3742 and Payne, Terry ORCID: 0000-0002-0106-8731
(2015)
Distributing Coalition Value Calculations to Coalition Members.
In: 29th AAAI Conference on Artificial Intelligence (AAAI-15), Austin, Texas.
|
Text
RileyPaper894.pdf - Author Accepted Manuscript Download (257kB) | Preview |
Abstract
Within characteristic function games, agents have the option of joining one of many different coalitions, based on the utility value of each candidate coalition. However, determining this utility value can be computationally complex since the number of coalitions increases exponentially with the number of agents available. Various approaches have been proposed that mediate this problem by distributing the computational load so that each agent calculates only a subset of coalition values. However, current approaches are either highly inefficient due to redundant calculations, or make the benevolence assumption (i.e. are not suitable for adversarial environments). We introduce DCG, a novel algorithm that distributes the calculations of coalition utility values across a community of agents, such that: (i) no inter-agent communication is required; (ii) the coalition value calculations are (approximately) equally partitioned into shares, one for each agent; (iii) the utility value is calculated only once for each coalition, thus redundant calculations are eliminated; (iv) there is an equal number of operations for agents with equal sized shares; and (v) an agent is only allocated those coalitions in which it is a potential member. The DCG algorithm is pre- sented and illustrated by means of an example. We formally prove that our approach allocates all of the coalitions to the agents, and that each coalition is assigned once and only once.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Uncontrolled Keywords: | Coalition formation, coalition value calculations, distributed problem solving, coordination without communication, power-set distribution |
| Subjects: | ?? QA75 ?? |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 18 Feb 2015 10:08 |
| Last Modified: | 19 Jan 2023 07:38 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/2007160 |
Altmetric
Altmetric
