Publication: On the vertices of the k-additive core
Full text at PDC
Advisors (or tutors)
The core of a game upsilon on N, which is the set of additive games phi dominating upsilon such that phi(N) = upsilon(N), is a central notion in cooperative game theory, decision making and in combinatorics, where it is related to submodular functions, matroids and the greedy algorithm. In many cases however, the core is empty, and alternative solutions have to be found. We define the k-additive core by replacing additive games by k-additive games in the definition of the core, where k-additive games are those games whose Mobius transform vanishes for subsets of more than k elements. For a sufficiently high value of k, the k-additive core is nonempty, and is a convex closed polyhedron. Our aim is to establish results similar to the classical results of Shapley and Ichiishi on the core of convex games (corresponds to Edmonds' theorem for the greedy algorithm). which characterize the vertices of the core.
E. Algaba, J.M. Bilbao, R. van den Brink, A. Jiménez-Losada, Cooperative games on antimatroids, Discrete Math. 282 (2004) 1–15. J.-P. Barthélemy, Monotone functions on finite lattices: an ordinal approach to capacities, belief and necessity functions, in: J. Fodor, B. De Baets, P. Perny, (Eds.),Preferences and Decisions under Incomplete Knowledge, Physica-Verlag, Wurzburg, 2000. pp. 195–208. J.M. Bilbao, N. Jiménez, E. Lebrón, H. Peters, The selectope for games with partial cooperation, Discrete Math. 216 (2000) 11–27. O. Bondareva, Some applications of linear programming to the theory of cooperative games, Problemy Kibernet 10 (1963) 119–139. A. Chateauneuf, J.-Y. Jaffray, Some characterizations of lower probabilities and other monotone capacities through the use of Möbius inversion,Math. Social Sci. 17 (1989) 263–283. V. Chvátal, Linear Programming, Freeman, New York, 1983. U. Faigle, W. Kern, On the core of ordered submodular cost games, Math. Programming 87 (2000) 483–499. U. Faigle, W. Kern, S. Fekete, W. Hochstättler, The nucleon of cooperative games and an algorithm for matching games, Math. Programming 83 (1998) 195–211. S. Fujishige. Submodular Functions and Optimization. second ed., Elsevier, Amsterdam, 2005. M. Grabisch, k-order additive discrete fuzzy measures and their representation, Fuzzy Sets and Systems 92 (1997) 167–189. J.C. Harsanyi, A simplified bargaining model for the n-person cooperative game, Internat. Econom. Rev. 4 (1963) 194–220. T. Ichiishi, Super-modularity: applications to convex games and to the greedy algorithm for LP, J. Econom. Theory 25 (1981) 283–286. L. Lovász. Submodular function and convexity. In A. Bachem, M. Grötschel, B. Korte, (Eds.), Mathematical Programming. The State of the Art, Springer, Berlin, 1983, pp. 235–257. P. Miranda, M. Grabisch, Optimization issues for fuzzy measures, Int. J. of Uncertainty, Fuzziness, and Knowledge-Based Systems 7 (6) (1999) 545–560. P. Miranda, M. Grabisch, k-balanced capacities, in: Proceedings of the International Fuzzy Systems Association World Congress (IFSA),Beijing, China, July 2005, pp. 455–460. G.C. Rota, On the foundations of combinatorial theory I. Theory of Möbius functions, Zeitschrift fürWahrscheinlichkeitstheorie und Verwandte Gebiete 2 (1964) 340–368. L.S. Shapley, Core of convex games, Internat. J. Game Theory 1 (1971) 11–26. J. Von Neuman, O. Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, NJ, 1944. P. Walley, Statistical Reasoning with Imprecise Probabilities, Chapman & Hall, London, 1991