Experience-Driven Decision Support Systems: The Analytic Hierarchy Process

Abstract

Automatic decision support systems are typically based on objective data and rely on data-driven techniques such as machine learning. Yet, in order to take effective decisions, it is fundamental to incorporate also experience-driven approaches that are able to leverage on the experience of human decision makers and experts. However, there is a need to handle the inconsistencies, contradictions and subjectivity that are typical when human actors are involved. This chapter reviews the analytic hierarchy process technique as a tool to derive absolute relevance values based on relative preference information provided by human decision makers. The main ideas of the methodology are informally presented, a suite of different possible applications is reviewed, and considerations regarding the relation between human and automatic decision-making are discussed. The chapter is complemented by an Appendix providing a formal mathematical presentation of the key concepts.

Appendices

Appendix

This appendix formally presents the key mathematical concepts discussed in the chapter. We will discuss the main machinery underlying the incomplete analytic hierarchy process problem, with particular reference to the logarithmic least-squares method. The interested reader is referred to Godsil and Royle (2001), Bozóki and Tsyganok (2019), Faramondi et al. (2020) and Oliva et al. (2019) for more details.

General Notation

Vectors are denoted in bold, while matrices are shown with upper-case letters. We use ${A}_{ij}$ to address the $\left(i,j\right)\text{-th}$ entry of a matrix $A$ and ${x}_{i}$ for the i-th entry of a vector ${\varvec{x}}$. Moreover, we write ${1}_{n}$ and ${0}_{n}$ to denote a vector with n components, all equal to one and zero, respectively; similarly, we use ${1}_{n \times n}$ and ${0}_{n \times n}$ to denote n × m matrices all equal to one and zero, respectively. We denote by ${{\varvec{I}}}_{n}$ the n × n identity matrix. Finally, we express by $\mathrm{exp}\left({\varvec{x}}\right)$ and $\mathrm{ln}\left({\varvec{x}}\right)$ the component-wise exponentiation or logarithm of the vector ${\varvec{x}}$, i.e., a vector such that ${\mathrm{exp}\left({\varvec{x}}\right)}_{i}={\text{e}}^{{x}_{i}}$ and ${\mathrm{ln}\left({\varvec{x}}\right)}_{i}=\mathrm{ln}\left({x}_{i}\right)$, respectively.

Fig. 9

(Source Faramondi et al., 2020)

Node importance according to the holistic index based on LLS AHP

Graph Theory

Let $G=\left\{V,E\right\}$ be a graph with n nodes $V=\{{v}_{1}, \dots ,{v}_{n}\}$ and e edges

$$E\subseteq V \times V \,\{\left({v}_{i},{v}_{j}\right)\left| {v}_{i}\in V\right\},$$

where $\left({v}_{i},{v}_{j}\right)\in E$ captures the existence of a link from node $v_{i}$ to node $v_{j}$. A graph is said to be undirected if $\left({v}_{i},{v}_{j}\right)\in E$ whenever $\left({v}_{j},{v}_{i}\right)\in E$, and is said to be directed otherwise. In the following, when dealing with undirected graphs, we represent edges using unordered pairs $\{{v}_{i},{v}_{j}\}$ in place of the two directed edges $\left({v}_{i},{v}_{j}\right), \left({v}_{j},{v}_{i}\right)$. A graph is connected if for each pair of nodes $v_{i}$, $v_{j}$ there is a path over G that connects them. Let the neighbourhood ${\mathcal{N}}_{i}$ of a node $v_{i}$ in an undirected graph G be the set of nodes $v_{j}$ that are connected to $v_{i}$ via an edge ${\{v}_{i},{v}_{j}\}\in E.$ The degree $d_{i}$ of a node $v_{i}$ in an undirected graph G is the number of its incoming edges, i.e., ${d}_{i}=\left|{\mathcal{N}}_{i}\right|$. The degree matrix D of an undirected graph G is the n × n diagonal matrix such that $D_{ii}=d_{i}$. The adjacency matrix $\text{Adj}$ of a directed or undirected graph $G=\left\{V,E\right\}$ with n nodes is the n × n matrix such that $\text{Adj}_{ij}=1$ if ${\{v}_{i},{v}_{j}\}\in E$ and $\text{Adj}_{ij}=0$, otherwise. The Laplacian matrix associated with an undirected graph G is the n × n matrix L, having the following structure

$$L_{ij} = \left\{ \begin{gathered} 1,\quad \quad {\text{if}}\;\left\{ {v_i ,v_j } \right\} \in E, \hfill \\ d_i ,\quad \quad \quad \quad \quad {\text{if}}\;i = j, \hfill \\ 0,\quad \quad \quad \quad \;{\text{otherwise}}{\text{.}} \hfill \\ \end{gathered} \right.$$

It is well known that L has an eigenvalue equal to zero, and that, in the case of undirected graphs, the multiplicity of such an eigenvalue corresponds to the number of connected components of G (Godsil & Royle, 2001). Therefore, the eigenvalue zero has multiplicity one if and only if the graph is connected.

Incomplete Analytic Hierarchy Process

In this subsection we review the analytic hierarchy process (AHP) problem when the available information is incomplete.

The aim is to compute an estimate of the unknown utilities, based on information on relative preferences. To this end, consider a set of n alternatives, and suppose that each alternative is characterized by an unknown utility or value w_i  0. In the incomplete information case, we are given a value ${\mathcal{A}}_{ij}=\frac{{\epsilon }_{ij }{w}_{i}}{{w}_{j}}$ for selected pairs of alternatives i, j; such a piece of information corresponds to an estimate of the ratio w_i/w_j, where ϵ_ij  0 is a multiplicative perturbation that represents the estimation error. Moreover, for all the available entries ${\mathcal{A}}_{ij}$, we assume that ${\mathcal{A}}_{ji}={\mathcal{A}}_{ij}^{-1}=\frac{{\epsilon }_{ij }^{-1}{w}_{j}}{{w}_{i}}$, i.e., the available terms ${\mathcal{A}}_{ij}$ and ${\mathcal{A}}_{ji}$ are always consistent and satisfy ${\mathcal{A}}_{ij }{\mathcal{A}}_{ji}=1.$

We point out that, while traditional AHP approaches (Barzilai et al., 1987; Crawford, 1987; Saaty, 1977) require knowledge of every pair of alternatives, in the partial information setting we are able to estimate the vector ${\text{\bf{w}}}={\left[{w}_{1},\dots , {w}_{n}\right]}^{\text{T}}$ of the utilities, knowing just a subset of the perturbed ratios. Specifically, let us consider a graph $G=\left\{V,E\right\}$, with $\left|V\right|=n$ nodes; in this view, each alternative i is associated with a node ${v}_{i}\in V$, while the knowledge of w_{i j} corresponds to an edge $\left({v}_{i},{v}_{j}\right)\in E.$ Clearly, since we assume knowing ${w}_{ij}$ whenever we know ${w}_{ji}$, the graph G is undirected. Let $\mathcal{A}$ be the n × n matrix collecting the terms ${\mathcal{A}}_{ij}$, with ${\mathcal{A}}_{ij}=0$ if $\left({v}_{i},{v}_{j}\right)\notin E.$ Notice that, in the AHP literature, there is no universal agreement on how to estimate the utilities in the presence of perturbations (see for instance the debate in Dyer (1990), Saaty (1990), for the original AHP problem). This is true also in the incomplete information case; see, for instance, Bozóki et al. (2010), Oliva et al. (2017), Menci et al. (2018). While the debate is still open, we point out that the logarithmic least-squares approach appears particularly appealing, since it focuses on error minimization.

For these reasons, we now review the incomplete logarithmic least-squares (ILLS) method (Bozóki et al., 2010; Menci et al., 2018), which represents an extension of the classical logarithmic least-squares (LLS) method developed in Crawford (1987), Barzilai et al. (1987), for solving the AHP problem in the complete information case.

Incomplete Logarithmic Least-Squares Approach to AHP

Within the ILLS algorithm, the aim is to find a logarithmic least-squares approximation w^∗ to the unknown utility vector w, i.e., to find the vector that solves

$${{\text{\bf{w}}}}^{*} = \mathop {{\text{arg min}}}\limits_{{\varvec{x}} \in \mathbb{R}_ + ^n } \left\{ {\frac{1}{2}\sum_{i = 1}^n {\sum_{j \in \rm{\mathcal{N}}_i } {\left( {{\text{ln}}\left( {\rm{\mathcal{A}}_{ij} } \right) - {\text{ln}}\left( {\frac{{x_i }}{{x_j }}} \right)} \right)} } ^2 } \right\}.$$

An effective strategy to solve the above optimization problem is to operate the substitution ${\varvec{y}}=\mathrm{ln}\left({\varvec{x}}\right)$, where $\text{ln}\left(\cdot \right)$ is the component-wise logarithm, so that the above equation can be rearranged as

$${{\text{\bf{w}}}}^{*}=\text{exp}\left(\mathop {\text{arg min}}\limits_{{\varvec{y}}\in {\mathbb{R}}^{n}}\left\{\frac{1}{2}\sum_{i=1}^{n}\sum_{j\in {\mathcal{N}}_{i}}{\left(\text{ln}\left({\mathcal{A}}_{ij}\right)-{y}_{i}+{y}_{j}\right)}^{2}\right\}\right),$$

where $\mathrm{exp}\left(\cdot \right)$ is the component-wise exponential. Let us define

$$\kappa \left({\varvec{y}}\right)=\frac{1}{2}\sum_{i=1}^{n}\sum_{j\in {\mathcal{N}}_{i}}{\left(\mathrm{ln}\left({\mathcal{A}}_{ij}\right)-{y}_{i}+{y}_{j}\right)}^{2};$$

because of the substitution ${\varvec{y}}=\mathrm{ln}\left({\varvec{x}}\right)$, the problem becomes convex and unconstrained, and its global minimum is in the form w  = exp(y^∗), where y^∗ satisfies

$${\left.\frac{\partial \kappa \left({\varvec{y}}\right)}{\partial {\varvec{y}}}\right|}_{{\varvec{y}}={{\varvec{y}}}^{*}}=\sum_{j\in {\mathcal{N}}_{i}}\left(\text{ln}\left({\mathcal{A}}_{ij}\right)-{y}_{i}+{y}_{j}\right)=0, \forall i=1,\dots , n,$$

i.e., we seek the argument of the function that nullifies its derivative. Let us consider the n × n matrix P such that ${P}_{ij}=\mathrm{ln}\left({\mathcal{A}}_{ij}\right)$ if ${\mathcal{A}}_{ij}>0$ and ${P}_{ij}=0,$ otherwise; we can express the above conditions in a compact form as

$$L{{\varvec{y}}}^{*}=P {1}_{n},$$

where L is the Laplacian matrix associated with the graph G. Note that, since for hypothesis G is undirected and connected, the Laplacian matrix L has rank n − 1 (Godsil & Royle, 2001). Therefore, a possible way to calculate a vector ${{\varvec{y}}}^{*}$ that satisfies the above equation is to fix one arbitrary component of ${{\varvec{y}}}^{*}$ and then solve a reduced size system simply by inverting the resulting nonsingular (n − 1) × (n − 1) matrix (Bozóki, & Tsyganok, 2019).

Vector ${{\varvec{y}}}^{*}$ can also be written as the arithmetic mean of vectors calculated from the spanning trees of the graph of comparisons, corresponding to the incomplete additive pairwise comparison matrix $\mathrm{ln}\left(\mathcal{A}\right)$(Bozóki, & Tsyganok, 2019). Finally, it is worth mentioning that, when the graph G is connected, the differential equation

$$\dot{{\varvec{y}}}\left(t\right)=-L{\varvec{y}}\left({\varvec{t}}\right)+P {1}_{n}$$

asymptotically converges to y^∗ (see Olivati-Saber et al., 2007), representing yet another way to compute it. Notably, the latter approach is typically used by the control system community for formation control of mobile robots, since the computations are easily implemented in a distributed way and can be performed cooperatively by different mobile robots. Therefore, such an approach appears particularly appealing in a distributed computing setting.

Merging Multiple Opinions

In view of the developments in this paper, we now provide a way to calculate a ranking for a group of decision makers, each with its own perturbed ratio matrix ${\mathcal{A}}^{\left(u\right)}$ which does not necessarily correspond to a connected graph. To do this consider m decision makers and suppose each decision maker u provides an n × n possibly perturbed sparse ratio matrix ${\mathcal{A}}^{\left(u\right)}$, which has the same structure as a possibly disconnected graph ${G}^{\left(u\right)}=\left\{V,{E}^{\left(u\right)}\right\}$. Denote by

$$G=\left\{V,\bigcup_{u=1}^{m}{E}^{(u)}\right\}$$

the graph corresponding to the overall information provided by the m decision makers (i.e., a graph featuring the union of the edges provided by all decision makers, where repeated edges are allowed), and consider the optimization problem

$${{\text{\bf{w}}}}^{*}=\text{exp}\left(\mathop{\text{arg min}}\limits_{{\varvec{y}}\in {\mathbb{R}}^{n}}\left\{\frac{1}{2}\sum_{u=1}^{m}\sum_{i=1}^{n}\sum_{j\in {\mathcal{N}}_{i}}{\left(\mathrm{ln}\left({\mathcal{A}}_{ij}^{\left(u\right)}\right)-{y}_{i}+{y}_{j}\right)}^{2}\right\}\right),$$

the global optimal solution to the above problem ${{\varvec{y}}}^{*}$ satisfies

$$\sum_{u=1}^{m}L({G}^{(u)}){{\varvec{y}}}^{*}=\sum_{u=1}^{m}{P}^{(u)}{1}_{n}$$

where $L({G}^{(u)})$ is the Laplacian matrix associated with ${G}^{(u)}$ and ${P}^{(u)}$ is an n × n matrix collecting the logarithm of the non-zero entries of ${\mathcal{A}}_{ij}^{(u)},$ while ${P}^{(u)}=0$ when ${\mathcal{A}}_{ij}^{(u)}=0$. Moreover exp(${{\varvec{y}}}^{*})$ is unique up to a scaling factor if and only if G is connected. Looking in greater detail, we observe that the problem is an unconstrained convex minimization problem; therefore, by evaluating the derivative of the objective function at zero, we find that the optimal solution ${{\varvec{y}}}^{*}$ satisfies the above equation.