Directed graph-based multi-agent coalitional decision making

摘要

In this paper, we investigate a new kind of decision making problems called multi-agent coalitional decision making (MACDM) problems. In this kind of problems it is analyzed how the actions (strategies) of the agents among a concerned coalition (camp) enhance their own benefits or damage other camps. A special kind of MACDM problems are the MACDM problems with two camps which exist broadly in practice, especially in the situations of two camps (departments, combat forces, enterprises, etc.) competing with each other. This kind of problems is firstly described by the corresponding directed graphs, in which every possible strategy is figured as a directed arc. In this case, each coalitional strategy of the concerned camp is a directed subgraph, and thus can be represented as a simplified adjacency matrix. We construct two integer programming models so as to select the best coalitional strategy by maximizing the benefit of the concerned camp or the damage of the other camp. By considering the characteristic of the integer programming models, we utilize a tabu search algorithm to solve them and prove that the optimal solution can always be reached when the relevant parameters are fixed properly. At length, a simple example is taken to illustrate how to deal with the MACDM problem with two camps.