Stability Coalition Formation with Cost Sharing in

Multi-Agent Systems Based on Volume Discount

Walaa El-Ashmawi1, Hu Jun1, 2 and Li Renfa1

1College of Information Science and Engineering, Hunan University, China

2State Key Laboratory for Novel Software Technology, Nanjing University, China

 Abstract: In Multi-Agent Systems(MAS), cooperation among agents to form coalitions based on volume discounts is a key topic. Such cooperation enables agents to achieve goals that they may not have been able to achieve independently at lower prices without ordering more than their real demand. In this paper, we propose a Stability Coalition Formation (SCF) and payoff distribution in terms of the core. Agents can enjoy a price discount for each of their requested action to achieve a goal through the concept of Social Agent Networ (SAN)k, where different opportunities can be found. Each opportunity is associated with coalition value and search cost, given a search cost, the goal of the agent is to find the best set of opportunities which fulfills the coalition’s demands, along with a cost sharing rule satisfying certain stability properties. The experimental results illustrated that, the performance of proposed semi-optimal solution to SCF has proven its stability with average payoff 99.98% closest to the optimal payoff and higher than the average coalition value obtained by 9% when considered a search cost as a parameter affected on the search for optimal coalitions. Also, it has proven its efficiency in average processing time that saved and reduced by 15%~44% according to a different number of agents.

 Keywords: MAS, coalition formation, volume discount, search cost, stability.