An Algorithm for Distributing Coalitional Value Calculations among Cooperating Agents
OA Location
Author(s)
Rahwan, Talal
Jennings, NR
Type
Journal Article
Abstract
The process of forming coalitions of software agents generally requires calculating a value for every possible coalition which indicates how beneficial that coalition would be if it was formed. Now, instead of having a single agent calculate all these values (as is typically the case), it is more efficient to distribute this calculation among the agents, thus using all the computational resources available to the system and avoiding the existence of a single point of failure. Given this, we present a novel algorithm for distributing this calculation among agents in cooperative environments. Specifically, by using our algorithm, each agent is assigned some part of the calculation such that the agents? shares are exhaustive and disjoint. Moreover, the algorithm is decentralized, requires no communication between the agents, has minimal memory requirements, and can reflect variations in the computational speeds of the agents. To evaluate the effectiveness of our algorithm, we compare it with the only other algorithm available in the literature for distributing the coalitional value calculations (due to Shehory and Kraus). This shows that for the case of 25 agents, the distribution process of our algorithm took less than 0.02% of the time, the values were calculated using 0.000006% of the memory, the calculation redundancy was reduced from 383229848 to 0, and the total number of bytes sent between the agents dropped from 1146989648 to 0 (note that for larger numbers of agents, these improvements become exponentially better).
Date Issued
2007
Citation
Artificial Intelligence Journal, 2007, 171, pp.535-567
Start Page
535
End Page
567
Journal / Book Title
Artificial Intelligence Journal
Volume
171
Identifier
http://eprints.soton.ac.uk/263720/
Subjects
Science & Technology
Technology
Computer Science, Artificial Intelligence
Computer Science
COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE
coalition formation
multi-agent systems
Artificial Intelligence & Image Processing
0801 Artificial Intelligence And Image Processing
1702 Cognitive Science
Article Number
8-9