Choquet-based optimisation in multiobjective shortest path and spanning tree problems

This paper is devoted to the search of Choquet-optimal solutions in finite graph problems with multiple objectives. The Choquet integral is one of the most sophisticated preference models used in decision theory for aggregating preferences on multiple objectives. We first present a condition on preferences (name hereafter preference for interior points) that characterizes preferences favouring compromise solutions, a natural attitude in various contexts such as multicriteria optimisation, robust optimisation and optimisation with multiple agents. Within Choquet expected utility theory, this condition amounts to using a submodular capacity and a convex utility function. Under these assumptions, we focus on the fast determination of Choquet-optimal paths and spanning trees. After investigating the complexity of these problems, we introduce a lower bound for the Choquet integral, computable in polynomial time. Then, we propose different algorithms using this bound, either based on a controlled enumeration of solutions (ranking approach) or an implicit enumeration scheme (branch and bound). Finally, we provide numerical experiments that show the actual efficiency of the algorithms on multiple instances of different sizes.     

Portfolio inertia under ambiguity

We consider individual's portfolio selection problems. Introducing the concept of ambiguity, we show the existence of portfolio inertia under the assumptions that decision maker's beliefs are captured by an inner measure, and that her preferences are represented by the Choquet integral with respect to the inner measure. Under the concept of ambiguity, it is considered that a σ-algebra or even an algebra is not necessarily an appropriate collection of events to which a decision maker assigns probabilities. Furthermore, we study the difference between ambiguity and uncertainty by considering investors' behavior.     

Minimum variance capacity identification

In the framework of multi-criteria decision making whose aggregation process is based on the Choquet integral, we present a maximum entropy like method enabling to determine, if it exists, the “least specific” capacity compatible with the initial preferences of the decision maker. The proposed approach consists in solving a strictly convex quadratic program whose objective function is equivalently either the opposite of a generalized entropy measure or the variance of the capacity. The application of the proposed approach is illustrated on two examples.     

Behavioral multi-criteria decision analysis: the TODIM method with criteria interactions

In this paper a multi-criteria decision aiding model is developed through the use of the Choquet integral. The proposed model is an extension of the TODIM method, which is based on nonlinear Cumulative Prospect Theory. The paper starts by reviewing the first steps of behavioral decision theory. A presentation of the TODIM method follows. The basic concepts of the Choquet integral as related to multi-criteria decision aiding are reviewed. It is also shown how the measures of dominance of the TODIM method can be rewritten through the application of the Choquet integral. From the ordering of decision criteria the fuzzy measures of criteria interactions are computed, which leads to the ranking of alternatives. A case study on the forecasting of property values for rent in a Brazilian city illustrates the proposed model. Results obtained from the use of the Choquet integral are then compared against a previously made usage of the TODIM method. It is concluded that significant advantages exist derived from the use of the Choquet integral. The paper closes with recommendations for future research.     

A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid

The main advances regarding the use of the Choquet and Sugeno integrals in multi-criteria decision aid over the last decade are reviewed. They concern mainly a bipolar extension of both the Choquet integral and the Sugeno integral, interesting particular submodels, new learning techniques, a better interpretation of the models and a better use of the Choquet integral in multi-criteria decision aid. Parallel to these theoretical works, the Choquet integral has been applied to many new fields, and several softwares and libraries dedicated to this model have been developed.      

Entropy of bi-capacities

In the context of multicriteria decision making whose aggregation process is based on the Choquet integral, bi-capacities can be regarded as a natural extension of capacities when the underlying evaluation scale is bipolar. The notion of entropy, recently generalized to capacities to measure their uniformity, is now extended to bi-capacities. We show that the resulting entropy measure has a very natural interpretation in terms of the Choquet integral and satisfies many natural properties that one would expect from an entropy measure.     

A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid

The main advances regarding the use of the Choquet and Sugeno integrals in multi-criteria decision aid over the last decade are reviewed. They concern mainly a bipolar extension of both the Choquet integral and the Sugeno integral, interesting particular submodels, new learning techniques, a better interpretation of the models and a better use of the Choquet integral in multi-criteria decision aid. Parallel to these theoretical works, the Choquet integral has been applied to many new fields, and several softwares and libraries dedicated to this model have been developed.     

An approach to aggregation of ordinal information in multi-criteria multi-person decision making using Choquet integral of Fubini type

An algorithm for the selection among n alternatives based on the evaluation of n (distinct) groups of persons according to the same m criteria is described. The evaluation of each person for each criterion is represented by a proportional ordinal 2-tuple and the overall opinion is aggregated by a pair of quantifier-guided ordered weighted averaging (OWA) aggregation and (floating) anchoring value-based ordered weighted averaging (AV-OWA) aggregation operators. An example is provided to illustrate the algorithm. The decision function of the algorithm is shown to be a Choquet integral of the associated function of two variables (corresponding to the two aggregation processes in the algorithm) which can be accomplished alternatively by a Choquet integral of Fubini type.     

Stochastic multiobjective acceptability analysis for the Choquet integral preference model and the scale construction problem

The Choquet integral preference model is adopted in Multiple Criteria Decision Aiding (MCDA) to deal with interactions between criteria, while the Stochastic Multiobjective Acceptability Analysis (SMAA) is an MCDA methodology considered to take into account uncertainty or imprecision on the considered data and preference parameters. In this paper, we propose to combine the Choquet integral preference model with the SMAA methodology in order to get robust recommendations taking into account all parameters compatible with the preference information provided by the Decision Maker (DM). In case the criteria are on a common scale, one has to elicit only a set of non-additive weights, technically a capacity, compatible with the DM’s preference information. Instead, if the criteria are on different scales, besides the capacity, one has to elicit also a common scale compatible with the preferences given by the DM. Our approach permits to explore the whole space of capacities and common scales compatible with the DM’s preference information.     

A characterization of the 2-additive Choquet integral through cardinal information

In the context of multiple criteria decision analysis, we present the necessary and sufficient conditions to represent a cardinal preferential information by the Choquet integral w.r.t. a 2-additive capacity. These conditions are based on some complex cycles called cyclones.     

Bipolarization of posets and natural interpolation

The Choquet integral w.r.t. a capacity can be seen in the finite case as a parsimonious linear interpolator between vertices of n[0,1]. We take this basic fact as a starting point to define the Choquet integral in a very general way, using the geometric realization of lattices and their natural triangulation, as in the work of Koshevoy.A second aim of the paper is to define a general mechanism for the bipolarization of ordered structures. Bisets (or signed sets), as well as bisubmodular functions, bicapacities, bicooperative games, as well as the Choquet integral defined for them can be seen as particular instances of this scheme.Lastly, an application to multicriteria aggregation with multiple reference levels illustrates all the results presented in the paper.     

On the moments and distribution of discrete Choquet integrals from continuous distributions

We study the moments and the distribution of the discrete Choquet integral when regarded as a real function of a random sample drawn from a continuous distribution. Since the discrete Choquet integral includes weighted arithmetic means, ordered weighted averaging functions, and lattice polynomial functions as particular cases, our results encompass the corresponding results for these aggregation functions. After detailing the results obtained in [J.-L. Marichal, I. Kojadinovic, Distribution functions of linear combinations of lattice polynomials from the uniform distribution, Statistics & Probability Letters 78 (2008) 985–991] in the uniform case, we present results for the standard exponential case, show how approximations of the moments can be obtained for other continuous distributions such as the standard normal, and elaborate on the asymptotic distribution of the Choquet integral. The results presented in this work can be used to improve the interpretation of discrete Choquet integrals when employed as aggregation functions.     

Generalized triangular fuzzy correlated averaging operator and their application to multiple attribute decision making

We investigate the multiple attribute decision making problems with triangular fuzzy information. Motivated by the ideal of Choquet integral [G. Choquet, Theory of capacities, Ann. Instit. Fourier 5 (1953) 131–295] and generalized OWA operator [R.R. Yager, Generalized OWA aggregation operators, Fuzzy Optim. Dec. Making 3 (2004) 93–107], in this paper, we have developed an generalized triangular fuzzy correlated averaging (GTFCA) operator. The prominent characteristic of the operators is that they cannot only consider the importance of the elements or their ordered positions, but also reflect the correlation among the elements or their ordered positions. We have applied the GTFCA operator to multiple attribute decision making problems with triangular fuzzy information. Finally an illustrative example has been given to show the developed method.     

An axiomatization of the Choquet integral in the context of multiple criteria decision making without any commensurability assumption

An axiomatization of the Choquet integral is proposed in the context of multiple criteria decision making without any commensurability assumption. The most essential axiom—named Commensurability Through Interaction—states that the importance of an attribute i takes only one or two values when a second attribute k varies. When the importance takes two values, the point of discontinuity is exactly the value on the attribute k that is commensurate to the fixed value on attribute i. If the weight of criterion i does not depend on criterion k, for any value of the other criteria than i and k, then criteria i and k are independent. Applying this construction to any pair i, k of criteria, one obtains a partition of the set of criteria. In each block, the criteria interact one with another, and it is thus possible to construct vectors of values on the attributes that are commensurate. There is complete independence between the criteria of any two blocks in this partition. Hence one cannot ensure commensurability between two blocks in the partition. But this is not a problem since the Choquet integral is additive between subsets of criteria that are independent.     

一种基于犹豫模糊集的多属性关联决策方法

主要讨论属性间具有关联性的条件下犹豫模糊多属性决策问题.首先,基于gλ模糊测度,Shapley值和Choquet积分,定义了两种犹豫模糊信息集成算子:AHFGSCgλ算子和GHFGSCgλ算子.然后,讨论了这些算子的一些性质.最后通过一个实例来说明算子的可行性和有效性.     

Geometry of decision making and the vector space formulation of the analytic hierarchy process

We extend the conventional Analytic Hierarchy Process (AHP) to an Euclidean vector space and develop formulations for aggregation of the alternative preferences with the criteria preferences. Relative priorities obtained from such a formulation are almost identical with the ones obtained using conventional AHP. Each decision is represented by a preference vector indicating the orientation of the decision maker's mind in the decision space spanned by the decision alternatives. This adds a geometric meaning to the decision making processes. We utilise the measure of similarity between any two decision makers and apply it for analysing decisions in a homogeneous group. We propose an aggregation scheme for calculating the group preference from individual preferences using a simple vector addition procedure that satisfies Pareto optimality condition. The results agree very well with the ones of conventional AHP.     

Belief structures,weight generating functions and decision-making

We describe the Dempster–Shafer belief structure and provide some of its basic properties. We introduce the plausibility and belief measures associated with a belief structure. We note that these are not the only measures that can be associated with a belief structure. We describe a general approach for generating a class of measures that can be associated with a belief structure using a monotonic function on the unit interval, called a weight generating function. We study a number of these functions and the measures that result. We show how to use weight-generating functions to obtain dual measures from a belief structure. We show the role of belief structures in representing imprecise probability distributions. We describe the use of dual measures, other then plausibility and belief, to provide alternative bounding intervals for the imprecise probabilities associated with a belief structure. We investigate the problem of decision making under belief structure type uncertain. We discuss two approaches to this decision problem. One of which is based on an expected value of the OWA aggregation of the payoffs associated with the focal elements. The second approach is based on using the Choquet integral of a measure generated from the belief structure. We show the equivalence of these approaches.     

Possibilistic sequential decision making

When the information about uncertainty cannot be quantified in a simple, probabilistic way, the topic of possibilistic decision theory is often a natural one to consider. The development of possibilistic decision theory has lead to the proposition a series of possibilistic criteria, namely: optimistic and pessimistic possibilistic qualitative criteria [7], possibilistic likely dominance [2], [9], binary possibilistic utility [11] and possibilistic Choquet integrals [24]. This paper focuses on sequential decision making in possibilistic decision trees. It proposes a theoretical study on the complexity of the problem of finding an optimal strategy depending on the monotonicity property of the optimization criteria – when the criterion is transitive, this property indeed allows a polytime solving of the problem by Dynamic Programming. We show that most possibilistic decision criteria, but possibilistic Choquet integrals, satisfy monotonicity and that the corresponding optimization problems can be solved in polynomial time by Dynamic Programming. Concerning the possibilistic likely dominance criteria which is quasi-transitive but not fully transitive, we propose an extended version of Dynamic Programming which remains polynomial in the size of the decision tree. We also show that for the particular case of possibilistic Choquet integrals, the problem of finding an optimal strategy is NP-hard. It can be solved by a Branch and Bound algorithm. Experiments show that even not necessarily optimal, the strategies built by Dynamic Programming are generally very good.     

On the fundamental convergence in the (C) mean in problems of information fusion

The Choquet integral can be regarded as one of aggregation operators being used in information fusion. In this study, we offer an interpretation of sequences of measurable functions and the Choquet integral in the framework of information fusion. Based on an efficiency measure space, we also define a new concept of a fundamental convergence in the (C) mean of sequences of measurable functions and discuss its theoretical underpinnings along with related interpretation issues as well as deliver some new results. Furthermore, an application of this concept is discussed in the context of information fusion. More specifically, based on the theoretical investigations, this idea is applied to the determination of a measurable function being used in the Choquet integral.     

As simple as possible but not simpler in Multiple Criteria Decision Aiding: the robust-stochastic level dependent Choquet integral approach

The level dependent Choquet integral has been proposed to handle decision making problems in which the importance and the interaction of criteria may depend on the level of the alternatives’ evaluations. This integral is based on a level dependent capacity, which is a family of single capacities associated to each level of evaluation for the considered criteria. We present two possible formulations of the level dependent capacity where importance and interaction of criteria are constant inside each one of the subintervals in which the interval of evaluations for considered criteria is split or vary with continuity inside the whole interval of evaluations. Since, in general, there is not only one but many level dependent capacities compatible with the preference information provided by the Decision Maker, we propose to take into account all of them by using the Robust Ordinal Regression (ROR) and the Stochastic Multicriteria Acceptability Analysis (SMAA). On one hand, ROR defines a necessary preference relation (if an alternative a is at least as good as an alternative b for all compatible level dependent capacities), and a possible preference relation (if a is at least as good as b for at least one compatible level dependent capacity). On the other hand, considering a random sampling of compatible level dependent capacities, SMAA gives the probability that each alternative reaches a certain ranking position as well as the probability that an alternative is preferred to another. A real-world decision problem on rankings of universities is provided to illustrate the proposed methodology.