ORIGINAL ARTICLE: José Carlos R. Alcantud (2024), Choquet integral for finite sets: new expression, computation, and applications (a ChatGPT-driven experience). https://imm.webs.upv.es/jornadas/2023/abstracts/abstract74.pdf
Article Abstract: The Choquet integral was developed in 1954 by Gustave Choquet. It was later applied in decision making under uncertainty since the pioneering work of Schmeidler, who proved its most popular characterization. However it was not used for multi-criteria decision aid (MCDA) till the decade of the 1990s. Nowadays many generalizations exist, and the topic is the subject of intense research and development in many areas.
In this paper we explore its utilization with finite sets, especially those of the form
{0,1,2,...,N}
. We find a simple expression of the Choquet integral for this case. Then we show an implementation of this specific formula with Wolfram Mathematica. Finally, we produce applications to
N
-soft sets that include aggregation. Antecedents exist, since Yager’s OWA operator is a particular example of the Choquet integral, and it has been used to aggregate
N
-soft sets recently. In addition to aggregation, the computation of scores of
N
-soft sets is another natural application of this restricted form of the Choquet integral. An Appendix narrates my experience with ChatGPT as an assistant for this work.
The discrete Choquet integral is an aggregation operator that uses a capacity on a finite set X with n elements. A capacity is a monotone set-valued function that vanishes on the empty set.
Two equivalent formulas produce the output for a non-negative vector with n components. One of them uses the increments between pairs of successive values of the vector formed by its ordered components. So initially, the vector is ordered from smallest to largest value. Then we compute an ad-hoc weighted average of the said increments, the weights being the values on the capacity on a decreasing chain of subsets of X defined from the vector.
1
​
Below we implement this formula.
First we find all the subsets of {1,2,....,n}. For illustration, we set n=4.
In[]:=
ClearAll[choquetIntegral,fuzzyMeasure,max,mylist,myvector,maxeval,myorderedvector,n,oneElementRefinementQ,subsets,vector];​​n=4;​​subsets=Subsets[Range@n];
We get the representation of this lattice of subsets as follows:
In[]:=
oneElementRefinementQ[x_,y_]:=Length[y]==1+Length[x]&&SubsetQ[y,x];​​vertices=Reverse/@Subsets[Range[n,1,-1]];​​vCoords=ScalingTransform[{3/2,1}]@RotationTransform[Pi/2]@GraphEmbedding[CompleteGraph[Length/@GatherBy[vertices,Length]]];​​RelationGraph[oneElementRefinementQ,vertices,ImageSize->600,VertexCoordinates->vCoords,VertexSize->Small,EdgeShapeFunction->"Line",VertexShapeFunction->"Circle",VertexLabels->"Name",VertexSize->0.05]
Out[]=
Now we define the discrete capacity or fuzzy measure. We need to associate a number with each subset of {1,2,....,n}. To become a fuzzy measure, this assignment must be monotonic (subsets never get a smaller evaluation than the subsets that it contains), it must vanish on the empty set, and if we use normalized capacities as is standard, it must attain value 1 at {1,2,....,n}.
For simplicity, we drop brackets in the comments:
In[]:=
fuzzyMeasure=ConstantArray[0,2^n];​​fuzzyMeasure[[1]]=0;(*valueofthecapacityattheemptyset*)​​fuzzyMeasure[[2]]=0.2;(*valueofthecapacityat1*)​​fuzzyMeasure[[3]]=0.2;(*valueofthecapacityat2*)​​fuzzyMeasure[[4]]=0.25;(*valueofthecapacityat3*)​​fuzzyMeasure[[5]]=0.25;(*valueofthecapacityat4*)​​​​fuzzyMeasure[[6]]=0.3;(*valueofthecapacityat12*)​​fuzzyMeasure[[7]]=0.3;(*valueofthecapacityat13*)​​fuzzyMeasure[[8]]=0.35;(*valueofthecapacityat14*)​​fuzzyMeasure[[9]]=0.35;(*valueofthecapacityat23*)​​fuzzyMeasure[[10]]=0.4;(*valueofthecapacityat24*)​​fuzzyMeasure[[11]]=0.4;(*valueofthecapacityat34*)​​​​fuzzyMeasure[[12]]=0.4;(*valueofthecapacityat123*)​​fuzzyMeasure[[13]]=0.45;(*valueofthecapacityat124*)​​fuzzyMeasure[[14]]=0.55;(*valueofthecapacityat134*)​​fuzzyMeasure[[15]]=0.7;(*valueofthecapacityat234*)​​​​fuzzyMeasure[[16]]=1;(*valueofthecapacityat1234*)
The standard algorithm computes the value of the discrete Choquet integral defined from this fuzzy measure as follows. We are using a vector with 4 components because we have defined a fuzzy measure on {1,2,3,4}. The algorithm operates on vectors with arbitrary dimension n, and it expects that the fuzzy measure has been defined on the appropriate set {1,2,....,n}.
In[]:=
myvector={0.8,2.95,6.47,5.11};(*thisisthevectorinyourproblem*)​​choquetIntegral=0;​​max=Length[myvector];​​myorderedvector=Prepend[Sort[myvector],0];​​vector=ConstantArray[0,2^Length[X]];​​(*Nowweloopoverallcomponentsofthevector*)​​Do[pos=Position[myvector,x_/;x≥k,1];​​choquetIntegral=choquetIntegral+(myorderedvector[[k+1]]-myorderedvector[[k]])*fuzzyMeasure[[Position[subsets,Union[Flatten[Position[myvector,x_/;x≥Sort[myvector][[k]]]]]][[1,1]]]];,​​{k,1,max}];​​Print["The result is ",choquetIntegral];
The result is 3.509
Now we present an alternative algorithm that computes the discrete Choquet integral when the vector is formed by non-negative integer numbers.
This restriction may seem very strong. However if we note that the discrete Choquet integral is positively homogeneous, then we will be able to use this strategy for finite vectors of numbers that are approximated to a fixed number of decimal positions.
For each vector formed by n non-negative integer numbers, the application of the Choquet discrete integral defined by this capacity will be the product of the list defined above (fuzzyMeasure) by a new vector computed as follows.
Important: We use a random vector “mylist” with 4 components, say that they are between 0 and 10. The user can replace the random vector by any list formed by any number n of non-negative integer elements. The fuzzy measure must be defined on the appropriate set {1,2,....,n}.
mylist=RandomInteger[{0,10},4];​​n=Length[mylist];​​vector=ConstantArray[0,2^n];​​maxeval=Max[mylist];​​Do[pos=Position[mylist,x_/;x≥k,1];​​If[MemberQ[subsets,Union[Flatten[Position[mylist,x_/;x≥k]]]],vector[[Position[subsets,Union[Flatten[Position[mylist,x_/;x≥k]]]][[1,1]]]]+=1],{k,1,maxeval}];
In[]:=
Print["To obtain the application of the Choquet discrete integral to the vector ",mylist," we multiply the list defined above for the fuzzy measure, by the list ",vector,". The result is ",fuzzyMeasure.vector];
To obtain the application of the Choquet discrete integral to the vector {8,4,10,6} we multiply the list defined above for the fuzzy measure, by the list {0,0,0,2,0,0,2,0,0,0,0,0,0,2,0,4}. The result is 6.2
Finally, it might be interesting to have discrete fuzzy measures on arbitrarily large sets in order to conduct numerical experiments. The next routine provides a very simple approach to randomly produce one such fuzzy measure on any set {1,2,....,n}. Essentially, it assigns increasingly larger intervals to sizes in a random manner, so that the more cardinality a subset has, the larger its fuzzy measure, which is randomly extracted from the interval associated with its size.
The routine presents the subsets together with their respective fuzzy measures in the form of a table.
ClearAll[n,subsets]​​n=6;​​subsets=Subsets[Range@n];​​maxvalL=Sort@RandomReal[{0,1},n];​​fuzzyMeasure=ConstantArray[0,2^n];​​Do[​​If[Length[subsets[[k]]]==1,min=0,min=maxvalL[[Length[subsets[[k]]]-1]]];​​max=maxvalL[[Length[subsets[[k]]]]];​​fuzzyMeasure[[k]]=RandomReal[{min,max}];,​​{k,2,2^n-1}​​]​​fuzzyMeasure[[2^n]]=1;​​Multicolumn[Row[#,"-"]&/@Transpose[{Grid[{#},Frame->All]&/@subsets,fuzzyMeasure}],4]
Out[]=
​
-0
3
4
-0.500456
2
3
4
-0.551517
1
3
4
5
-0.604691
1
-0.32737
3
5
-0.500858
2
3
5
-0.504745
1
3
4
6
-0.68629
2
-0.167909
3
6
-0.501775
2
3
6
-0.529403
1
3
5
6
-0.741349
3
-0.0774378
4
5
-0.50069
2
4
5
-0.556409
1
4
5
6
-0.759008
4
-0.297259
4
6
-0.501727
2
4
6
-0.535004
2
3
4
5
-0.697365
5
-0.310967
5
6
-0.500516
2
5
6
-0.53471
2
3
4
6
-0.726536
6
-0.383645
1
2
3
-0.564588
3
4
5
-0.545191
2
3
5
6
-0.613549
1
2
-0.500621
1
2
4
-0.537239
3
4
6
-0.550156
2
4
5
6
-0.739041
1
3
-0.500947
1
2
5
-0.522888
3
5
6
-0.566361
3
4
5
6
-0.738045
1
4
-0.501342
1
2
6
-0.554982
4
5
6
-0.560281
1
2
3
4
5
-0.891958
1
5
-0.50136
1
3
4
-0.516011
1
2
3
4
-0.702127
1
2
3
4
6
-0.900732
1
6
-0.501126
1
3
5
-0.55798
1
2
3
5
-0.702667
1
2
3
5
6
-0.922477
2
3
-0.500702
1
3
6
-0.537074
1
2
3
6
-0.603245
1
2
4
5
6
-0.916031
2
4
-0.501383
1
4
5
-0.545524
1
2
4
5
-0.676683
1
3
4
5
6
-0.941019
2
5
-0.50037
1
4
6
-0.551056
1
2
4
6
-0.781893
2
3
4
5
6
-0.808565
2
6
-0.501222
1
5
6
-0.537634
1
2
5
6
-0.764508
1
2
3
4
5
6
-1

References

[1] Gleb Beliakov, Simon James, and Jian-Zhang Wu. Discrete Fuzzy Measures. Computational Aspects. Springer Nature Switzerland AG 2020. https://doi.org/10.1007/978-3-030-15305-2. Chapter 5.2, equation (5.2)

CITE THIS NOTEBOOK

Choquet integral for finite sets: new expression, computation, and applications​
by José Carlos R. Alcantud​
Wolfram Community, STAFF PICKS, February 21, 2024
​https://community.wolfram.com/groups/-/m/t/3129284