On the convex hull of k-additive 0-1 capacities and its application to model identification in decision making - HAL-SHS - Sciences de l'Homme et de la Société Accéder directement au contenu
Autre Publication Scientifique Documents de travail du Centre d'Économie de la Sorbonne Année : 2022

On the convex hull of k-additive 0-1 capacities and its application to model identification in decision making

Résumé

The Choquet integral w.r.t. a capacity is a versatile tool commonly used in decision making. Its pratical identification requires, however, to solve an optimization problem with exponentially many variables and constraints. The introduction of k-additive capacities, through the use of the Möbius transform, permits to reduce the number of variables to a polynomial size, but leaves the number of constraints exponential. When k = 2, the use of vertices of the set of 2-additive capacities permits to solve the problem as the number of vertices is polynomial. When k > 2, this solution is no more applicable as the set of vertices of k-additive capacities is not known. We propose in this paper to use instead the set of vertices which are 0-1 valued. We show that the loss of generality is small, and that the number of such vertices is polynomial. Also, we study the geometric properties of the convex hull of 0-1 valued k-additive capacities.
L'intégrale de Choquet par rapport à une capacité est un outil versatile communément appliqué en décision. Son identification en pratique requiert par contre de résoudre un problème d'optimisation avec un nombre exponentiel de variables et de contraintes. L'introduction des capacités k-additives, par l'intermédiaire de la transformée de Möbius, permet de réduire le nombre de variables à une taille polynomiale, mais laisse le nombre de contraintes exponentiel. Quand k=2, l'utilisation des sommets de l'ensemble des capacités 2-additives permet de résoudre le problème, car le nombre de sommets est polynomial. Quand k>2, cette solution n'est plus applicable car l'ensemble des sommets des capacités k-additives n'est pas connu. Nous proposons dans ce papier d'utiliser à la place l'ensemble des sommets qui sont 0-1 valués. On montre que la perte de généralité est minime, et que le nombre de tels sommets est polynomial. Egalement, nous étudions les propriétés géométriques de la fermeture convexe des capacités k-additives 0-1 valuées.
Fichier principal
Vignette du fichier
22003.pdf (657.98 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

halshs-03561127 , version 1 (08-02-2022)

Licence

Paternité

Identifiants

  • HAL Id : halshs-03561127 , version 1

Citer

Michel Grabisch, Christophe Labreuche. On the convex hull of k-additive 0-1 capacities and its application to model identification in decision making. 2022. ⟨halshs-03561127⟩

Relations

69 Consultations
58 Téléchargements

Partager

Gmail Facebook X LinkedIn More