Doctor of Philosophy
School of Computer Science and Software Engineering - Faculty of Informatics
Sombattheera, Chattrakul, Advances in practical optimal coalition structure algorithms, Doctor of Philosophy thesis, School of Computer Science and Software Engineering - Faculty of Informatics, University of Wollongong, 2010. http://ro.uow.edu.au/theses/3141
This thesis presents a number of algorithms for forming coalitions among cooperative agents in pragmatic domains where traditional cooperative game theory solution concepts do not apply due to bounded rationality of agents. While previous work in coalition formation in multi-agent systems research operated on relatively small number of agents, e.g. less than 30 agents, this work explores coalition formation among 100 agents, this is due to limited computational resources not the performance of the our algorithms. We explore a bestfirst search centralized algorithm for optimal coalition structures which is based on a novel idea of deciding what is the best coalition to put into coalition structure being generated. Empirical results show that the solution reaches optimality quickly and terminates quickly in pragmatic domains. We further explore on optimal coalition structures with distributed algorithms in linear and non-linear domains. For the linear domains, we explore linear production and integer programming. For the non-linear domains we explore logistic providers. Based on existing algorithms, we explore a novel environment of forming coalitions in supply networks involving buyers, sellers and logistics providers agents. In this setting, buyers form coalitions to increase their negotiation power while sellers and logistics providers form coalitions to aggregate their supply power and optimize their resources usage.
02Whole.pdf (1208 kB)