Skip to main content

Research Repository

Advanced Search

On the core and f-nucleolus of flow games

Kern, W.; Paulusma, D.

On the core and f-nucleolus of flow games Thumbnail


Authors

W. Kern



Abstract

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).

Citation

Kern, W., & Paulusma, D. (2009). On the core and f-nucleolus of flow games. Mathematics of Operations Research, 34(4), 981-991. https://doi.org/10.1287/moor.1090.0405

Journal Article Type Article
Online Publication Date Oct 2, 2009
Publication Date Nov 1, 2009
Deposit Date Dec 15, 2009
Publicly Available Date Sep 22, 2014
Journal Mathematics of Operations Research
Print ISSN 0364-765X
Electronic ISSN 1526-5471
Publisher Institute for Operations Research and Management Sciences
Peer Reviewed Peer Reviewed
Volume 34
Issue 4
Pages 981-991
DOI https://doi.org/10.1287/moor.1090.0405
Keywords Flow game, Computational complexity, Solution concept.
Public URL https://durham-repository.worktribe.com/output/1522793
Publisher URL http://mor.journal.informs.org/cgi/content/abstract/34/4/981

Files





You might also like



Downloadable Citations