Improvement of Pair‐wise Comparison Methods Based on Graph Theory Concepts

Abstract

   The paper briefly summarizes the currently available results of recent research on improvement of decision support methods, based on pair-wise comparisons of alternatives. Pair-wise comparison structures (especially, incomplete ones) can be easily represented by non-directed incidence graphs. It turns out that smaller-diameter quasi-regular graphs ensure higher credibility and consistency of expert session results, and maintain stability of preference structures. Particular pair-wise comparison patterns, both taking and not taking the rough ranking of alternatives into account, allow expert session organizers to significantly reduce the minimum required number of pair-wise comparisons, especially on large numbers of alternatives, without compromising the quality of expert data and credibility of expert session results. Following these patterns also allows us to reduce the computational complexity of pairwise comparison-based decision support methods. Improved pair-wise-comparison-based decision support methods are widely applicable to decision-making problems in weaklystructured subject domains, calling for expert estimation.

Keywords

•  1  pair-wise comparison matrix
• spanning tree
• graph diameter
• graph regularity
• ranking

-

units. So, as many researchers (from Condorcet to Saaty [ 1 ], from Kendall to Hwang & Yoon [ 6 ]) show, the best to measure the objects and significance of criteria, by which these objects are evaluated, is to compare them with each other. This assumption provides the basis for a whole family of expert pairwise comparison (PWC) methods.

The methods prove to be highly efficient, especially in weakly-structured subject domains. However, they have some common problems, which researchers around the globe are trying to solve.

The key problems are as follows.

1. Subjectivity of experts. Reasons: cognitive biases, mindsets, background, experience etc. 2. Often, low credibility of expert session results. Reasons: expert estimation errors, inconsistency, incompatibility, incompleteness, insufficiency, low degree of detail of expert data. 3. Large numbers of pair-wise comparisons required to obtain the resulting priorities, and high computational complexity of priority calculation methods.

While selection of competent and unbiased experts (problem 1) is, mostly, the responsibility of the decision-maker (DM), high quality of expert data representation (problem 2), sufficient numbers of comparisons, and manageable computational complexity of priority calculation methods (problem 3) can be ensured through certain mathematical procedures.

So, in our paper we are going to outline several approaches, based on graph theory, targeted at reduction of labor-intensity (problem 3) and improvement of credibility (problem 2) of PWC-based decision support methods.

2. Problem statement 

Let us start by formulating the common problem of priority calculation based on a set of PWC (as posed in AHP and other related methods [ 1,2 ]). by one or several experts. A multiplicative pair-wise comparison matrix (PCM) looks as follows: We have a set of objects (or alternatives) ; 1. . , which are compared among themselves ; , 1. . ; ∀, : 1/ or … … … … … .

We need to find the set of normalized relative alternative weights ; 1. . ; ∑

1 , which would allow us to rate the alternatives.

Methods of priority elicitation from a PCM are quite numerous. They include eigenvector method [ 1,2 ], best/worst method [ 7,8 ], geometric mean (GM) [ 9 ], combinatorial method of spanning tree enumeration [ 10 ], logarithmic least squares [ 11 ]. All these methods have a lot in common, but produce different results. In this paper we are going to address some modifications of available priority calculation methods, based on graph theory.

3. Problem solution ideas 

In the context of this paper, it is important to note, that alongside PCM, graphs represent a handy instrument for representation of PWC. That is, any object can be represented by a graph node (vertex), while a PWC between any two objects can be represented by the respective edge of a graph, and a complete PCM of dimensionality can be represented by a complete graph with nodes.

When it comes to PWC methods, credibility improvement and computational complexity reduction can be achieved through several conceptual ways or approaches. The approaches are as follows.

Comparisons of alternatives can be performed and ordered according to specific patterns (represented by respective graphs) [ 12,13 ].

Comparisons can be performed and ordered according to the ranking of alternatives [ 7,8,14 ]. Comparisons can be performed according to both specific patterns (incidence graphs) and given alternative ranking [ 15 ].

In subsequent sections we will address these conceptual approaches and patterns in greater detail. 4. Modified combinatorial method of spanning tree enumeration  In order to be able to rate a set of objects, it is enough to perform at least 1 independent PWC (build a connected PWC graph, spanning all the objects, called a spanning tree). For example, we can compare all objects with the 1st one, the last one, the best one, the worst one, the neighboring one in the ranking etc. At the same time, in order to obtain a complete set of PWC, an expert has to compare all objects with each other, and, thus, perform 1/2 enumeration of all basic sets of 1 by the respective spanning tree graph (Fig. 1).

PWC. Combinatorial method is based on independent PWC. Each of these basic sets can be represented

(ICPCM). Any row or column of this ICPCM (or any other set of 1 fact, a set of alternative weights. Priorities which we need to find in the above problem statement, are independent PWC) is, in calculated as GM across all ICPCM (spanning trees) (1).

∏ ⁄ ; 1. . (1) According to Cayley’s theorem on trees [ 16 ], the total number of trees, which can be built on . So, for example, the maximum number of trees we need to analyze in objects, amounts to objects – 8

262144 order to calculate the relative weights of 6 objects is 6 1296 ; 7 objects – 7 16807 ; 8 etc. These numbers illustrate considerable computational complexity of the method. The ordinary combinatorial method, based on formula (1) turns out to be mathematically equivalent to row GM [ 9 ] and LLSM [ 11 ]. However, we are using a modified method. Instead of ordinary GM formula (1) it uses weighted GM (2).

∏, ∏ ∑,, ; 1. . (2)

In formula (2) is the number of experts, and is the rating of the respective ICPCM, reflecting completeness, detail, consistency, and compatibility of expert data (as explained in [ 10, 12 ]). So, beside , we need to calculate the respective ICPCM ratings. As a result, for larger “transitive” weights tremendous. numbers of objects, the computational complexity of the modified method (2) becomes really

So, how can we reduce the computational complexity of the method without compromising the quality (credibility) of the result? We suggest sorting the spanning trees according to their diameter. A diameter of a graph is the longest shortest distance between two nodes.

The smallest possible spanning tree diameter value is 2. It is the diameter of a star-type spanning tree, where one of the alternatives is compared to all other alternatives from the set (Fig. 2a). The respective PWC form one row or column of a PCM.

The largest possible spanning tree diameter value is 1

. It is the diameter of a path-type spanning tree, where each alternative is compared to the neighboring ones (Fig. 2b). The respective PWC are located above the principal diagonal of the PCM. Figure 2: Examples of a star‐type and path‐type trees for 5 alternatives  b max , (3) /

If we assume that the maximum error made by an expert during PWC , then the maximum

error accumulated on a path-type tree equals approximately 1 , on a star-type tree 2 [ 12 ]. If we have a spanning tree of diameter , then ∓ 1 ∓ In (3)

. Under small the accumulated error equals approximately . So, based on these considerations, it makes sense to start with enumerating smaller-diameter spanning trees, because they accumulate smaller expert errors. Experiments from [ 12 ] show that weighted GM across smallerdiameter spanning trees yields approximately the same results as weighted GM across all trees.

Enumeration of smaller-diameter trees only significantly reduces the computational complexity of combinatorial method. For example, of 1296 trees, built on 6 alternatives, there are only 6 trees of diameter 2 and 210 trees of diameter 3. This example is illustrated by Fig. 3.

Figure 3: Alternative weight calculated as GM across all spanning trees. 1 – ordinary GM;  unsorted  Straight line – true non‐perturbed value. 

In a conventional combinatorial method of spanning tree enumeration (EAST) the order of enumeration of spanning trees does not make a difference. At the same time, in order to sort the trees in the order of increasing diameter, we need to enumerate them in a specific order. First, we need to

For this purpose, we can utilize Prüfer sequences. Prüfer [ 17 ] invented a bijective mapping of a set of indices of an array ( 2 )-dimensional hypercubic array into a set of spanning trees.

It turns out that the diameter of a spanning tree equals the number of different indices in the respective Prüfer sequence plus 1. For instance, sequence (1,1,1) corresponds to a star-type graph with 5 nodes with node number 1 in the middle. Diameter of this graph equals 2, while the respective sequence features only the 1 node number (1). Sequence (2,3,4) corresponds to a path-type graph of 5 nodes: (1-2-3-4-5). This sequence features 3 different node numbers (2,3, and 4), and the diameter of the respective graph is 4. The respective spanning trees are shown on Fig. 4.

a b Figure 4: Spanning trees of 5 nodes, corresponding to Prüfer sequences (1,1,1) and (2,3,4). 

Moreover, the degree of each node in the spanning tree equals the number of times this node is featured in the respective sequence plus 1. For instance, for the sequence (1,1,1) we get a spanning tree, where the degree of the 1st node equals 4, while degrees of all other nodes equal 1.

These considerations significantly simplify the process of spanning tree sorting by diameter. 5. Completion  of  incomplete  PCM  based  on  small‐diameter  quasi(‐regular)  graphs 

The union of all spanning trees is the complete undirected incidence graph on vertices. It also corresponds to a complete PCM of dimensionality . Under large number of compared alternatives it makes sense to try to reduce the number of comparisons the expert has to perform.

Empirical research [ 13 ] shows that instead of complete incidence graph, we can take smallerdiameter quasi-regular graphs as patterns for preference structure. A regular graph with regularity value is a graph where all the nodes have the same degree , that is the same number of adjacent nodes . In a quasi-regular graph where exactly one node has the degree of 1 , while the degree of all other nodes equals .

Smaller diameter minimizes accumulated expert errors, while (quasi-)regularity condition ensures the stability of preference structure. Moreover, it turns out that on larger dimensionalities the completion ratio reduction of the PWC number an expert has to make in order to obtain credible priorities, becomes more significant on larger number of alternatives.

For example, Petersen graph (Fig. 5a) with completion ratio 0.333 turns out to be the only 3regular graph ( 3 ) with diameter 2 for 10 . And graph, shown on Fig. 5b, is the only quasiregular graph with 3 of diameter 2 for 5 .

The research [ 13 ] indicates, that incomplete PCMs, filled according to minimum-diameter quasiregular graphs, are more stable to perturbations (simulating expert errors) than PCMs, built according to other filling patterns (in terms of Euclidian and absolute distance).

Example on Fig. 6 shows the deviation of priorities calculated using LLSM method after strong perturbation of an initial PCM of 16 objects. 3-regular graph of diameter 3 yields the smallest deviation in terms of both Euclidian and absolute distance (red circle on the chart). also decreases. It means that Figure 5: (Quasi‐)regular graph examples  Figure 6: Deviations of priorities calculated using LLSM method after strong initial PCM perturbation  for n = 16; k = 3; d = 3  6. Mixed  approaches  based  on  both  PWC  patterns  and  initial  alternative  ranking 

Credibility and consistency of expert estimation results depend on calibration of estimates. In order to obtain every single PWC, the expert has to answer two questions: ordinal one (which of the two objects dominates over the other?) and cardinal one (how much better the object is? what is the degree of dominance?). So, preliminary calibration of estimates through ranking allows the expert to get at least some understanding of the range of differences and, if necessary, choose some object as a unit value. This can be the largest object, the smallest object, the “median”, or a random object from the given set.

If all objects are compared to the smallest and/or the largest one, these comparisons form star-type spanning trees. A well-known best/worst PWC method [ 7,8 ], as well as best/second best (TOP2) method [ 15 ], are based on the union of the two star-type graphs (if analyzed from graph perspective). If the two “pivotal” alternatives are the best and the worst one, then the graph interpretation of the PWC pattern might look as shown on Fig. 7. The size of the circles on the figure reflects the ranks of the respective objects.

Some recent research [ 15 ] (conducted so far on dimensionalities from 5. .10 ) speaks in favor of best-worst graphs (taking the ranking into consideration; worst in terms of Euclidean distance, best in terms of Kendall’s ; red circle on the figure) and union of two random spanning trees (not taking ranking into consideration; best in terms of Euclidean distance, worst in terms of Kendall’s ; rosy circle on the figure). TOP2 graphs (taking the ranking into consideration; blue triangle on the figure) seem to lie in between (Fig. 8).

Another approach to PWC methods, also taking alternative ranking into account is, suggested in [ 14 ]. It is based on the assumption that distortions in evaluation can be minimized if objects are presented to respondents from largest to smallest [ 18 ]. The largest PWC is the comparison of the 1st and the last object in the ranking (whose ranks differ by 1 ), while the smallest PWC is the comparison between the neighboring objects in the ranking (whose ranks differ by 1). The experiment described in [ 14 ] shows that results of expert session are more credible in the eyes of experts themselves, if the first comparison is made between the best object and the worst one (distance in the ranking between these two objects, ranked 1st and last, equals 1 ). After that the expert should compare the next-mostdistant objects in the ranking (1st and ( 1 )-th, and 2nd and -th; distance in the ranking between these objects, equals 2 ). The process continues until all neighboring objects in the ranking are compared. As a result, PWC form ( 1 ) turns or queues. First queues of PWC are more significant, so if we need to reduce the number of PWC (for example, on large ), then it is preferable to omit the last PWC 5 5 2 2 queues rather than the first ones. At the same time, we should make sure that the overall preference structure should form a connected graph, spanning all nodes (alternatives).

7 Figure 9: Minimum complete PWC set if comparisons are arranged in queues according to ranking (7  alternatives) 

For example, if we are estimating 7 alternatives (Fig. 9), then the 1st PWC queue will consist of a single PWC between the 1st and the 7th alternatives in the ranking; the 2nd queue will include comparisons between the 1st and 6th as well as 2nd and 7th alternatives; the 3rd queue – PWC between 1st and 5th, 2nd and 6th, 3rd and 7th; the 4th queue – PWC between 1st and 4th, 2nd and 5th, 3rd and 6th, 4th and 7th; etc. However, we should note that the set of PWC becomes connected at the start of the 4th queue, when the graph spans the 4th alternative (Fig. 9). So, technically, if we follow this particular order of PWC, it is sufficient to perform only 7 PWC instead of 21 PWC. Moreover, if we omit the comparison between 2nd and 6th alternatives during the 3rd queue (as the 6th alternative has already been compared with the 1st alternative during the 2nd queue), then we will get a spanning tree (Fig. 10). Figure 10: A spanning tree, obtained if comparisons are arranged in queues according to ranking, and  redundant comparisons are omitted (7 alternatives) 

In the general case of alternatives such a spanning tree will form a bi-partite graph, in which one part will be concentrated around the first (best) alternative, and another – around the last (worst) one. The first alternative will be connected (compared) to alternatives with numbers from /2 1 to . The last alternative will be connected (compared) to alternatives with numbers from 1 to /2 . These will be the basic 1 comparisons.

These considerations provide the starting point for development of an algorithm of reduction of the number of PWC [ 15 ] needed to ensure maximum credibility and consistency of the PWC session results.

Moreover, they stand in line with the respective research [ 19 ], showing that sufficient redundancy of PWC set is achieved on smaller number of comparisons (lying between the minimum of 1 PWC and the maximum of

PWC. In fact, at some point, addition of new comparisons reduces the consistency level of the whole PWC set. The author of [ 19 ] also proposes to perform rough ranking of alternatives before inputting PWC between them.

Some might argue that ranking of alternatives makes the expert perform additional ordinal comparisons. However, ordinal questions are posed to the expert in any case. That is, he has to answer from 1 to ordinal questions (such as “which alternative is the best one?”; “which one is the best among remaining ones?”; “which alternative of the two is better than the other?”) within any PWC method. In fact, some earlier research by the authors of this paper ([ 20 ], [ 21 ]), was dedicated to development of methods for calculation of weight vectors based on rankings only.

So, again, reduction of the number of PWC both reduces computational complexity of aggregation process and improves the consistency of comparison results.

Finding optimal PWC patterns for the case when PWC are arranged in queues is going to be the subject of a separate future research.

7. Conclusions 

Graph representation of PWC structures in decision-making problems is an efficient tool. It allows to reduce computational complexity of decision-making problems and the number of PWC experts need to perform in order to obtain credible results.

Graphs with smaller diameter tend to accumulate smaller expert estimation errors, while regular graphs help an expert session organizer to maintain stability of preference structures and patterns on a set of objects.

Patterns of spanning tree enumeration and incomplete PCM filling can depend on respective incidence graph structure and initial rough ranking of alternatives.

Future research on the subject will be dedicated to finding the best PWC patterns (in terms of different cardinal and ordinal indicators), both taking and not taking the initial ranking of alternatives into account.

Particularly, it makes sense to study the behavior of various consistency indices (C.R. and others), depending on the number of PWC, performed according to specific incomplete PCM filling-in patterns.

References 

References

[1] T. Saaty , The Analytic Hierarchy Process . McGraw-Hill , New York, 1980 .

[2] T. Saaty , Decision Making with Dependence and Feedback: The analytic Network Process . RWS Publicaitons , Pittsburgh, 1996 .

[3] V. Tsyganok , S. , Kadenko , O. Andiichuk , Using different pair-wise comparison scales for developing industrial strategies , International Journal of Management and Decision Making , 14 ( 3 ) ( 2015 ), 224 - 250 , doi:10.1504/IJMDM. 2015 . 070760 .

[4] M. Oliveira Ramos , E. M. da Silva , F. Rodrigues Lima-Júnior , A fuzzy AHP approach to select suppliers in the Brazilian food supply chain , Production , vol. 30 , e20200013 ( 2020 ). doi: 10 .1590/ 0103 - 6513 . 20200013 .

[5] F. De Felice (Ed.), Applications and Theory of Analytic Hierarchy Process. Decision Making for Strategic Decisions , IntechOpen, 2016 .

[6] C.L. Hwang and K. Yoon , Multiple attribute decision making: methods and applications: a stateof-the-art survey . Berlin, New York: Springer-Verlag, 1981 .

[7] J. Rezaei , Best-worst multi-criteria decision-making method . Omega , 53 , ( 2015 ), 49 - 57 , doi: 10.1016/j.omega. 2014 . 11 .009.

[8] J. Rezaei , Best-worst multi-criteria decision-making method: Some properties and a linear model , Omega , 64 , ( 2016 ), 126 - 130 , doi: 10.1016/j.omega. 2015 . 12 .001.

[9] M. Lundy , S. Siraj , S. Greco , The Mathematical Equivalence of the “Spanning Tree” and Row Geometric Mean Preference Vectors and its Implications for Preference Analysis , European Journal of Operational Research 257 ( 1 ), ( 2017 ), 197 - 208 . doi: 10 .1016/j.ejor. 2016 . 07 .042.

[10] V. Tsyganok , S. Kadenko , O. Andriichuk , P. Roik , Combinatorial Method for Aggregation of Incomplete Group Judgments, in: Proceedings of 2018 IEEE 1st International Conference on System Analysis & Intelligent Computing (SAIC) , 2018 , pp. 25 - 30 . doi: 10 .1109/SAIC. 2018 . 8516768 .

[11] S. Bozóki , V. Tsyganok , The (logarithmic) least squares optimality of the arithmetic (geo-metric) mean of weight vectors calculated from all spanning trees for incomplete additive (multiplicative) pairwise comparison matrices . International Journal of General Systems 48 ( 4 ), ( 2019 ), 362 - 381 . doi: 10 .1080/03081079. 2019 .1585432

[12] S. Kadenko , V. Tsyganok , S. Szádoczki , S. Bozóki , An update on combinatorial method for aggregation of expert judgments in AHP . Production, 31 , ( 2021 ) doi: 10.1590/ 0103 - 6513 . 20210045 .

[13] Z. Szádoczki , S. Bozóki , H. Tekile , Filling in pattern designs for incomplete pairwise comparison matrices:(quasi-) regular graphs with minimal diameter . Omega , 107 , ( 2022 ), doi: 10.1016/j.omega. 2021 . 102557 .

[14] O. Andriichuk , V. Tsyganok , S. Kadenko , Y. Porplenko , Experimental Research of Impact of Order of Pairwise Alternative Comparisons upon Credibility of Expert Session Results , in: Proceedings of the 2020 IEEE 2nd International Conference on System Analysis & Intelligent Computing (SAIC) , 2020 , pp. 1 - 5 , doi: 10.1109/SAIC51296. 2020 . 9239126 .

[15] P. Juhász , S. Bozóki , Z. Szádoczki , S. Kadenko , V. Tsyganok , Nem teljesen kitöltött páros összehasonlítás mátrixok kitöltési mintázatainak vizsgálata , in: XXXIV. Magyar Operációkutatási Konferencia 2021 . 08 .31.- 2021 . 09 .02, ( 2021 ), URL: https://www.gazdasagmodellezes.hu/images /stories/konferenciak/GMT2021/MOK_absztraktok.pdf.

[16] Arthur Cayley , A Theorem on Trees . Quarterly Journal of Mathematics , 23 ( 1889 ): 376 - 378 .

[17] H. Prüfer , Neuer Beweis eines Satzes über Permutationen . Arch. Math. Phys. , 27 , ( 1918 ) 742 - 744 .

[18] Stanley Smith Stevens , Eugene Galanter, Ratio Scales and Category Scales for a Dozen Perceptual Continua , Journal of Experimental Psychology , Vol. 54 , No 6, 1957 : 377 - 411 .

[19] W.C. Wedley , Fewer Comparisons - Efficiency via Sufficient Redundancy, in: Proceedings of the 10th International Symposium on the Analytic Hierarchy/Network Process, Multi-criteria Decision Making, Pitsburg , Pensilvania, USA, July 30 - August 2 , 2009 , ( 2009 ). URL: https://citeseerx.ist.psu.edu/viewdoc/download?doi =10.1.1.553.2890&rep=rep1&type=pdf.

[20] S. Kadenko , Defining the relative weights of alternative estimation criteria based on clear and fuzzy rankings . Journal of Automation and Information Sciences , 45 ( 2 ), 41 - 49 ( 2013 ), DOI: 10.1615/JAutomatInfScien.v45. i2 . 50 .

[21] S. Kadenko , Determination of parameters of criteria of “tree” type hierarchy on the basis of ordinal estimates . Journal of Automation and Information Sciences , 40 ( 8 ), 7 - 15 ( 2008 ), DOI: 10.1615/JAutomatInfScien.v40. i8 . 20 .