Coalition formation based on marginal contributions and the Markov process

• A new coalition formation method considers structure generation and payoff division.
• We prune the search space by the relation of marginal contributions and Shapley values.
• The coalitions are formed by estimating probability distributions of Markov states.
• It is experimentally showed that the method proposed is effective and efficient.

With competition intensifying in the globalized economy, an increasing number of firms are forming coalitions or alliances to improve purchasing efficiency and reduce operating costs in various industries. Forming such coalitions or alliances has become a key research challenge in two important kinds of decision support systems, namely group support systems and negotiation support systems, since the number of possible coalitions is very large in most cases. Most of the existing research on coalition formation focuses on generation of optimal structures alone. Nevertheless, self-interested agents, who are mainly concerned with their own benefits, usually determine whether to join a coalition on the basis of payoffs they can possibly get from the coalition. Accordingly, in this paper, we propose a novel method of coalition formation to enable agents to improve their own benefits based on marginal contributions and the Markov process. Our method considers both coalition structure generation and payoff division which are two primary concerns of group and negotiation support systems.By using a real-world scenario, we give an example of formation of retailer coalitions to illustrate the proposed method. Finally, it is experimentally showed that the method proposed in this paper is effective and efficient, compared with other existing methods. The coalitions generated by our algorithms can significantly increase most agents' payoffs. The managerial implication of our research is that firms can apply the proposed method to identify the most beneficial coalition network with their business partners.