Efficient Monotonicity and Convexity Checks for Randomly Sampled Fuzzy Measures

When dealing with a fuzzy measure on <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math></inline-formula> elements, verifying satisfaction of the monotonicity conditions typically requires performing <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n2^{n-1}$</tex-math></inline-formula> comparisons on measure values, while checking the convexity conditions involves <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\binom{n}{2} 2^{n-2}$</tex-math></inline-formula> comparisons among marginal contributions. The exponential computation required for these checks in fuzzy measure optimization models often leads heuristic algorithms into numerous challenging situations. In this contribution, we propose efficient comparison algorithms based on sorting methods, linear extensions of fuzzy measures, and partial orders on set pairs of marginal contributions. With the aid of these algorithms, the computational complexity is substantially reduced to a linear level on average. Our numerical experiments confirm the significant benefit when it comes to scenarios with large values of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math></inline-formula>, (e.g., <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n&gt;10$</tex-math></inline-formula>), allowing us to apply these methods to problems that were previously intractable.