Identification of Choquet capacity in multicriteria sorting problems through stochastic inverse analysis
Renata Pelissari Leonardo Tomazeli Duarte
cs.AI stat.OT








rvt]Renata Pelissaricor1
renatapelissari@unicamp.br

rvt]Leonardo Tomazeli Duarte
leonardo.duarte@fca.unicamp.br

[cor1]Corresponding author

[rvt]School of Applied Sciences, UNICAMP, Pedro Zaccaria 1300, 13484-350 Limeira, SP, Brazil


In multicriteria decision aiding (MCDA), the Choquet integral has been used as an aggregation operator to deal with the case of interacting decision criteria. While the application of the Choquet integral for ranking problems have been receiving most of the attention, this paper rather focuses on multicriteria sorting problems (MCSP). In the Choquet integral context, a practical problem that arises is related to the elicitation of parameters known as the Choquet capacities. We address the problem of Choquet capacity identification for MCSP by applying the Stochastic Acceptability Multicriteri Analysis (SMAA), proposing the SMAA-S-Choquet method. The proposed method is also able to model uncertain data that may be present in both decision matrix and limiting profiles, the latter a parameter associated with the sorting problematic. We also introduce two new descriptive measures in order to conduct reverse analysis regarding the capacities: the Scenario Acceptability Index and the Scenario Central Capacity vector. 



Multicriteria sorting problem, Preference elicitation, Capacity identification, Choquet integral, Stochastic Multicriteria Acceptability Analysis







§ INTRODUCTION


    This paper considers a multicriteria sorting problem (MCSP) with m alternatives A={a_1, …, a_m} evaluated in terms of n criteria, g_1, …, g_n, to be sorted into k predefined and ordered categories, K_1, …, K_k. When the considered problem has interacting criteria, a widely used aggregation operator is the Choquet integral <cit.>. Analogously to most of multicriteria decision aiding (MCDA) methods that require a criteria weight vector from the decision-maker (DM), methods whose aggregation procedure is based on the Choquet integral require the prior identification of a capacity. Choquet capacities can be seen as weights to all coalitions of criteria and, therefore, differently from MCDA methods where n-1 weights are required, in the application of the Choquet integral 2^n - 2 parameters are needed <cit.>. 
    
    With the aim of reducing the number of parameters, the concept of 2-additive capacity was introduced in <cit.>. The 2-additive property implies that there may be interaction between any two criteria but not among three or more and it enables to reduce the number of parameters from 2^n - 2 to n(n+1)/2, which represents a significant reduction as n grows. Therefore, a 2-additive capacity offers a good trade-off between ability of modeling interaction and complexity of the model. In this paper, we focus on the 2-additive model. 
    
    Even with the reduction of the numbers of parameters, the DM may still find difficult to define exact values for the capacities. Several works in the literature address this problem known as capacity elicitation or capacity identification by applying supervised, semi-supervised and unsupervised methods, as discussed in depth by <cit.>. Supervised methods, also called preference disaggregation, or indirect elicitation in the MCDA field, require examples of decisions in order to estimate the capacities <cit.>. Although indirect methods are generally attractive for the DM, these exhibit a significant drawback when there is a relatively small reference set of examples <cit.>.
    
    In semi-supervised methods, examples of decision are not required but other type of preference information is needed such as relative importance of criteria and an indication that there is an interaction between two criteria. Examples of semi-supervised methods include works based on diamond pairwise comparison  <cit.> and on the Stochastic Multicriteria Acceptability Analysis (SMAA) <cit.>. 
    
    In unsupervised methods, the elicitation of the capacities is conducted without any prior information from the DM. The only information needed by the method is the decision matrix and the method is strongly based on statistical tools since the interactions between the criteria must be estimated from the observed data <cit.>.
    
    As one can note in the literature, while the proposal of approaches for capacity identification has been focusing on ranking MCDA problems (where the objective is to obtain a ranking of the alternatives), very few similar approaches were proposed for MCSP. In the MCSP context, <cit.> proposed an incremental capacity elicitation approach through a sequence of preference queries.
    
    Our aim is to propose a semi-supervised method for capacity identification in the MCSP context by applying SMAA. Since SMAA methodology is based on an inverse analysis of the space of feasible parameter values, we propose to apply SMAA in order to describe the capacities that make an alternative to be placed into a determined category. To make a reverse analysis possible, the SMAA methodology gives as result descriptive measures which are analyzed by the DM in order to obtain a final decision. Although many descriptive measures have been already proposed for different SMAA variants (see <cit.>), there are still some limitations with regard to descriptive measures in SMAA sorting methods. 
    
    
    Firstly, the acceptability category index, which informs the probability of an alternative to be assigned to a given category, is the only descriptive measure provided by SMAA sorting methods <cit.>. Based on this measure,  alternatives are usually assigned to the category with the highest acceptability category index and it is possible that the classification of two alternatives being resulting from different capacities which may be considered a drawback of SMAA sorting methods. Indeed, it is natural to assume that DMs expect that all alternatives being classified based on the same preference system. In order to overcome this limitation, our recommendation is then to analyze the feasible scenarios formed by the possible combinations of alternatives classification instead of analyzing the individual classification of each alternative. For that, we propose the scenario acceptability index which indicates the probability of occurrence of each feasible scenario.
    
    The second limitation regards the lack of a descriptive measure allowing the reverse analysis. While most of SMAA ranking methods calculates the central weights vector, a descriptive measure that shows the criteria weights which make an alternative ranks first, there is no similar measure for SMAA-sorting methods. We then present the Scenario Central Capacity vector which allows the reverse analysis identifying the capacity vector that makes a scenario possible.
    
   
    
    Therefore, our contribution is threefold: (1) proposal of SMAA-S-Choquet for capacity identification in multicriteria sorting problems; (2) proposal of the scenario acceptability index descriptive measure, introducing the concept of analysing scenarios; (3) proposal of the scenario central capacity vector for reverse analysis in SMAA-S-Choquet. It is important to highlight that both proposed descriptive measures can be easily modify to be used in any SMAA sorting methods. It is also worth mentioning that SMAA-S-Choquet also allows the application of the Choquet integral preference model when the decision matrix and other model parameters are defined by random variables instead of necessarily deterministic values.
    
    This paper is organized as follows. In Section 2, we introduce the Choquet integral preference model for multicriteria sorting problems. In Section 3, we propose the SMAA-S-Choquet method and the new descriptive measures. In Section 4 we conduct some numerical tests and present a numerical example. Conclusions and future research trends are presented in Section 5.
    


§ SORTING WITH THE CHOQUET INTEGRAL PREFERENCE MODEL


        Choquet integral is based on the concept of capacity (fuzzy measure). However, as presented by <cit.>, it is also possible to express the Choquet integral in terms of other measures such as the generalized interaction index. For the 2-additive capacities case, the interaction index between two criteria {g_j, g_s} is represented by I_js and, when the generalized interaction index is calculated for a single criterion, say g_j, it gives rise to the Shapley importance index which is denoted by I_j = I(g_j). Still in the 2-additive capacities context, capacities are completely determined by the Shapley indexes I_j and the interaction indexes I_js. 
        
        In this study, the Choquet integral is parametrized in the generalized interaction index domain. Such a representation admits a direct interpretation, as the Shapley has more practical interpretation. Indeed, the Shapley index I_j quantifies the average importance of a single criterion g_j for the decision process, similar to criteria weights in traditional MCDA methods. Moreover, I_ij>0 models a synergy between g_j and g_s, I_js<0 represents a redundancy between g_j and g_s, and I_js = 0 means that criteria g_j and g_s do not interact. Interaction indices have to meet the boundary and monotonicity coinstraints defined respectively by: 
        
    ∑_j=1^n I_j = 1  and  I_j - 1/2∑_j≠ s|I_js| ≥ 0, ∀ j.

   
        The 2-additive Choquet integral preference model based on the generalized interaction index is expressed by
            
    CI(a)    =   ∑_I_js > 0min{g_j(a), g_s(a)}I_js + ∑_I_js < 0max{g_j(a), g_s(a)}|I_js| 
       +   ∑_j=1^n g_j(a) (I_j - 1/2∑_j≠ s|I_js|).

            
        For the sorting problematic, CI(a) has to be compared to reference profiles which characterize the predefined ordered categories. Reference profiles can be of two types: limiting profiles or central reference profiles. In this paper, we focus on the former, where categories are defined by two limiting profiles, the upper and lower limits of the category. A sorting procedure based on limiting profiles is also known as threshold-based driven sorting procedure. 
        
        Let R = {r_1, …, r_k+1} be the set of limiting profiles, in which r_1 and r_k+1 are the best and the worst, respectively. Since categories are completely ordered, each reference profile is preferred to the successive ones, i.e., r_1 ≻ r_2 ≻…≻ r_k ≻ r_k+1. Moreover, performance of all alternatives of A shall be between the worst and best limiting profiles. Therefore, we have formally that ∀ a_i ∈ A, ∀ g_j ∈ G: g_j(r_1)≥ g_j(a_i) ≥ g_j(r_k+1). 
        
        The Choquet integral sorting formulation according to the threshold-based driven sorting procedure is then defined as follows <cit.>:
        
    a ∈ A  is sorted into category  K_h,  iff  CI(a) ∈ [r_h-1, r_h[.

       


§ THE PROPOSED METHOD: SMAA-S-CHOQUET


    We present the proposed method SMAA-S-Choquet starting by discussing its required input data. The decision matrix and the set of limiting profiles need to be completely defined, although they can be defined by uncertain values. For those situations, evaluations of the alternatives are defined by random variables ξ_ij with a probability density function f_ξ(X) in the space X: 
    
    X = {X ∈ℝ^m ×ℝ^n: ξ_ij, i=1, …, m, j=1, …, n}.

    Uncertain limiting profiles are also represented by random variables ψ with a probability density function f_Y(ψ) in the space Y: 
    Y = {ψ⊆ℝ^(k+1)×ℝ^n: ψ_hj - ψ_lj≤ 0, ∀ h<l, h=1, …, k, j=1, …, n}.

    
    Choquet capacities are not directly required. Indeed, our aim is the identification of the capacities. However, some preference information are still required from the DM. We shall suppose that the DM is able to provide some indirect preference information in terms of the interaction index, indicating which pairs of criteria are synergistic or redundant, and in terms of the Shapley index, indicating the relative importance of the criteria. This preference information then results in the following restrictions:
         
             
  * Restrictions related to the DM preference information regarding interaction index:
                
    E^DMP-I
                     I_js > 0, if criteria j and s are synergy,
    
                     I_js < 0, if criteria j and s are redundant.

            
  * Restrictions related to the DM preference information regarding the Shapley index:
                
    E^DMP-S
                        I_j ≥ I_s , if  j ≽ s, 
    
                        I_j > I_s , if  j ≻ s, 
    
                        I_j = I_s , if  j ∼ s.

            
  * In addition to the restrictions related to the DM preferences, restrictions that ensure monotonicity and boundary conditions shall also be considered for the capacity identification (E^MB):
                
    ∑_j=1^n I_j = 1  and  I_j - 1/2|∑_j ≠ s| ≥ 0, ∀ j.

              
    We shall call compatible model a capacity whose interaction index representation satisfies the set of constraints E = E^DMP-I∪ E^DMP-S∪ E^MB. Total lack of preference information is possible only regarding the Shapley index. In this case, E reduces to E = E^DMP-I∪  E^MB.
    
    In the rest of this section, we describe the simulation scheme, presented in Algorithm 1, on which the SMAA-S-Choquet is based, and present the new descriptive measures proposed here. 
    
    The simulation processes starts starts by drawing criteria evaluations and limiting profiles from their probability distributions. Criteria evaluations g_j(a_i) have to be sampled in order to be between the worst and best sampled limiting profiles. 



    For capacity elicitation we apply a simulation process based on the Hit-And-Run (HAR) method <cit.>. The Hit-And-Run sampling begins with the choice of one point inside the constrained capacity space E. At each iteration, a random direction is sampled that, with the considered position, generates a line. The intersection of this line with the boundary of space E generates a line segment from which the next point is drawn uniformly. The HAR sampler is implemented using the hitandrun package for the R statistical software proposed by Tervonen and available at http://cran.r-project.org/web/packages/hitandrun/.
    
    Then, using the sampled values and the capacity vector elicited, the Choquet integral sorting formulation is applied. The obtained result is the classification of each alternative to the predefined categories. A “scenario” is here understood as the conjoined categorization of all alternatives. Denoting by v⃗_t each possible scenario, we have the following definition: 
    
    v⃗_t= {(K^t(a_1), K^t(a_2), …, K^t(a_m))},

    where K^t(a_i) = K_h is the category h assigned to alternative a_i in scenario v⃗_t. For simplification and for better visualization, each element of the vector scenario can also be denoted simply by the number of the category K^t(a_i) = h. Based on the scenarios, the following statistics are collected:
    
        
  * B_t: the number of times that scenario v⃗_t occurs.
        
  * I⃗_t^x: Shapley index associate to scenario t, for each time x=1,…, B_t that scenario v⃗_t occurs. 
     
    
    This process should be repeated a sufficient number of times in order to extract robust statistical information – in previous works, 10,000 iterations were conducted <cit.>. After the last iteration of the simulation process, descriptive measures are computed in order to help the DM achieve a final decision. 
    
    The category acceptability index (C_i^h, i=1,…, m, h=1, …, k) is the measure given by SMAA sorting methods <cit.>. It represents the probability of an alternative to be sorted into a category; very often, the alternatives are attributed to the category with the highest category acceptability value. For instance, let us consider a decision-making problem with two alternatives and two categories in which C_1^1 = 0.9 and C_1^2 = 0.1, and C_2^1 = 0.38 and C_2^2 = 0.62. Therefore, the DM may conclude that a_1 and a_2 should be sorted into categories K_1 and K_2, respectively. It is reasonable to assume that the DM wants to sort the set of all alternatives based on the same capacity vector, i.e, whether alternative a_1 is categorized to category K_2 considering that criteria 1 is more important than criteria 2, for instance, one expects that the categorization of the other alternative is also based on the fact that criteria 1 is more important than criteria 2. However, there is no guarantee that this occurs when using the category acceptability index. 
    
    In order to overcome this drawback, we propose the Scenario Acceptability Index (SAI), which is based on the category acceptability index, but it uses the concept of scenario (introduced right above) instead of individual classifications of the alternatives. While the category acceptability index represents the probability of an alternative to be sorted into a category, SAI represents the probability of a scenario occurring. Therefore, based on the collected statistics, estimates for the SAI are computed by
    
    SAI_t = B_t/N,

    where N is the total number of executions.
    
    The SAI of an impossible scenario is equal to 0, the SAI of any feasible scenario is between 0 and 1 and the sum of all SAI is equal to 1. The greater the value of SAI_t, the greater the probability of a scenario v⃗_t occurring. Therefore, SAI is suggested to be used to support the prioritization of scenarios and, consequently, the indication of categories assigned to each alternative.  
    
    The capacity vector that makes a scenario possible is also a relevant criterion to be used by the DM for prioritizing scenarios. For that, we propose the Scenario Central Capacity vector which is based on the central capacity vector (introduced by <cit.>). While the latter represents the typical preferences that make an alternative preferred in a ranking problem, scenario central capacity vector I⃗^c_t represents the typical DM preferences that make possible the occurrence of scenario v⃗_t. It is regarded as the expected centroid of the favorable capacity space and is defined:
    
    I⃗^c_t = ∑_x=1^B_tI⃗_t^x/B_t.

    The scenario central capacity vector allows a reverse analysis of capacities in the application of SMAA-S-Choquet. The proposed method SMAA-S-Choquet was implemented by the authors in the R statistical software. 
    


§ EXAMPLE AND EXPERIMENTS


    The proposed method is illustrated by the following synthetic example inspired by <cit.> and <cit.>. The dean of a technical school wants to categorized five students into 3 categories, accepted (K_1), waitlisted (K_2) and rejected (K_3), based on their grades on Mathematics and Statistics. A student good in Mathematics and in Statistics is of course well appreciated, but since students good in Mathematics are in general also good in Statistics, the dean does not want to overvalue students having good grades in both. Therefore, we can say that there is a negative interaction (redundancy) between Mathematics and Statistics.
    
    In order to apply the SMAA-S-Choquet, indirect preference information in terms of the interaction index is required. To represent the redundancy between Mathematics and Statistics the dean defined I_12 <0. Defining preference information regarding Shapely index is not mandatory but it can be included in the model if the DM wishes, and the dean defines that the importance of both subjects are the same (I_1 = I_2).
    
    Students were evaluated based on 10 tests applied in each subject, as presented in Table <ref> (Statistics grades were omitted for lack of space). Instead of considering the average grade, we assume the grades of each student in each subject as a random variable following a normal distribution whose parameters, mean and standard deviation, are estimated from the sample of 10 tests (Table <ref>). When defining the limiting profiles, the dean demonstrated imprecision in relation to some of them, which was represented by interval values. The dean also assumes that the limiting profiles are the same for both subjects R={10, [7.5, 8], [4.5, 5], 0}. 
    
    
Applying SMAA-S-Choquet, t=40 feasible scenarios were obtained. In Table <ref>, we present the five main scenarios and their respective SAI(t) and I⃗^c_t. 
    
    Analyzing the scenario acceptability index SAI, the dean may choose either scenario v⃗_1 or v⃗_2 since both have the highest SAI values (SAI(1)=18% and SAI(2)=16%). To decide between these two, it is important to identify the scenario which capacity better describes the dean' preferences. Since the dean defined I_1=I_2, due to the monotonicity condition, the HAR approach generates I_1=I_2=0.5 for all scenarios and iteration, which leads the dean to focus on analyzing the interaction index I_12. One may realize that the higher the interaction index absolute value I_12, the more the alternatives are sorted into better categories. Indeed, the higher the absolute value I_12, the more redundant are considered the two subjects, and therefore, the more sufficient is a good grade in only one subject. Therefore, the dean should choose scenario v⃗_1 over v⃗_2 only if she wants to consider a higher interaction index absolute value.
    
    We also present the category acceptability index in Table <ref> in order to compare it to the result obtained by using SAI. Based on the category acceptability index, the final categorization of alternatives would be identical to scenario v⃗_1. However, with this example, it becomes clear that this information (the category acceptability index) is not enough to support the DM since information regarding the capacities is also needed. 
    
    In order to verify the robustness of SMAA-S-Choquet, we performed a numerical experiment regarding sampling variability, on synthetic data. Specifically, we run each proposed model with 200 iterations, and the mean and standard deviation of scenario acceptability indices and scenario capacity vectors are computed. 
    
    The MCSP considered in this experiment has the following characteristics: two criteria, ten alternatives and three categories were considered; the same limiting profiles are defined by both criteria R={10,7,5,3,0}; criteria 1 is less important than criteria 2, i.e, I_1<I_2; there is a redundancy between g_1 and g_2, i.e, I_12 < 0. The decision matrix is randomly generated according to a uniform distribution in the range [0,10] (Table <ref>).
    



By analyzing Table 5, we see that the variability in the estimation of SAI(t) does not change the prioritization of the scenarios. The variability in the estimation of the interaction and Shapley indices is also low, which shows that I⃗^c_t is a suitable measure to differentiate the scenarios.



The low variability of the I⃗^c_t estimation also indicates that this is a stable measure for estimating capacities for each scenario. The confidence intervals of I⃗^c_t are shown in Figure <ref>. On the x-axis we have the scenarios and on the y-axis the estimations of I⃗^c_t. One can also see that the variability is higher for scenarios with low SAI, as occurs for scenario v⃗_15. In addition, we also analyzed the distribution of the elicit capacities (I⃗^c_t) of the three scenarios with the highest SAI (Figure <ref>). We can see that the histograms are centralized and close to a normal distribution, indicating that using a measure such as I⃗^c_t, which is computed based on the mean, is appropriate.


  
    
    
    

    


§ CONCLUSION

    
    In this paper, a new capacity identification method was proposed for sorting problems based on stochastic inverse analysis. The scenario concept was introduced for SMAA sorting methods and new descriptive measures were proposed. Experiments with synthetic data were carried out in order to demonstrate the effectiveness of the proposed method. The presented experiment comprised the analysis of the proposed method considering uncertainty only in the capacities, but other experiments considering uncertain decision matrix and limiting profiles shall also be conducted in the future. 
    
    
    


§ ACKNOWLEDGMENTS

    This study was funded by grant #2018/23447-4, São Paulo Research Foundation (FAPESP). L.T. Duarte thanks the National Council for Scientic and Technological Development (CNPq, grant number 311357/2017-2) for funding his research.
   




 
tocchapterBibliografia

    


