A stochastic method for exploiting outranking relations in multicriteria choice problems

Abstract

The multicriteria decision aiding field offers many methods to support decision makers in comparing a list of alternatives. Among these, outranking methods such as ELECTRE are appreciated for avoiding full compensation among criteria, but outranking relations are difficult to exploit due to incompleteness and lack of transitivity. This work focuses on choice problems, proposing a stochastic exploitation method to select the most preferred alternative. It builds on the concept of Markov solution, which has become popular to select a winner in tournaments and voting problems. The proposed method can be used to exploit crisp outranking relations, valued outranking relations, or stochastic outranking relations. This can be a valuable addition to the toolbox for exploiting outranking relations as this work shows that solutions can be computed without much effort and guarantee some essential properties.

Appendix A

This appendix shows that the simulation process to compute the stationary probabilities, as proposed in Sect. 3.4, is convergent.

Lemma A.1

${P}^{t}$ is bounded for any t.

Proof

From the Chapman–Kolmogorov equation, ${P}_{ij}^{t+s}=\sum_{k=1}^{n}{P}_{ik}^{t}{P}_{kj}^{s}$, it is straightforward to see that, for each alternative $j$ and each integer $t\ge 1$

$$\underset{i}{\mathrm{max}}{P}_{ij}^{t+1}\le \underset{l}{\mathrm{max}}{P}_{lj}^{t} \quad {\text{and}} \quad \underset{i}{\mathrm{min}}{P}_{ij}^{t+1}\ge \underset{l}{\mathrm{min}}{P}_{lj}^{t+1}.$$

Thus,

$$ \begin{aligned} P_{ij}^{t + 1} & = \mathop \sum \limits_{k = 1}^{n} P_{ik} P_{kj}^{t} \le \mathop \sum \limits_{k = 1}^{n} P_{ik} \mathop {\max }\limits_{l} P_{lj}^{t} = \mathop {\max }\limits_{l} P_{lj}^{t} \quad {\text{and}}\\ P_{ij}^{t + 1} & = \mathop \sum \limits_{k = 1}^{n} P_{ik} P_{kj}^{t} \ge \mathop \sum \limits_{k = 1}^{n} P_{ik} \mathop {\min }\limits_{l} P_{lj}^{t} = \mathop {\min }\limits_{l} P_{lj}^{t} .\end{aligned} $$

This shows that, for each column $j$, the largest of the elements is non-increasing with $t$ and the smallest of the elements is non-decreasing with $t$. Thus, the maximum and minimum elements of a column can change with $t$, but the range covered by those elements either shrinks or stays the same as $t\to \infty .$

It should be noted that in general ${P}^{t}$ may not converge despite being bounded, namely when P is the transition matrix of a periodic Markov chain. For instance, for

$$Q=\left[\begin{array}{ccccc}0& 0& 0& 0& 1\\ 0& 0& 0& 0.5& 0.5\\ 0.5& 0.5& 0& 0& 0\\ 0.5& 0.5& 0& 0& 0\\ 0& 1& 0& 0& 0\end{array}\right]$$

$\underset{t\to \infty }{\mathrm{lim}}{Q}^{t}$ does not exist. Furthermore,$\left[\begin{array}{cc}\frac{1}{5}& \frac{1}{5}\end{array} \begin{array}{ccc}\frac{1}{5}& \frac{1}{5}& \frac{1}{5}\end{array}\right] . {Q}^{t}=\left[0.12 0.48 0 0.16 0.24\right]$, if $t$ is odd and $\left[\begin{array}{cc}\frac{1}{5}& \frac{1}{5}\end{array} \begin{array}{ccc}\frac{1}{5}& \frac{1}{5}& \frac{1}{5}\end{array}\right] . {Q}^{t}=\left[0.08 0.32 0 0.24 0.36\right]$, if $t$ is even. However, there is a unique (the algebraic multiplicity of eigenvalue $\lambda =1$ is one) stationary distribution $\pi =\left[\begin{array}{cc}\frac{1}{10}& \frac{2}{5}\end{array} \begin{array}{ccc}0& \frac{1}{5}& \frac{3}{10}\end{array}\right].$

Proposition A.1

The ESS can be approximated by [$\frac{1}{n}\dots \frac{1}{n}$].P^t for a large value of t.

Proof

This approximation is possible if P^t converges as t increases. Let us suppose that P^t does not converge. Then, the Markov chain defined by P must be either unbounded or periodic. Lemma A.1 shows it is not unbounded, therefore lack of convergence can only occur if it is periodic, as occurred for the preceding example matrix Q. Looking at the canonical form of $P$ for a weakly (same for strongly) periodic Markov chain, which is obtained from the transition matrix of a strongly periodic Markov chain by replacing the ones by block matrices ${W}_{i}$ (Gebali, 2008), only the last element of the first row is a non-zero element:

$$P=\left[\begin{array}{ccccccc}0& 0& 0& \dots & 0& 0& {W}_{n}\\ {W}_{1}& 0& 0& \dots & 0& 0& 0\\ 0& {W}_{2}& 0& \dots & 0& 0& 0\\ \vdots & & & \ddots & & & \vdots \\ 0& 0& 0& \dots & 0& 0& 0\\ 0& 0& 0& \dots & { W}_{n-2}& 0& 0\\ 0& 0& 0& \dots & 0& {W}_{n-1}& 0\end{array}\right].$$

In our specific case, the transition matrix is defined by p_ij = c_ij /(n-1) for all $i\ne j$ and ${p}_{ii}=1-{\sum }_{j\ne i}{p}_{ij}$ for all i. Thus, if the first element of the first row is zero, then all the remaining elements of that row must be non-null (more precisely all remaining elements must be 1/(n−1)). This type of transition matrices therefore cannot correspond to the transition matrix of a periodic Markov chain. This, together with the Lemma A.1, shows by contradiction that ${P}^{t}$ converges.