Finding nucleolus of flow game
Xiaotie Deng, Qizhi Fang, Xiaoxun Sun · Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 · 2006
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; ω). The player set is E and the value of a coalition S ⊆ E is defined as the value of the 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 (ω(e) = 1 for each e ∈ 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 computation and recognition of the nucleolus are NP-hard for flow games with general capacity.