Decision Support
Implementing stochastic multicriteria acceptability analysis

https://doi.org/10.1016/j.ejor.2005.12.037Get rights and content

Abstract

Stochastic multicriteria acceptability analysis (SMAA) is a family of methods for aiding multicriteria group decision making in problems with inaccurate, uncertain, or missing information. These methods are based on exploring the weight space in order to describe the preferences that make each alternative the most preferred one, or that would give a certain rank for a specific alternative. The main results of the analysis are rank acceptability indices, central weight vectors and confidence factors for different alternatives. The rank acceptability indices describe the variety of different preferences resulting in a certain rank for an alternative, the central weight vectors represent the typical preferences favouring each alternative, and the confidence factors measure whether the criteria measurements are sufficiently accurate for making an informed decision.

The computations in SMAA require the evaluation of multidimensional integrals that must in practice be computed numerically. In this paper we present efficient methods for performing the computations through Monte Carlo simulation, analyze the complexity, and assess the accuracy of the presented algorithms. We also test the efficiency of these methods empirically. Based on the tests, the implementation is fast enough to analyze typical-sized discrete problems interactively within seconds. Due to almost linear time complexity, the method is also suitable for analysing very large decision problems, for example, discrete approximations of continuous decision problems.

Introduction

Stochastic multicriteria acceptability analysis (SMAA) methods have been developed for discrete multicriteria decision aiding (MCDA) problems, where criteria measurements are uncertain or inaccurate and where it is for some reason difficult to obtain accurate or any preference information from the decision makers (DMs) (Lahdelma and Salminen, 2001).

Usually in MCDA problems the preference information is modelled by determining importance weights for criteria. The SMAA methods are based on exploring the weight space in order to describe the preferences that would make each alternative the most preferred one, or that would give a certain rank for a specific alternative. The main results of the analysis are rank acceptability indices, central weight vectors and confidence factors for different alternatives. The rank acceptability indices describe the variety of different preferences resulting in a certain rank for an alternative, the central weight vectors represent the typical preferences favouring each alternative, and the confidence factors measure whether the criteria measurements are sufficiently accurate for making an informed decision.

In MCDA literature outside SMAA, there is a long history of methodologies that allow decision aiding under uncertain and/or imprecise information. See e.g. Dias and Clímaco, 2000, Dias et al., 2002, Fishburn, 1965, Hazen, 1986, Kirkwood and Sarin, 1985, Mousseau et al., 2000, Mousseau et al., 2003, and for more general information on this subject, see Figueira et al. (2005). Although this area has been studied for three decades, the SMAA methods are the first ones allowing both preference information and criteria measurements to be expressed as arbitrarily distributed stochastic variables. The SMAA approach has also recently been applied to extend other MCDA methods to allow using them with imprecise information (see Tervonen et al., 2005).

The SMAA methods are based on inverse weight space analysis, which has also been considered in the works of Charnetski Soland, 1978, Bana e Costa, 1986. In the original SMAA method by Lahdelma et al. (1998) the weight space analysis is performed based on an additive utility or value function and stochastic criteria measurements. The SMAA-2 method (Lahdelma and Salminen, 2001) generalized the analysis to a general utility or value function, to include various kinds of preference information and to consider holistically all ranks. The SMAA-3 method (Lahdelma and Salminen, 2002) applies ELECTRE III type pseudo-criteria in the analysis. The SMAA-O method (Lahdelma et al., 2003) extends SMAA-2 for treating mixed ordinal and cardinal criteria in a comparable manner. The SMAA-A method (or Ref-SMAA method) models the preferences using reference points and achievement scalarizing functions (Lahdelma et al., 2005). Durbach (2006) has also developed a variant of the SMAA-A method using achievement functions.

SMAA methods are applicable in many real-life problem types for a number of reasons. Firstly, the inverse weight space approach is suitable for many group decision-making problems, where the DMs are unable or unwilling to provide preference information, or it is difficult to reach consensus over the preferences. In such cases the preference information can be expressed as weight intervals including preferences of all DMs, or with some other weight distribution accepted by all DMs. SMAA can then be used to compute descriptive information about the acceptability of different alternatives, and this can help the DMs to identify commonly acceptable compromise solutions. Secondly, SMAA supports a very general and flexible way to model different kinds of uncertain or inaccurate preference and criteria information through stochastic distributions. Thirdly, as demonstrated in this paper, the SMAA computations can be implemented very efficiently through numerical methods, making it possible to use the method in many different decision-making contexts, including interactive decision processes. As a consequence, SMAA methods have been successfully applied in a number of real-life decision problems in Finland. For applications of SMAA, see e.g. Hokkanen et al., 1998, Hokkanen et al., 1999, Hokkanen et al., 2000, Kangas et al., 2003, Kangas et al., in press, Kangas and Kangas, 2003, Lahdelma and Salminen, 2006, Lahdelma et al., 2001, Lahdelma et al., 2002.

In this paper we describe how the basic computations of the SMAA-2 and SMAA-O methods can be implemented efficiently through Monte Carlo simulation. We have chosen to present the computations of these two methods, because they form the basis for all other SMAA variants. In particular, we present the algorithms for computing the rank acceptability indices, central weight vectors, and confidence factors. We begin by introducing the SMAA-2 and SMAA-O methods in Section 2. In Section 3, we describe the implementation of the algorithms and discuss techniques for handling preference information. Following this, we analyze the complexity of the algorithms theoretically in Section 4. We assess the accuracy of the computations in Section 5, and present results from empirical efficiency tests in Section 6. We end this paper with conclusions in Section 7.

Section snippets

The basic SMAA-2 method

The SMAA-2 method (Lahdelma and Salminen, 2001) has been developed for discrete stochastic multicriteria decision-making problems with multiple DMs. SMAA-2 applies inverse weight space analysis to describe for each alternative what kind of preferences make it the most preferred one, or place it on any particular rank. The decision problem is represented as a set of m alternatives {x1, x2,  , xm} that are evaluated in terms of n criteria. The DMs’ preference structure is represented by a

Description of the SMAA algorithm

The multidimensional integrals (4), (5), (6) of SMAA computations are in practice impossible to compute analytically, because the distributions fX and fW vary according to the application and can be arbitrarily complex. Straightforward integration techniques based on discretizing the distributions with respect to each dimension are infeasible, because the integrals have a very high dimension, and the required effort depends exponentially on the number of dimensions. For example, in a problem

Complexity of the SMAA algorithm

If all of the criteria are measured on cardinal scales, the complexity of the algorithm for Phase 1 (Algorithm 3) is O(Kw · ϕW + Kw · ϕX + Kw · m · n + Kw · mlog(m) + m2), where ϕW is the complexity of generating a weight vector from the weight distribution and ϕX is the complexity of generating a criterion matrix from the criteria distribution. In many applications the weights are generated from a uniform distribution following the method described before (Algorithm 2). In practice the number of iterations Kw  m

Accuracy of the SMAA computations

The accuracy of the results can be calculated by considering the Monte Carlo simulations as point estimators for bir and pic. By the central limit theorem we can conclude that bir and pic are normally distributed, if the numbers of iterations (Kw, Kc) are large enough (>25) (Milton and Arnold, 1995). In practical SMAA computations the number of iterations is typically 104–106.

If we want to achieve accuracy db with 95% confidence for bir, we need the following number of Monte Carlo iterations Kw (

Empirical tests

We have performed empirical tests to measure the running time of the algorithm separately for Phases 1 and 2. The tests were performed on a GNU/Linux personal computer with one 2.6 GHz Pentium-4 processor and no significant extra load during the tests.

Our test problems include all combinations of the number of alternatives m and number of criteria n, wherem{4,6,8,10,15,25,50,100,150,200}andn{4,8,16,32}.For each problem size we generated six sample problems: three with uniformly distributed

Conclusions

Stochastic multicriteria acceptability analysis is a family of methods for aiding multicriteria group decision making in problems with inaccurate, uncertain, or missing information. The multidimensional integrals which form core of the SMAA computations are in practice impossible to compute analytically. We have demonstrated that the computations can be implemented efficiently with sufficient accuracy using Monte Carlo simulation techniques. With cardinal criteria, the computation time is

Acknowledgements

The work of Tommi Tervonen was partially supported by the MONET research project (POCTI/GES/37707/2001) and grants from Turun Yliopistosäätiö and the Finnish Cultural Foundation.

References (30)

  • R. Lahdelma et al.

    Reference point approach for multiple decision makers

    European Journal of Operational Research

    (2005)
  • V. Mousseau et al.

    A user-oriented implementation of the ELECTRE-TRI method integrating preference elicitation support

    Computers & Operations Research

    (2000)
  • V. Mousseau et al.

    Resolving inconsistencies among constraints on the parameters of an MCDA model

    European Journal of Operational Research

    (2003)
  • J. Charnetski et al.

    Multiple-attribute decision making with partial information: The comparative hypervolume criterion

    Naval Research Logistics Quarterly

    (1978)
  • H.A. David

    Order Statistics

    (1970)
  • Cited by (233)

    View all citing articles on Scopus
    View full text