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
Version
  • 1
Volume
  • 451