Coalition Formation Algorithms for Virtual Organisations
Coalition formation in multi-agent systems (MAS) is becoming increasingly important as it increases the ability of agents to execute tasks and maximize their payoffs. This is especially true in virtual enterprises, where dynamic coalitions of small, agile enterprises can provide more services and make more profits than an individual can. Moreover, such coalitions can disband when they are no longer effective. Thus the automation of coalition formation will not only save considerable labour time, but also may be more effective at finding beneficial coalitions than human in complex settings.
Coalition formation has been addressed in game theory for some time. However, game theoric approaches are typically centralized and computationally infeasible. MAS researchers, using game theory concepts, have developed algorithms for coalition formation in MAS environments. However, many of them suffer from a number of important drawbacks, for example:
- They are only applicable for small number of agents.
- They only consider super-additive environments. Super-additive means that for any pair of coalitions, it is always beneficial for them to form one big coalition. Thus, in super-additive environments, all agents are best off by forming the grand coalition, i.e. the coalition contains all the agents. While this assumption simplifies the analysis, it also limits the scope of the application.
Thus, our research will do a thorough literature review of existing coalition formation algorithms, and evaluate them both theoretically and empirically. Based on our findings, we will develop a more efficient algorithm for coalition formation, applicable for virtual enterprises environment.
Type: Normal Research Project
Research Groups: Intelligence, Agents, Multimedia Group, Agents, Interaction and Complexity
Themes: Agent Based Computing, E-Business Technologies
Dates: 1st January 2001 to 1st December 2003
You can edit the record for this project by visiting http://secure.ecs.soton.ac.uk/db/projects/editproj.php?project=47