Payoff Distribution of Agents in Optimal Coalition Structure under Non-Superadditive Environment by Shapley Value

Abstract

An important feature in multiagent systems is forming coalitions among agents to execute tasks. At the system level, the most important thing for forming coalition is the system’s benefit. At agent level, the most important factor for forming coalitions is the division of joint benefits accruing from agents’ cooperation—agents must negotiate among themselves for maximizing their individual payoffs.

In superadditive environment, each agent can divide the payoffs equally because agents can always form grand coalition which yields maximal benefit for the system. However, in non-superadditive environment, forming grand coalition cannot guarantee such outcome. To yield maximal benefit to the system, cardinalities and coalition values may vary that means some agents may belong to low-valued coalitions, which do not attract agents to cooperate for the benefit of the system. This research applies Shapley Value concept in order to distribute coalition values more fairly. The concept follows the principle of agents’ contribution to the system in order to convey more fairness to agents in small coalitions. The results show that applying the concept can distribute the system’s benefit to coalitions of small, medium and large sizes more fairly and yields maximal benefit to the system. That is it can help agents in coalitions of low values to gains higher payoffs in proportion that the coalitions contribute to the system.