5.1 Problem Statement

Given:

a ₁ ,   a ₂ , ..., a _n are alternatives , n is the number of alternatives,

P ₁ , P ₂ , ... P _m - individual rankings of alternatives by experts, m - the number of experts.

Rankings have the form where

- the alternative that ranks first in the P ₁ ranking,

- alternative, standing on the n- th place in the ranking of P ₁ .

Alternative has rank 1, alternative has rank n .

Required to find: final ranking P * , taking into account the opinion of all experts.

5.2 Majority rule

According to the majority rule, the number of experts who preferred each of the alternatives is calculated, and the best alternative is announced, which the best experts called the best. Let considered 5 alternatives. Their ranking, corresponding to the opinion of 10 experts, is presented in Table. 5.1:

Table 5.1

An example of ranking alternatives by experts

In this case, according to the majority rule, the alternative A 1 will be better, since it was called the best 3 experts (for the remaining alternatives, this number is less than or equal to 2). However, the same alternative was recognized as the worst by 7 out of 10 experts. So the recognition of the alternative A 1 best is debatable. To eliminate such shortcomings introduce additional requirements. For example, only the alternative that is considered better by at least half of the experts can become better. Under such conditions, there may not be a better alternative at all.

5.3 Condorcet Principle

Condorcet was offered the following case to determine the best alternative. Each expert ranks the alternatives by preference. Based on the obtained rankings for each pair of alternatives, A _i and A _j are calculated   S _ij is the number of experts who consider A _{i to be} more preferable than A _j . If S _ij > S _ji , then the alternative A _{i is} considered more preferable than A _j . The best alternative is declared A _i if S _ij > S _ji for all i ≠ j . In this case, the alternative to Condorcet is the alternative to A 2 . However, using the Condorcet principle, a paradox may arise that is a consequence of the intransitivity of collective relations. If the three experts ranked the alternatives A 1, A2, A3 as follows:

A1 A3 A2

A2 A1 A3

A3 A2 A1

then S ₁₂ > S ₂₁ , S ₂₃ > S ₃₂ , S ₃₁ > S ₁₃ . There is no alternative to Condorcet.

5.4 Borda method

The Borda method is based on ordering alternatives based on the sum of ranks assigned to alternatives by experts [6, p. 62]. The alternatives ranked by the experts are assigned the number: the last one by preference - 0, the penultimate one - 1, etc. The method consists of 2 stages:

1. At the first stage, for each object with number k , the value of S _k is determined, equal to the sum of ranks assigned to the object by all experts:

;

2. at the second stage, the object's rank is determined - the larger the value of S _k , the higher the place of the alternative in the sought ranking.

An example of constructing a final ranking using the method of bord

Let there be alternatives a ₁ ,   a ₂ ,   a ₃ , a ₄ and the ranking of these alternatives by experts (Table 5.2). Required to find the final ranking.

Table 5.2

Ranking criteria by experts

Denote the R ₁ ranks obtained on the basis of alternative rankings by experts,   R2 ,   R ₃ ,   R _{4. The} process of constructing the final ranking using the Bord method is presented in Table. 5.3.

Table 5.3

Building a final ranking

5.5 Kemeny Median Search Method

The Kemeny median search method allows finding the final ranking P , the total distance from which to all given rankings is minimal:

,

where m is the number of experts, P ₁ , ..., P _m are the rankings, d (P, P _u ) is the distance between the rankings [6, p. 73].

Thus, to search for a median, it is necessary to introduce the concept of the distance between rankings . It is defined using the relationship matrix. , , , n is the number of alternatives.

r _i , r _j are the ranks of the i -th and j -th alternatives in the ranking of the hth expert. Note that alternative ranks are compared the other way round, that is, the rank is r _i = 1> r _j = 2 (rank 1 is greater than rank 2 ) and r _i = 5 < r _j = 3 (rank 5 is less than rank 3 ).

Distance from arbitrary ranking P , which corresponds to the matrix, to all rankings P ₁ , P ₂ , ..., P _m , which correspond to the matrix of pair relations , ..., is determined by the formula:

.

To find the Kemeny median, a loss matrix is introduced. , .

,

where P is the ranking, the element of the matrix of relations p _ij is equal to 1 .

At the same time, the task of finding the Kemeny median for rankings is formulated as the task of finding such an ordering of alternatives, and therefore rows and columns of the loss matrix, so that the sum of its elements located above the diagonal is minimal.

Kemeny median heuristic search algorithm

Suppose that for the initial rankings the loss matrix is ​​defined. The search process for the final ranking consists of 2 stages.

At the first stage, a preliminary ranking of P _{I is built} .

1st iteration . Calculate the sum of the elements of the rows of the loss matrix:

.

Find the minimum of them. .

Alternative a _i1 , put in first place in the desired ranking. Striking out in row and column with number i ₁ , we get a matrix, the set of indices of rows and columns, respectively, I ⁽¹⁾ = J ⁽¹⁾ = {1, ..., n } \ I ₁ .

kth iteration . In the loss matrix calculate the sum of the elements of the lines:

.

Find the minimum of them:

.

Alternative a _ik , put on the k - th place in the desired ordering. Striking out in row and column with number i _k , we get the matrix , the set of indices of rows and columns, respectively, I ^{( k )} = J ^{( k )} = {1, ..., n } \ { i ₁ , ..., i _k } .

The algorithm terminates after the nth iteration ( I ^{( k )} = J ^{( k )} and is equal to the empty set). Sought ordering

In the second stage of the found ranking P _I   get the final ranking of P _II , with the process of transition from ranking P _I to ranking P _II   happens as follows: for the ranking elements P _{I, we} successively verify the validity of relations (1)

(5.1)

Once for some k   it is broken, the alternatives a _ik and a _{ik +1} in the ranking are interchanged, and we check the relation (5.1), starting with the alternative immediately preceding the alternative subjected to the permutation. After a finite number of steps, a P _II ranking will be obtained.

An example of constructing a final ranking using the Kemeny median search method

Consider the process of constructing the final ranking on the example discussed earlier (the initial data are presented in Table 5.2).

1. Build a matrix of relations for the ranking of experts:

	0	-one	-one	-one		0	-one	-one	-one
	one	0	-one	one		one	0	one	one
	one	one	0	one		one	-one	0	one
	one	-one	-one	0		one	-one	-one	0
	0	one	one	one		0	0	-one	-one
	-one	0	-one	-one		0	0	-one	-one
	-one	one	0	0		one	one	0	-one
	-one	one	0	0		one	one	one	0

For example, p ₁₂ ⁽¹⁾ = -1 , since r ₁ < r ₂ ( r ₁ = 3, r ₂ = 1 ), p ₃₄ ⁽²⁾ = 0 , because r ₃ = r ₄ ( r ₃ = 2 r ₄ = 2 ).

2. The loss matrix has the following form:

For example, r ₁₂ = d ₁₂ ( P ₁ , P ₃ ) + d ₁₂ ( P ₂ , P ₃ ) + d ₁₂ ( P ₄ , P ₃ ) , since P ₃ is a ranking, the element of the relationship matrix is p ₁₂ ^{(3 )} = 1 . Then r ₁₂ = | p ₁₂ ⁽³⁾ - p ₁₂ ⁽¹⁾ | + | p ₁₂ ⁽²⁾ - p ₁₂ ⁽³⁾ | + | p ₁₂ ⁽³⁾ - p ₁₂ ⁽⁴⁾ | = | 1 - (- 1) | + | 1 - (- 1) | + | 1-0 | = 5 .

3. Find a preliminary ranking of P _I   ( first stage ).

1st iteration . Calculate

The minimum is reached at S ₃ ⁽¹⁾ . In first place in the ranking P _I   alternative a ₃ is placed, and it is excluded from further consideration.

2nd iteration . Calculate

The minimum is reached at S ₄ ⁽²⁾ . The second place in the P _I ranking is the alternative to a ₄ , and it is excluded from further consideration.

3rd iteration . Calculate

The minimum is reached on S ₂ ⁽³⁾ . The third place in the P _I ranking is the alternative to a ₂ , and it is excluded from further consideration. Thus, the P _I ranking is as follows:

4. Find the P _II ranking ( second stage ).

So, i ₁ = 3, i ₂ = 4, i ₃ = 2, i ₄ = 1. Compare and or r ₂₁   and r ₁₂ , Since r ₂₁ ≤ r ₁₂ ( 3 ≤ 5 ), the alternatives are not interchanged, go to the comparison of r ₄₂ and r ₂₄ . Since r ₄₂ ≤ r ₂₄ ( 4 ≤ 4 ) , we turn to the comparison of r ₃₄ and r ₄₃ .   Since r ₃₄ < r ₄₃   ( 3 ≤ 5 ), then the found ranking

and is a P _II ranking for which relations (5.1) are satisfied.

The final rankings of alternatives by the Board method and the Kemeny median search method are presented in Table. 5.5.

Table 5.5

The results of the construction of the final ranking using the method of the Board and the method of searching for the Kemeny median

The results of the work of the methods described above can sometimes vary quite strongly. The Borda method gives results that are intuitive, since it is based on the idea of ​​averaging estimates. As for the method of searching for the Kemeny median, then, on the contrary, it can give unexpected results. To obtain the final ranking, the method uses a special estimate — the distance between the rankings. And the algorithm for obtaining the final ranking considered by us is based on heuristics — the assumption that the final ranking constructed in this way will be closest to the opinion of all experts from the point of view of the estimate introduced.