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

Résumé En

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.