Finding nucleolus of flow game

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

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: Xiaotie Deng , Toshihide Ibaraki , Hiroshi Nagamochi, Combinatorial optimization games, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.720-729, January 05-07, 1997, New Orleans, Louisiana, United States
• 4: Xiaotie Deng , Christos H. Papadimitriou, On the complexity of cooperative solution concepts, Mathematics of Operations Research, v.19 n.2, p.257-266, May 1994 [doi>10.1287/moor.19.2.257]
• 5: J. Edmonds, Paths, Trees, and Flowers, Canadian Journal of Mathematics, 17 (1965), pp. 449--467.
• 6: Qizhi Fang , Shanfeng Zhu , Mao-cheng Cai , Xiaotie Deng, Membership for Core of LP Games and Other Games, Proceedings of the 7th Annual International Conference on Computing and Combinatorics, p.247-256, August 20-23, 2001
• 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: Ulrich Faigle , Walter Kern , Jeroen Kuipers, Computing the nucleolus of min-cost spanning tree games is NP-hard, International Journal of Game Theory, v.27 n.3, p.443-450, Dec. 1998 [doi>10.1007/s001820050083]
• 9: Ulrich Faigle , Walter Kern , Jeroen Kuipers, On the computation of the nucleolus of a cooperative game, International Journal of Game Theory, v.30 n.1, p.79-98, September 2001 [doi>10.1007/s001820100065]
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1993.
• 12: Michel X. Goemans , Martin Skutella, Cooperative facility location games, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.76-85, January 09-11, 2000, San Francisco, California, United States
• 13: D. Granot , F. Granot , W. R. Zhu, Characterization sets for the nucleolus, International Journal of Game Theory, v.27 n.3, p.359-374, Dec. 1998 [doi>10.1007/s001820050078]
• 14: D. Granot , M. Maschler , G. Owen , W. R. Zhu, The kernel/nucleolus of a standard tree game, International Journal of Game Theory, v.25 n.2, p.219-244, 1996 [doi>10.1007/BF01247104]
• 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: Walter Kern , Daniël Paulusma, Matching games: the least core and the nucleolus, Mathematics of Operations Research, v.28 n.2, p.294-308, May 2003 [doi>10.1287/moor.28.2.294.14477]
• 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: Tamás Solymosi , Tirukkannamangai E. S. Raghavan, An algorithm for finding the nucleolus of assignment games, International Journal of Game Theory, v.23 n.2, p.119-143, 1994 [doi>10.1007/BF01240179]
• 28: L. S. Shapley and M. Shubik, The assignment game, International Journal of Game Theory, 1 (1972), pp. 111--130.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory

Keywords:
NP-hard, LP duality, efficient algorithm, flow game, nucleolus