×

zbMATH — the first resource for mathematics

The complexity of the nucleolus in compact games. (English) Zbl 1348.91073

MSC:
91A43 Games involving graphs
91A12 Cooperative games
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
90C05 Linear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Karthik Aadithya, Tomasz Michalak, and Nicholas Jennings. 2011. Representation of coalitional games with algebraic decision diagrams. Tech. Rep. UCB/EECS-2011-8. Department of Electrical Engineering and Computer Sciences, The University of California, Berkeley.
[2] Thomas Ågotnes, Wiebe van der Hoek, and Michael Wooldridge. 2009. Reasoning about Coalitional Games.Artif. Intell. 173, 1, 45–79. · Zbl 1180.68271
[3] Javier Arin and Vincent Feltkamp. 1997. The nucleolus and kernel of veto-rich transferable utility games.Int. J. Game Theory 26, 1, 61–73. · Zbl 0871.90115 · doi:10.1007/BF01262513
[4] Robert J. Aumann and Michael Maschler. 1985. Game-theoretic analysis of a bankruptcy problem from the Talmud.J. Econ. Theory 36, 2, 195–213. · Zbl 0578.90100 · doi:10.1016/0022-0531(85)90102-4
[5] Yoram Bachrach and Ely Porat. 2010. Path disruption games. InProceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’10), Michael Luck, Sandip Sen, Wiebe van der Hoek, and Gal A. Kaminka (Eds.), 1123–1130.
[6] Yoram Bachrach and Jeffrey S. Rosenschein. 2008. Coalitional skill games. InProceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’08), Lin Padgham, David C. Parkes, Jörg Müller, and Simon Parsons (Eds.), 1023–1030.
[7] Yoram Bachrach, Jeffrey S. Rosenschein, and Ely Porat. 2008. Power and stability in connectivity games. InProceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’08), Lin Padgham, David C. Parkes, Jörg Müller, and Simon Parsons (Eds.), 999–1006.
[8] Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. 1998.Complexity and Real Computation. Springer-Verlag New York, Inc., Secaucus, NJ. · Zbl 0872.68036 · doi:10.1007/978-1-4612-0701-6
[9] Rodica Brânzei, Elena Iñarra, Stef Tijs, and José M. Zarzuelo. 2006. A simple algorithm for the nucleolus of airport profit games.Int. J. Game Theory 34, 2, 259–272. · Zbl 1126.91004
[10] Rodica Brânzei, Tamás Solymosi, and Stef Tijs. 2005. Strongly essential coalitions and the nucleolus of peer group games.Int. J. Game Theory 33, 3, 447–460.
[11] Ning Chen, Pinyan Lu, and Hongyang Zhang. 2012. Computing the nucleolus of matching, cover and clique games. InProceedings of the 26th National Conference on Artificial Intelligence (AAAI-12), Bart Selman and Jörg Hoffmann (Eds.), 1319–1325.
[12] Vincent Conitzer and Tuomas Sandholm. 2004. Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. InProceedings of the 19th National Conference on Artificial Intelligence (AAAI-04), Deborah L. McGuinness and George Ferguson (Eds.), 219–225.
[13] Vincent Conitzer and Tuomas Sandholm. 2006. Complexity of constructing solutions in the core based on synergies among coalitions.Artif. Intell. 170, 6–7, 607–619. · Zbl 1131.91305 · doi:10.1016/j.artint.2006.01.005
[14] Xiaotie Deng, Qizhi Fang, and Xiaoxun Sun. 2009. Finding nucleolus of flow game.J. Combinat. Optim. 18, 1, 64–86. · Zbl 1188.91024 · doi:10.1007/s10878-008-9138-0
[15] Xiaotie Deng and Christos H. Papadimitriou. 1994. On the Complexity of Cooperative Solution Concepts.Math. Oper. Res. 19, 2, 257–266. · Zbl 0824.90146 · doi:10.1287/moor.19.2.257
[16] Jean Derks and Jeronen Kuipers. 1992. On the core and the nucleolus of routing games. Tech. Rep. 92-07. University of Limburg, Maastricht, Netherlands.
[17] Irinel Dragan. 1981. A procedure for finding the nucleolus of a cooperativen person game.Math. Meth. Oper. Res. 25, 5, 119–131. · Zbl 0464.90093 · doi:10.1007/BF01919297
[18] Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg, and Michael Wooldridge. 2009a.On the computational complexity of weighted voting games.Ann. Math. Artif. Intell. 56, 2, 109–131. · Zbl 1185.91081 · doi:10.1007/s10472-009-9162-5
[19] Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg, and Michael Wooldridge. 2009b.A tractable and expressive class of marginal contribution nets and its applications.Math. Logic Quart. 55, 4, 362–376. · Zbl 1175.91022 · doi:10.1002/malq.200810021
[20] Ulrich Faigle, Walter Kern, and Jeroen Kuipers. 1998. Computing the nucleolus of min-cost spanning tree games is NP-hard.Int. J. Game Theory 27, 3, 443–450. · Zbl 1058.91511 · doi:10.1007/s001820050083
[21] Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, and Christopher Umans. 2008.On the Complexity of Succinct Zero-Sum Games.Computational Complexity 17, 3, 353–376. · Zbl 1162.91302 · doi:10.1007/s00037-008-0252-2
[22] Donald B. Gillies. 1959. Solutions to general non-zero-sum games. InContributions to the Theory of Games, Volume IV, Albert William Tucker and R. Duncan Luce (Eds.), Annals of Mathematics Studies, Vol. 40, Princeton University Press, Princeton, NJ, 47–85. · Zbl 0085.13106
[23] Daniel Granot and Frieda Granot. 1992. On some network flow games.Math. Oper. Res. 17, 4, 792–841. · Zbl 0773.90097 · doi:10.1287/moor.17.4.792
[24] Daniel Granot, Frieda Granot, and Weiping R. Zhu. 1998. Characterization sets for the nucleolus.Int. J. Game Theory 27, 3, 359–374. · Zbl 0960.91009 · doi:10.1007/s001820050078
[25] Daniel Granot, Michael Maschler, Guillermo Owen, and Weiping R. Zhu. 1996.The kernel/nucleolus of a standard tree game.Int. J. Game Theory 25, 2, 219–244. · Zbl 0846.90136 · doi:10.1007/BF01247104
[26] Gianluigi Greco, Enrico Malizia, Luigi Palopoli, and Francesco Scarcello. 2010.Non-transferable utility coalitional games via mixed-integer linear constraints.J. Artif. Intell. Res.38, 633–685. · Zbl 1203.91017
[27] Gianluigi Greco, Enrico Malizia, Luigi Palopoli, and Francesco Scarcello. 2011.On the complexity of core, kernel, and bargaining set.Artif. Intell. 175, 12–13, 1877–1910. · Zbl 1233.91018
[28] Martin Grötschel, László Lovász, and Alexander Schrijver. 1993.Geometric Algorithms and Combinatorial Optimization(2nd Ed.). Algorithms and Combinatorics, Vol. 2,Springer-Verlag, Berlin/Heidelberg, Germany.
[29] Eduard Helly. 1923. Über Mengen konvexer Körper mit gemeinschaftlichen Punkten.Jahresbericht der Deutschen Mathematiker-Vereinigung32, 175–176. · JFM 49.0534.02
[30] Samuel Ieong and Yoav Shoham. 2005. Marginal contribution nets: A compact representation scheme for coalitional games. InProceedings of the 6th ACM Conference on Electronic Commerce (EC’05), John Riedl, Michael J. Kearns, and Michael K. Reiter (Eds.), 193–202.
[31] Samuel Ieong and Yoav Shoham. 2006. Multi-attribute coalitional games. InProceedings of the 7th ACM Conference on Electronic Commerce (EC’06), Joan Feigenbaum, John Chuang, and David M. Pennock (Eds.), 170–179.
[32] David S. Johnson. 1990. A catalog of complexity classes. InHandbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, Jan van Leeuwen (Ed.), The MIT Press, Cambridge, MA, 67–161. · Zbl 0900.68246
[33] Ehud Kalai and Eitan Zemel. 1980. On totally balanced games and games of flow. Discussion Paper 413. Northwestern University, Center for Mathematical Studies in Economics and Management Science, Evanston, IL. · Zbl 0498.90030
[34] Walter Kern and Daniël Paulusma. 2003. Matching games: The least core and the nucleolus.Math. Oper. Res. 28, 2, 294–308. · Zbl 1082.91016
[35] Elon Kohlberg. 1972. The nucleolus as a solution of a minimization problem.SIAM J. Appl. Math.23, 1, 34–39. · Zbl 0243.90057 · doi:10.1137/0123004
[36] Alexander Kopelowitz. 1967. Computations of the kernels of simple games and the nucleolus of n-person games.Tech. Rep. RM-31. The Hebrew University of Jerusalem, Jerusalem, Israel.
[37] Mark W. Krentel. 1986. The complexity of optimization problems. InProceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC’86), 69–76.
[38] Jeroen Kuipers. 1996. A polynomial time algorithm for computing the nucleolus of convex games.Report M 96-12. Maastricht University, Maastricht, The Netherlands.
[39] Stephen C. Littlechild. 1974. A simple expression for the nucleolus in a special case.Int. J. Game Theory 3, 1, 21–29. · Zbl 0281.90108 · doi:10.1007/BF01766216
[40] Stephen C. Littlechild and Fred Thompson. 1977. Aircraft landing fees: A game theory approach.Bell J. Econ. 8, 1, 186–204. · doi:10.2307/3003493
[41] Mohammad Mahmoody and David Xiao. 2010. On the power of randomized reductions and the checkability of SAT. InProceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC’10), Dieter van Melkebeek (Ed.), 64–75.
[42] Michael Maschler, Bezalel Peleg, and Lloyd Stowell Shapley. 1979. Geometric properties of the kernel, nucleolus, and related solution concepts.Math. Oper. Res. 4, 4, 303–338. · Zbl 0426.90097 · doi:10.1287/moor.4.4.303
[43] Nimrod Megiddo. 1978. Computational complexity of the game theory approach to cost allocation for a tree.Math. Oper. Res. 3, 3, 189–196. · Zbl 0397.90111 · doi:10.1287/moor.3.3.189
[44] Leonardo Militano, Antonio Iera, and Francesco Scarcello. 2013. A fair cooperative content-sharing service.Comput. Net.(2013).
[45] Marina Núñez and Carles Rafels. 2005. The Böhm-Bawerk horse market: A cooperative analysis.Int. J. Game Theory 33, 3, 421–430. · Zbl 1121.91011
[46] Martin J. Osborne and Ariel Rubinstein. 1994.A Course in Game Theory. The MIT Press, Cambridge, MA. · Zbl 1194.91003
[47] Guillermo Owen. 1974. A note on the nucleolus.Int. J. Game Theory 3, 2, 101–103. · Zbl 0287.90013 · doi:10.1007/BF01766395
[48] Guillermo Owen. 1975. On the core of linear production games.Math. Prog. 9, 1, 358–370. · Zbl 0318.90060 · doi:10.1007/BF01681356
[49] Christos H. Papadimitriou and Kenneth Steiglitz. 1998.Combinatorial Optimization: Algorithms and Complexity(2nd Ed.).Dover Publications. · Zbl 0944.90066
[50] Daniël Paulusma. 2001. Complexity aspects of cooperative games. Ph.D. Dissertation. University of Twente, Enschede, The Netherlands.
[51] Jos A. M. Potters, Johannes H. Reijnierse, and Michel Ansing. 1996. Computing the nucleolus by solving a prolonged simplex algorithm.Math. Oper. Res. 21, 3, 757–768. · Zbl 0873.90127 · doi:10.1287/moor.21.3.757
[52] Michael Rabin. 1955. A note on Helly’s theorem.Pacific J. Math. 5, 3, 363–366. · Zbl 0065.15303 · doi:10.2140/pjm.1955.5.363
[53] Hans Reijnierse. 1995. Games, graphs and algorithms. Ph.D. Dissertation. University of Nijmegen, the Netherlands. · Zbl 0835.90129
[54] Hans Reijnierse and Jos Potters. 1998. The B-nucleolus of TU-games.Games Econ. Behav. 24, 1, 77–96. · Zbl 0910.90275 · doi:10.1006/game.1997.0629
[55] Jayaram K. Sankaran. 1991. On finding the nucleolus of ann-person cooperative game.Int. J. Game Theory 19, 4, 329–338. · Zbl 0733.90083 · doi:10.1007/BF01766424
[56] David Schmeidler. 1969. The nucleolus of a characteristic function game.SIAM J. Appl. Math. 17, 6, 1163–1170. · Zbl 0191.49502 · doi:10.1137/0117107
[57] Alexander Schrijver. 1998.Theory of Linear and Integer Programming. John Wiley & Sons, New York, NY. · Zbl 0970.90052
[58] Lloyd Stowell Shapley and Martin Shubik. 1971. The assignment game I: The core.Int. J. Game Theory 1, 1, 111–130. · Zbl 0236.90078 · doi:10.1007/BF01753437
[59] Tammar Shrot, Yonatan Aumann, and Sarit Kraus. 2010. On agent types in coalition formation problems. InProceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’10), Michael Luck, Sandip Sen, Wiebe van der Hoek, and Gal A. Kaminka (Eds.), 757–764.
[60] Tamás Solymosi. 1993. On computing the nucleolus of cooperative games. Ph.D. Dissertation. University of Illinois, Chicago.
[61] Tamás Solymosi, Harry Aarts, and Theo Driessen. 1998. On computing the nucleolus of a balanced connected game.Math. Oper. Res. 23, 4, 983–1009. · Zbl 0985.91005
[62] Tamás Solymosi and Tirukkannamangai E. S. Raghavan. 1994. An algorithm for finding the nucleolus of assignment games.Int. J. Game Theory 23, 2, 119–143. · Zbl 0811.90128
[63] Tamás Solymosi, Tirukkannamangai E. S. Raghavan, and Stef Tijs. 2005. Computing the nucleolus of cyclic permutation games.Europ. J. Oper. Res. 162, 1, 270–280. · Zbl 1080.91008
[64] Suguru Ueda, Makoto Kitaki, Atsushi Iwasaki, and Makoto Yokoo. 2011. Concise characteristic function representations in coalitional games based on agent types. InProceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11), Toby Walsh (Ed.), 393–399.
[65] Leslie G. Valiant and Vijay V. Vazirani. 1986. NP is as easy as detecting unique solutions.Theoret. Comput. Sci.47, 85–93. · Zbl 0621.68030 · doi:10.1016/0304-3975(86)90135-0
[66] René van den Brink, IIlya Katsev, and Gerard van der Laan. 1998. Computation of the nucleolus for a class of disjunctive games with a permission structure.Tech. Rep. TI 2008-060/3. Tinbergen Institute, Amsterdam, Netherlands. · Zbl 1274.91058
[67] John von Neumann and Oskar Morgenstern. 1953.Theory of Games and Economic Behavior(3rd Ed.). Princeton University Press, Princeton, NJ. · Zbl 0053.09303
[68] H. Peyton Young, Norio Okada, and Tsuyoshi Hashimoto. 1982. Cost allocation in water resources development.Water Resource Res. 18, 3, 463–475. · doi:10.1029/WR018i003p00463
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.