Convergence, steady state, and global gains of agent-based coalition formation in e-markets

In this paper, we present a rigorous analysis of an agent-based coalition formation mechanism in emarkets proposed by Lerman and Shehory. While the agent-based coalition formation shows good performance through simulations, our analysis provides guidelines for agent designers to simplify the system design. We show that the coalition formations with different initial distributions converge to a unique steady state. The steady state, which represents both the final coalition distribution and the global utility gain, is proven to be determined by buyer agents' local strategies. The global utility gain is shown to increase as the number of buyer agents increases. In a system of uniform-attachment-uniform-detachment rates, the global utility gain is proven to increase as the detachment rate decreases.