Title: | Finding Nucleolus of Flow Game |

Author: | Xiaotie Deng, Qizhi Fang, and Xiaoxun Sun |

Book Tittle: | SODA |

Year: | 2006 |

Abstract: | 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,w). The player set is E and the value of a coalition S 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 (w(e) = 1 for each e in 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. |

Cited by 2

@InProceedings{deng06a, author = {Xiaotie Deng and Qizhi Fang and Xiaoxun Sun}, title = {Finding Nucleolus of Flow Game}, booktitle = {{SODA}}, year = 2006, abstract = {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,w). The player set is E and the value of a coalition S 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 (w(e) = 1 for each e in 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.}, keywords = {economics game-theory}, url = {http://jmvidal.cse.sc.edu/library/deng06a.pdf}, cluster = {7614503354907664532} }Last modified: Wed Mar 9 10:16:33 EST 2011