On the vertices of the k-additive core

Abstract : The core of a game v on N, which is the set of additive games φ dominating v such that φ(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 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 Möbius 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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2008, 308 (22), pp.5204-5217. 〈10.1016/j.disc.2007.09.042〉
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-00321625
Contributeur : Michel Grabisch <>
Soumis le : lundi 15 septembre 2008 - 15:05:32
Dernière modification le : mardi 27 mars 2018 - 11:48:05
Document(s) archivé(s) le : jeudi 3 juin 2010 - 21:29:46

Fichiers

dm07.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Michel Grabisch, Pedro Miranda. On the vertices of the k-additive core. Discrete Mathematics, Elsevier, 2008, 308 (22), pp.5204-5217. 〈10.1016/j.disc.2007.09.042〉. 〈hal-00321625〉

Partager

Métriques

Consultations de la notice

258

Téléchargements de fichiers

178