Dynamic Coalition Formation Based on Multi-sided Negotiation

The coalition formation is an important aspect of multi-agent negotiation and cooperation. Based on the Bilateral Shapley-Value, a multi-sided eigenvalue is presented by using the reference of n-person stochastic cooperative game. It is obvious when multisided eigenvalue have superadditivity, rational agents will combine to one coalition. A dynamic coalition formation algorithm is constructed based on the eigenvalue. Procedures of multi-sided negotiation, agent’s negotiation and coalition condensing are introduced in detail. In the end, the complexity, validity, coalition stability and parameter’s function of the algorithm is given. According to these, the correctness of the algorithm is proven.