Generating fuzzy measures from additive measures

The relationship between the linear extensions of all subsets in $N$ and the fuzzy measures on $N$ can be summarized as the following statement.

As special fuzzy measures with only $n$ coefficients, additive measures can be adopted as an efficient way to obtain linear extensions and further generate fuzzy measures. However, one main problem is the high repetition of linear extensions obtained by additive measures for small $n$, e.g, $n\leqslant 4$, and furthermore, large part of the linear extensions cannot be reached by additive measures.

In order to mitigate the repetition of a group of existing linear extensions, we can randomly adjust the positions of some subsets without violating the monotonicity condition for each of these linear orders. For a subset $\emptyset\neq A\subset N$ within a linear extension, the following algorithm, 1, can be employed to achieve a compatible adjustment of its position, where $\textbf{Pos}({A})$ represents its position index and $A=\arg\textbf{Pos}({A})$.

Indeed, the above operations can be equivalently performed through adjusting the associated additive measures. Suppose a linear extension is derived from an additive measure established by the nonzero measure values of $n$ singletons, i.e., the weight vector $(w_{1},w_{2},...,w_{n})$ where $\sum_{i}w_{i}=1$ and $\mu(A)=\sum_{i\in A}w_{i}$ for $A\subseteq N$. Then, the following alternative operations can be executed using Algorithm 2.

In algorithms 1 and 2, it is ensured that adjustments about any nonempty proper subset in $N$ do not break any monotonicity condition with respect to set inclusion.

Another method to adjust linear extension is through random walk [17, 11], as shown in algorithm 3 starting from the subset $A$ in the linear extension.

Algorithm 3 demonstrates that in a random walk, if $A$ is not a subset of $\arg(\textbf{Pos}(A)+1)$, their positions are exchanged. The random walk can be applied to a fuzzy measure $\mu$ by replacing the swap operation with setting $\mu(A)$ as a value between $\mu(\arg(\textbf{Pos}(A)+1))$ and $\mu(\arg(\textbf{Pos}(A)+2))$.

Actually, Algorithm 3 can be altered to a different random walk direction by exchanging the values of $A$ and $\arg(\textbf{Pos}(A)-1)$, under the condition that $|A|\leqslant|\arg(\textbf{Pos}(A)-1)|$ or $A\nsupseteq\arg(\textbf{Pos}(A)-1)$. Consequently, the fuzzy measure value of $\mu(A)$ would be adjusted to lie within the range of $\mu(\arg(\textbf{Pos}(A)-1))$ and $\mu(\arg(\textbf{Pos}(A)-2))$.

Now let’s assess the complexity of Algorithms 1 and 3. The former comprises set differences, minimization and maximization, position indexing, and insertion operations, leading to a complexity of at least $2o(|A|)+2o(n)+2o(1)$. The latter involves subset checks, number comparisons, and swap operations, resulting in a complexity ranging from $o(4)$ to $o(|A|)+o(4)$. Hence, one step of random walk proves to be more efficient.

Table 1 presents average results obtained from generating additive measures for universal sets with 3 to 6 elements over 10 iterations. The first through eighth columns correspond to the number of elements, the number of additive measures¹¹1The total number of linear extensions for $n=1$ to $5$ are 1, 2, 48, 1680384, 14807804035657359360, and so on. This sequence is denoted as A046873 in OEIS, with additional values currently unknown [10]. , the repetition ratio of linear extensions for the additive measures, the repetition ratio after applying algorithm 1, and the repetition ratios for one through five steps of random walk, respectively. One can observe that one and two steps of random walk can yield comparable, and sometimes even better, results when compared to Algorithm 1. Employing more steps of random walk can further enhance the performance. For the case of $n=6$, we can conclude that the repetition ratios are all zero for the extensive domain and numerous linear extensions.

The core of a fuzzy measure $\mu$ on $N$ consists of the collection of additive measures $\nu$ on $N$ satisfying $\nu(A)\geqslant\mu(A)$ for all subsets $A\subseteq N$ [23, 15]. Supermodular measures, also known as convex games, are characterized by having a non-empty core, making them totally balanced [24]. This fact inspires the following proposition, which outlines some strategies to adjust additive measures into supermodular measures.

By employing adjustment strategies (S1) and (S2), we can transform an additive measure into a supermodular measure, while their linear extensions remain unchanged. To decrease the repetition ratio of linear extensions and enhance supermodularity, additional refinement of the measure values becomes necessary.

Actually, the Eq. (1) can be rewritten as [15]

Based on this equation, we can determine the permissible range for any nonempty proper subset $A$ to ensure supermodularity as:

By adjusting $\mu(A)$ within the allowable range $[\max(l_{1},l_{2}),l_{3}]$, it will result in a new linear extension if $\mu(A)$ not in the range [$\mu(\arg(\textbf{Pos}(A)-1)),\mu(\arg(\textbf{Pos}(A)+1)]$.

Achieving a new linear extension through random walk for a supermodular measure requires additional checks on measure values beyond the set inclusion conditions listed in Algorithm 3.

If the value of $\mu(A)$ is increased, then $\Delta_{i}\mu(A)$ will decrease and $\Delta_{i}\mu(A\backslash\{i\})$ will increase. To maintain supermodularity, it’s necessary to verify the conditions $\Delta_{i}\mu(A)\geqslant\Delta_{i}\mu(A\backslash\{j\})$ for $i\notin A$ and $j\in A$, and $\Delta_{i}\mu(A\backslash\{i\})\leqslant\Delta_{i}\mu(A\backslash\{i\}\cup\{j\})$ for $i\in A$ and $j\notin A$. However, these two conditions are essentially equivalent (both collapsing to the condition that $\mu(A)\leqslant l_{3}$ given in Algorithm 4). The inclusion of $\min(l_{3},\mu(\arg(\textbf{Pos}(A)+2)))$ in Algorithm 5 ensures that the position of $A$ is swapped only with $(\textbf{Pos}(A)+1))$ if it is feasible.

Conversely, if the value of $\mu(A)$ is decreased (this is also allowed), then $\Delta_{i}\mu(A)$ will increase and $\Delta_{i}\mu(A\backslash\{i\})$ will decrease. To maintain supermodularity after random walk in this direction, we need to check the conditions $\Delta_{i}\mu(A)\leqslant\Delta_{i}\mu(A\cup\{j\})$ for $i,j\notin A$, and $\Delta_{i}\mu(A\backslash\{i\})\geqslant\Delta_{i}\mu(A\backslash\{i,j\})$ for $i,j\in A$, which is equivalent to check the conditions that $\mu(A)\geqslant l_{2}$ and $\mu(A)\geqslant l_{1}$, as given in Algorithm 4. Then if feasible, the $\mu(A)$ can be set as a value between $\mu(\arg(\textbf{Pos}(A)-1))$ and $\max(l_{1},l_{2},\mu(\arg(\textbf{Pos}(A)-2)))$.

The antibuoyant measure is a special type of supermodular measure [2], which can be defined through marginal contributions. A fuzzy measure is antibuoyant if [1]

The core of an antibuoyant measure is a uniform (additive and symmetric) measure [2], specifically an additive measure $\nu$ on $N$ with $\nu(i)=\frac{1}{n}$. Therefore, starting from the uniform measure, we can apply the adjustment strategies (S1) and (S2) to obtain an antibuoyant measure and a strictly antibuoyant measure, respectively.

The allowable range of $\mu(A)$ that ensures still an antibuoyant measure should be:

where $l_{4}=\max_{i,j\in A}(2\mu(A\backslash\{i\})-\mu(A\backslash\{i,j\},2\mu(A\backslash\{j\})-\mu(A\backslash\{i,j\})$, $l_{5}=\max_{i,j\notin A}(2\mu(A\cup\{i\})+\mu(A\cup\{i,j\},2\mu(A\cup\{j\})+\mu(A\cup\{i,j\}))$, $l_{6}=\min_{i\notin A,j\in A}\frac{1}{2}(\mu(A\cup\{i\}+\mu(A\backslash\{j\}))$.

The random walk of $\mu(A)$ for an antibuoyant measure can be given as

On the contrary, if we want to decrease the value of $\mu(A)$ to get a new linear extension for the antibuoyant measure, we need to check whether $\mu(\arg(\textbf{Pos}(A)-1))\geqslant l_{4}$ and $\mu(\arg(\textbf{Pos}(A)-1))\geqslant l_{5}$, then if feasible, set $\mu(A)$ as a value between $\mu(\arg(\textbf{Pos}(A)-1))$ and $\min(l_{4},l_{5},\mu(\arg(\textbf{Pos}(A)-2)))$.

The allowable range and random walk of regular fuzzy measures can be smoothly adapted to $p$-symmetric measures [10] by representing any subset $S$ as a $p$-dimensional vector $\mathbf{b}_{S}=(b_{1},...,b_{p})$ as defined in 7. The subset inclusion relation can be transformed into a partial order of $p$-dimensional vectors: $\mathbf{a}\leqslant\mathbf{b}$ if $a_{i}\leqslant b_{i}$ for $i\in(1,\ldots,p)$. The relationship between sets $A$ and $B=A\backslash\{i\}$ can be represented as $\sum(\mathbf{b}_{A}-\mathbf{b}_{B})=1$. For the initial additive measures for $p$-symmetric measures, the singletons in the same partition of the basis should have the same weight, i.e., $\mathbf{b}_{\{i\}}=\mathbf{b}_{\{j\}}$ implies $\nu(\{i\})=\nu(\{j\})$. As a result, the algorithms and adjustment strategies for normal fuzzy measures, supermodular, superadditive, and buoyant measures are applicable to $p$-symmetric measures. Actually, any normal fuzzy measure can be seen as the $n$-symmetric measure with the basis of $N$, with all subsets being represented as 0-1 valued $n$-dimensional vectors.

When considering $k$-tolerant measures, $k$-interactive measures, and $k$-maxitive measures, our primary focus lies in addressing the random walk or measure value adjustments for subsets with orders lower than $k$. Suppose we already have a fuzzy measure $\nu(A)$ on $N$, no matter it is normal, additive, supermodular, antibuoyant or superadditive fuzzy measure, we can get

• •

  a $k$-tolerant measure $\mu$ by setting

  $$\mu(A)=\begin{cases}\mu(A)=\nu(A)&|A|\leqslant k;\\ \mu(A)=1&|A|\geqslant k+1.\end{cases}$$

  (5)

• •

  a $k$-interactive measure $\mu$ by setting

  $$\mu(A)=\begin{cases}\mu(A)=\frac{K\nu(A)}{\max_{|B|=k}\nu(B)}&|A|\leqslant k;\\ \mu(A)=K+\frac{|A|-k-1}{n-k-1}(1-K)&|A|\geqslant k+1.\end{cases}$$

  (6)

• •

  a $k$-maxitive measure $\mu$ by setting

  $$\mu(A)=\begin{cases}\mu(A)=\frac{\nu(A)}{\max_{|B|=k}\nu(B)}&|A|\leqslant k;\\ \mu(A)=\max_{|B|=|A|-1}\mu(B)&|A|\geqslant k+1.\end{cases}$$

  (7)

We can verify that all the operations mentioned above consistently maintain the monotonicity and normalization conditions, while also satisfying the specific requirements of the three special types of measures.

For $k$-additive measures, $k$-nonadditive measures, and $k$-nonmodular measures, maintaining the zero value for $k+1$ and higher interaction indices magnifies the complexity of adjustment strategies and random walks for the lower $k$-order subsets.