A Stable and Feasible Payoff Division for Coalition Formation in a Class of Task Oriented Domains

摘要

In the last few years the use of coalition formation algorithms in multi-agent systems has been proposed as a possible way of modelling autonomous agent cooperation. Game theory provides different concepts for the stability of solutions in cooperative games, regarding the fairness of the resultant payment configuration. One of these is the core. In this paper we present an analysis-based upon game theory-for a class of task-oriented problems arising from some Internet transactions. A procedure that guarantees an optimum task allocation is defined, and a new payoff division model is proposed for the corresponding value. We prove that the proposed payoff division lies inside the core. The whole computation (of the optimal value and the payoffs) has a polynomial complexity in the number of agents.