On Random Generation of Supermodular Capacities

Discrete fuzzy measures (capacities) are a powerful tool to model interacting inputs and aggregate them using Choquet, Sugeno, and other fuzzy integrals. Simulation studies and probabilistic optimization algorithms require efficient random sampling from the set of fuzzy measures. It is a challenging problem due to an extremely high complexity of the polytope of capacities. This article addresses random sampling from two special classes: supermodular and submodular fuzzy measures. A suitable marginal contributions representation converts the problem to sampling from an order polytope, which is dealt efficiently using the Markov chain random walk. © 1993-2012 IEEE.