We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

On the core and f-nucleolus of flow games.

Kern, Walter and Paulusma, Daniel (2009) 'On the core and f-nucleolus of flow games.', Mathematics of operations research., 34 (4). pp. 981-991.


Using the ellipsoid method, both Deng et al. [Deng, X., Q. Fang, X. Sun. 2006. Finding nucleolus of flow game. Proc. 17th ACM-SIAM Sympos. Discrete Algorithms. ACM Press, New York, 124–131] and Potters et al. [Potters, J., H. Reijnierse, A. Biswas. 2006. The nucleolus of balanced simple flow networks. Games Econom. Behav. 54 205–225] show that the nucleolus of simple flow games (where all edge capacities are equal to one) can be computed in polynomial time. Our main result is a combinatorial method based on eliminating redundant s–t path constraints such that only a polynomial number of constraints remains. This leads to efficient algorithms for computing the core, nucleolus, and nucleon of simple flow games. Deng et al. also prove that computing the nucleolus for (general) flow games is NP-hard. We generalize this by proving that computing the f-nucleolus of flow games is NP-hard for all priority functions f that satisfy f(A) > 0 for all coalitions A with worth v(A) > 0 (so, including the priority functions corresponding to the nucleolus, nucleon, and per-capita nucleolus).

Item Type:Article
Keywords:Flow game, Computational complexity, Solution concept.
Full text:(VoR) Version of Record
Download PDF
Publisher Web site:
Publisher statement:© 2009 INFORMS
Date accepted:No date available
Date deposited:22 September 2014
Date of first online publication:02 October 2009
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar