On computational complexity of membership test in flow games and linear production games

Let Γ≡(N,v) be a cooperative game with the player set N and characteristic function v: 2^N→R. An imputation of the game is in the core if no subset of players could gain advantage by splitting from the grand coalition of all players. It is well known that, for the flow game (and equivalently, for the linear production game), the core is always non-empty and a solution in the core can be found in polynomial time. In this paper, we show that, given an imputation x, it is NP-complete to decide x is not a member of the core, for the flow game. And because of the specific reduction we constructed, the result also holds for the linear production game. Received: October 2000/Final version: March 2002