On the vertices of the kk-additive core

The core of a game vv on NN, which is the set of additive games φφ dominating vv such that φ(N)=v(N)φ(N)=v(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 kk-additive core by replacing additive games by kk-additive games in the definition of the core, where kk-additive games are those games whose Möbius transform vanishes for subsets of more than kk elements. For a sufficiently high value of kk, the kk-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.