Skip to main content
placeholder image

A best-first anytime algorithm for computing optimal coalition structures

Conference Paper


Download full-text (Open Access)

Abstract


  • This work presents a best-first anytime algorithm for computing optimal coalition structures. The approach is novel in that it generates coalition structures based on coalition values, while existing algorithms base their generation on the structure (members and configurations) of coalitions. With our algorithm, coalition structures are generated by repeatedly choosing the best coalition, as determined using a novel metric called agent's contribution to coalition structure that we define. We have compared the performance of our algorithm against that of Rahwan et al [5] using 20 data distributions. Our results show that our algorithm almost always converges on an optimal coalition structure faster (although it terminates later in some cases). Empirically, our algorithm almost always yields better than or as good as Rahwan et al's results at any point in time. Copyright © 2008, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

UOW Authors


  •   Sombattheera, Chattrakul (external author)
  •   Ghose, Aditya

Publication Date


  • 2008

Citation


  • Sombattheera, C. & Ghose, A. (2008). A best-first anytime algorithm for computing optimal coalition structures. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS (pp. 1393-1396).

Scopus Eid


  • 2-s2.0-84899978286

Ro Full-text Url


  • http://ro.uow.edu.au/cgi/viewcontent.cgi?article=4606&context=eispapers

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/3587

Start Page


  • 1393

End Page


  • 1396

Abstract


  • This work presents a best-first anytime algorithm for computing optimal coalition structures. The approach is novel in that it generates coalition structures based on coalition values, while existing algorithms base their generation on the structure (members and configurations) of coalitions. With our algorithm, coalition structures are generated by repeatedly choosing the best coalition, as determined using a novel metric called agent's contribution to coalition structure that we define. We have compared the performance of our algorithm against that of Rahwan et al [5] using 20 data distributions. Our results show that our algorithm almost always converges on an optimal coalition structure faster (although it terminates later in some cases). Empirically, our algorithm almost always yields better than or as good as Rahwan et al's results at any point in time. Copyright © 2008, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

UOW Authors


  •   Sombattheera, Chattrakul (external author)
  •   Ghose, Aditya

Publication Date


  • 2008

Citation


  • Sombattheera, C. & Ghose, A. (2008). A best-first anytime algorithm for computing optimal coalition structures. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS (pp. 1393-1396).

Scopus Eid


  • 2-s2.0-84899978286

Ro Full-text Url


  • http://ro.uow.edu.au/cgi/viewcontent.cgi?article=4606&context=eispapers

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/3587

Start Page


  • 1393

End Page


  • 1396