On the convex hull of k-additive 0-1 capacities and its application to model identification in decision making
Journal article: The Choquet integral w.r.t. a capacity is a versatile tool commonly used in decision making. Its practical 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 number of such vertices is polynomial, and we observe that the loss of generality is very small for n = 4, k = 3, and conjecture that this still holds for larger values of n. Also, we study the geometric properties of the convex hull of 0-1 valued k-additive capacities.
Author(s)
Michel Grabisch, Christophe Labreuche
Journal
- Fuzzy Sets and Systems
Date of publication
- 2022
Keywords
- Capacity k-additive capacity Choquet integral vertices facets
- Capacity
- K-additive capacity
- Choquet integral
- Vertices
- Facets
Pages
- 228-252
URL of the HAL notice
Version
- 1
Volume
- 451