Finding nucleolus of flow game

We study the algorithmic issues of finding the nucleolus of a flow game. The flow game is a cooperative game defined on a network D = (V, E; omega). The player set is E and the value of a coalition S subset of E is defined as the value of a maximum flow from source to sink in the subnetwork induced by S. We show that the nucleolus of the flow game defined on a simple network (omega(e) = 1 for each e is an element of E) can be computed in polynomial time by a linear program duality approach, settling a twenty-three years old conjecture by Kalai and Zemel. In contrast, we prove that both the computation and the recognition of the nucleolus are NP-hard for flow games with general capacity.