Algorithmic Issues On The Solutions Of Path Coalitional Games

A cooperative game is a decision analysis model of competition, in which selfish agents want to obtain the interests as large as possible through cooperation together. In the process of the decision, the agents need to consider how to form an coalition and how to divide the total revenue of the cooperation. A cooperative game model (?)=(N,γ) consists of two parts, where N is the set of the players and γ:2Nâ†'R is the characteristic function satisfying γ((?))=0. For each coalition S(?)N, γ(S) represents the gains obtained by the cooperation of the players in S. One of the most important problems in cooperative game theory is to find one or a set of distribution of the total revenue y(N) so as to guarantee the stability of the cooperation. The word "stability" means no player and no subgroup of players can obtain more revenue by escaping from the grand coalition N to form their own coalitions. Different kinds of distribution of total revenue correspond to different solution concepts of the cooperative game. In terms of "stability of cooperation", there are three solution concepts:the core, the least-core and the nucleolus.Given some solution p of the cooperative game (?)=(N,γ), we usually consider the following three questions from the algorithmic and computational complexity point of view:(1) Testing non-emptiness:how to test the existence of p or the non-emptiness of P?(2) Solution construction:how to find an element in p?(3) Checking membership:given a candidate solution, how to decide whether it belongs to p?In this paper, we discuss a kind of cooperative game model arising from flow networks:path coalitional games. Path coalitional game is defined on a directed graph D=(V,E;s,t), in which V,E are vertex and edge sets of D, and s,t are the source and the sink of D, respectively. There are two different kinds of path coalitional games corresponding to the cases where the player set is the edge set and vertex set of D, respectively, called edge path coalitional game and vertex path coalitional game. In both games, the characteristic function is as follows: In this paper, we mainly investigate the algorithmic and computational complexityproblems related to the core, the least-core and the nucleolus for the path coalitionalgames. The main results are as follows:(1) For the core: making use of the equivalence condition of the non-emptinessof the core for simple games, we show that for path coalitional games: the core isnon-empty if and only if the graph D contains only one edge (vertex) disjoint s-tpath, i.e., the maximum number of edge (vertex) disjoint s-t path is1. This yieldsthat all the problems of testing non-emptiness, solution construction and checkingmembership are solved in polynomial time.(2) For the least-core: making use of the linear program model for the least-coreand the theorem of Max-flow and Min-cut, the characterization of the least-core isgiven, that is, the Least-core is equivalent to the set of convex hull of the Min-cuts,divided by the maximum flow value in D. This yields directly that all the problemsof computing the value of the least-core, solution construction and checkingmembership of the least-core can be solved in polynomial time.(3) For the nucleolus: for the sequential linear program algorithm for computingthe nucleolus, we show that only the set of constraints related to the singletons andpath coalitions is enough to characterize the nucleolus, therefore, the sequential linearprograms can be simplified. From the known efficient algorithm for computing thenucleolus of simple flow games, we show that for edge path coalitional games, bothproblems of finding the nucleolus and checking whether a given distribution is thenucleolus are efficient solvable. As for the vertex path coalitional games, it can betransformed to the edge’s case with public edges. Therefore, the correspondingproblems on the nucleolus of a vertex path coalitional game are also solvable inpolynomial time.