On the polytope of fuzzy measures

Elías F. Combarro, P. Miranda.

In this paper we deal with the problem of studying some mathematical aspects regarding the polytope of fuzzy measures when the referential set is finite. More concretely, we study whether two extreme points are adjacent; for general polytopes, this is a NP-hard problem. However, for the case of fuzzy measures, we give a necessary and sufficient condition for two extreme points to be adjacent. This allows us to prove that it is possible to find out in polynomial time (in the number of minimal subsets) whether two extremes are adjacent. These results can be extended to the polytope given by the convex hull of monotone boolean functions.

PDF full paper