skip to main content
10.5555/1109557.1109572acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Finding nucleolus of flow game

Published: 22 January 2006 Publication History

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; ω). The player set is E and the value of a coalition SE 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 eE) 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.

References

[1]
R. J. Aumann and M. Maschler, Game theoretic analysis of a bankruptcy problem from the Talmud, Journal of Economic Theory, 36 (1985), pp. 195--396.]]
[2]
Brânzei, R., Solymosi, T. and Tijs, S. H. Strongly Essential Coalitions and the Nucleolus of Peer Group Games, CentER Discussion Paper 2003--19.]]
[3]
X. Deng, T. Ibaraki and H. Nagamochi, Algorithmic aspects of the core of combinatorial optimization games, Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, (1997), pp. 720--729.]]
[4]
X. Deng and C. H. Papadimitriou, On the complexity of cooperative solution concepts, Mathematics of Operations Research, 19 (1994), pp. 257--266.]]
[5]
J. Edmonds, Paths, Trees, and Flowers, Canadian Journal of Mathematics, 17 (1965), pp. 449--467.]]
[6]
Q. Fang, S. Zhu, M. Cai, X. Deng, Membership for core of LP games and other games, Lecture notes in computer science 2108, (2001), pp. 247--256.]]
[7]
U. Faigle and W. Kern, Partition games and the core of hierarchically convex cost games, Universiteit Twente, faculteit der toegepaste wiskunde, Memorandum, No. 1269, 1995.]]
[8]
U. Faigle, W. Kern and J. Kuipers, Computing the nucleolus of min-cost spanning tree games is NP-hard, International Journal of Game Theory, 27 (1998), pp. 443--450.]]
[9]
U. Faigle, W. Kern and J. Kuipers, On the computation of the nucleolus of a cooperative game, International Journal of Game Theory, 30 (2001), pp. 79--98.]]
[10]
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco, 1979.]]
[11]
M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1993.]]
[12]
M. X. Goemans and M. Skutella, Cooperative facility location games, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, (2000), pp. 76--85.]]
[13]
D. Granot, F. Granot and W. R. Zhu, Characterization sets for the nucleolus, International Journal of Game Theory, 27 (1998), pp. 359--374.]]
[14]
D. Granot, M. Maschler, G. Owen and W. R. Zhu, The kernel/nucleolus of a standard tree game, International Journal of Game Theory, 25 (1996), pp. 219--244.]]
[15]
G. Huberman, The nucleolus and the essential coalitions, In: Analysis and Optimizations of Systems, pp. 416--422, Springer, Berlin, 1980.]]
[16]
E. Kalai and E. Zemel, Totally balanced games and games of flow, Mathematics of Operations Research, 7 (1982), pp. 476--478.]]
[17]
E. Kalai and E. Zemel, Generalized network problems yielding totally balanced games, Operations Research, 30 (1982), pp. 498--1008.]]
[18]
W. Kern and D. Paulusma, Matching games: the least core and the nucleolus, Mathematics of Operations Research, 28 (2003), pp. 294--308.]]
[19]
A. Kopelowitz, Computation of the kernels of simple games and the nucleolus of n-person games, RM-31, Math. Dept., The Hebre University of Jerusalem, 1967.]]
[20]
J. Kuipers T. Solymosi and H. Aarts, Computing the nucleolus of some combinatorially structured games, Mathematical Programming, 88 (2000), pp. 541--563.]]
[21]
Jean Lemaire, Lemaire, Jean, An Application of Game Theory: Cost Allocation, ASTIN Bulletin 14, 1 (1984), pp. 61--81.]]
[22]
Joe Malkevitch, Resolving Bankruptcy Claims, Feature Column, Monthly Essays on Mathematical Topics, AMS, March 2005. http://www.ams.org/featurecolumn/index.html.]]
[23]
N. Megiddo, Computational complexity and the game theory approach to cost allocation for ta tree, Mathematics of Operations Research, 3 (1978), pp. 189--196.]]
[24]
G. Owen, On the core of linear production games, Mathematical Programming, 9 (1975), pp. 358--370.]]
[25]
T. E. S. Raghavan, T. Solymosi, An Algorithm to Locate the Nucleolus Prices for a Real Estate Game, GPI XII, 1998.]]
[26]
D. Schmeidler, The nucleolus of a characteristic function game, SIAM Journal of Applied Mathematics, 17 (1969), pp. 1163--1170.]]
[27]
T. Solymosi and T. E. S. Raghavan, An algorithm for finding the nucleolus of assignment games, International Journal of Game Theory, 23 (1994), pp. 119--143.]]
[28]
L. S. Shapley and M. Shubik, The assignment game, International Journal of Game Theory, 1 (1972), pp. 111--130.]]

Cited By

View all
  • (2010)The cooperative game theory foundations of network bargaining gamesProceedings of the 37th international colloquium conference on Automata, languages and programming10.5555/1880918.1880928(67-78)Online publication date: 6-Jul-2010
  • (2009)Computing the nucleolus of weighted voting gamesProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496807(327-335)Online publication date: 4-Jan-2009
  • (2009)On the computational complexity of weighted voting gamesAnnals of Mathematics and Artificial Intelligence10.1007/s10472-009-9162-556:2(109-131)Online publication date: 1-Jun-2009
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
January 2006
1261 pages
ISBN:0898716055

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Author Tags

  1. NP-hard
  2. LP duality
  3. efficient algorithm
  4. flow game
  5. nucleolus

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2010)The cooperative game theory foundations of network bargaining gamesProceedings of the 37th international colloquium conference on Automata, languages and programming10.5555/1880918.1880928(67-78)Online publication date: 6-Jul-2010
  • (2009)Computing the nucleolus of weighted voting gamesProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496807(327-335)Online publication date: 4-Jan-2009
  • (2009)On the computational complexity of weighted voting gamesAnnals of Mathematics and Artificial Intelligence10.1007/s10472-009-9162-556:2(109-131)Online publication date: 1-Jun-2009
  • (2007)Algorithms for core stability, core largeness, exactness, and extendability of flow gamesProceedings of the 13th annual international conference on Computing and Combinatorics10.5555/2394650.2394693(439-477)Online publication date: 16-Jul-2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media