arXiv:1503.04003v3 [math.OC] 28 Aug 2016

Using Tropical Optimization Techniques to
Evaluate Alternatives via Pairwise Comparisons∗
N. Krivulin†

Abstract
We describe a new approach based on tropical optimization techniques to solve the problem of rating alternatives from pairwise comparison data. The problem is formulated to approximate, in the logChebyshev sense, pairwise comparison matrices by reciprocal matrices
of unit rank, and then represented in general terms of tropical mathematics as a tropical optimization problem. The optimization problem
takes a common, unified form for both multiplicative and additive comparison scales. We apply recent results in tropical optimization to offer
new complete solutions to the rating problems under various assumptions about the pairwise comparison matrices. The solutions are given
in a compact vector form, which extends known solutions and involves
modest computational efforts. The results obtained are illustrated with
numerical examples. Specifically, we show by example that the partial
solution known before may miss better results provided by the new
complete solution. An example to demonstrate a tropical analogue of
the analytical hierarchy process decision scheme is also given.
Key-Words: idempotent semifield, tropical optimization, matrix
approximation, pairwise comparison, consistent matrix.
MSC (2010): 65K10, 15A80, 65K05, 41A50, 90B50

1

Introduction

Tropical optimization problems present an important research and application domain of tropical mathematics, which finds use in solving real-world
problems in various fields, including project scheduling, location analysis
and decision making. Tropical (idempotent) mathematics deals with the
theory and application of semirings with idempotent addition, and dates
∗
This work was supported in part by the Russian Foundation for Humanities (grant
No. 16-02-00059).
†
St. Petersburg State University, Universitetskaya nab. 7/9, St. Petersburg, 199034,
Russia, nkk@math.spbu.ru.

1

back to a few influential works by Pandit [25], Cuninghame-Green [3], Giffler [9], Hoffman [15], Vorob’ev [32], and Romanovskiı̆ [26], appeared in the
early 1960s.
In later decades, a large body of literature was published on various aspects of tropical mathematics, including recent monographs by Kolokoltsov
and Maslov [17], Golan [10], Heidergott et al. [14], Itenberg et. al [16],
Gondran and Minoux [11], McEneaney [24], and Maclagan and Sturmfels
[23], as well as numerous research and applied papers. Many studies, such as
the early papers [3, 15], were motivated and illustrated by extremal problems
drawn from operations research, computer science, and other areas. A noticeable part of these problems can be directly formulated and solved within
the framework of tropical mathematics as tropical optimization problems.
Tropical optimization problems are usually formulated to minimize or
maximize a function defined on vectors over an idempotent semifield (a
semiring with multiplicative inverses), with or without constraints on the
feasible solutions. The objective function can be either linear or nonlinear;
the nonlinear objective functions are typically defined through multiplicative
conjugate transposition of vectors. The constraints take the form of linear
vector equations and inequalities. Some of the problems are completely
solved under quite general assumptions in a closed compact vector form,
whereas the other problems have solutions available only in the form of
a numerical algorithm, which produces a partial solution if any exists, or
indicates the infeasibility of the problem. For further details and references,
one can consult, for instance, the overviews by Krivulin [19, 21].
One of the application areas, where tropical optimization can be of service, is the analysis of preferences based on pairwise comparison data in
decision making. Given a matrix that contains the result of pairwise comparisons of alternatives, the problem of interest is to rate (judge, score) the
alternatives. The problem arises in various contexts (see the classical works
by Thurstone [30], Saaty [27], and David [4] to list a few). In the tropical
mathematics setting, the problem is examined in the papers by Elsner and
van den Driessche [5, 6], Tran [31], and Gursoy et al. [13], where a solution
is proposed to calculate a tropical eigenvector of the matrix as the vector
of final scores assigned to the alternatives. The solution is used in [13] as
an alternative calculation technique for the Analytical Hierarchy Process
(AHP) decision scheme [27].
New general methods of tropical optimization were recently developed
by Krivulin in [18, 20, 21] to provide a useful framework for solving many
optimization problems, including the above problem of rating alternatives in
decision making [22]. The methods offer direct solutions in a closed vector
form, which is suitable for further analysis and practical application.
The purpose of this paper is to describe a new approach based on tropical optimization techniques to solve the problem of rating alternatives from
pairwise comparisons. We formulate the problem to approximate, in log2

Chebyshev sense, pairwise comparison matrices by reciprocal matrices of
unit rank, and then represent the problem in general terms of tropical mathematics as a tropical optimization problem. The optimization problem takes
a common, unified form for both multiplicative and additive comparison
scales.
We apply recent results in tropical optimization to offer new complete
solutions to the rating problems under various assumptions about the pairwise comparison matrices. The solutions are given in a compact vector form,
which extends known solutions and involves modest computational efforts.
The results obtained are illustrated with numerical examples. We show by
example that the partial solution, which was known before, may miss better
results provided by the new complete solution. An example to demonstrate
a tropical analogue of the AHP decision scheme is also given.
The paper is organized as follows. Section 2 outlines the method of ranking alternatives from their pairwise comparisons as a starting point for the
subsequent discussion. Furthermore, in Section 3, we offer a brief overview
of preliminary definitions, notation and results of tropical mathematics to
provide an analytical framework for the development of new solutions. In
Section 4, the problems of approximating square matrices by reciprocal matrices of unit rank are solved as tropical optimization problems. Section 5
uses results of the previous section to derive the vector of final scores from
pairwise comparison data. Finally, Section 6 demonstrates various examples
of solving problems to evaluate the scores of alternatives.

2

Pairwise Comparison Judgments

The method of pairwise comparisons is widely accepted in decision making to
estimate preferences when a direct evaluation of the preferences is impossible
or infeasible. Given a set of alternatives, the method uses the result of
pairwise comparisons with an appropriate scale to make judgment on the
relative preference of each alternative by evaluating its individual score or
rating (see, e.g., [30, 27, 4, 28] for further details).

2.1

Pairwise Comparison Matrices

The results of comparing the alternatives in pairs on a multiplicative or additive scale are described by pairwise comparison matrices that have a specific
form. Consider a pairwise comparison matrix A = (aij ) obtained with a
multiplicative scale. The entry aij of the matrix shows that alternative i
is preferred to alternative j by aij times. The multiplicative comparison
matrix is symmetrically reciprocal, which means that it has only positive
entries satisfying the condition
aij = 1/aji .
3

If an additive scale is used, the matrix A has the skew-symmetric form
with the entries, which compare preferences in terms of differences, and fit
the equality
aij = −aji .
In practice, however, multiplicative (additive) pairwise comparison matrices can have a form that differs from the symmetrically reciprocal (skewsymmetric) form, due to inexact or incorrect measurements.
To provide consistency of and to avoid confusion in the data given by
pairwise comparison matrices, these data must be transitive, which requires
that the entries of the multiplicative (additive) comparison matrix satisfy
the equality
aij = aik akj
(aij = aik + akj ).
If a pairwise comparison matrix has only transitive entries, it is called
consistent. For each multiplicative (additive) consistent matrix A = (aij ),
there is a positive (real) vector x = (xi ) whose elements completely determine the entries of A as follows:
aij = xi /xj

(aij = xi − xj ).

Finally, provided that a matrix A is consistent, its corresponding vector
x is considered to represent directly (up to a positive factor) the individual
scores of alternatives, and thus offers a solution to the problem of analysis
of preference in question.

2.2

Approximation by Consistent Matrices

The pairwise comparison matrices encountered in real-world applications
are generally inconsistent, which can be caused by various reasons from
limitations in human judgment to errors in the source data. Therefore, the
problem of approximating a pairwise comparison matrix A by a consistent
matrix arises in the general form
minimize d(A, X),

(1)

where the minimum is taken over all consistent matrices X , and d is a
suitable measure of approximation error.
Note that any consistent matrix X is uniquely determined, up to a positive factor, by a single vector x, and hence the solution of problem (1)
is equivalent to finding x. Since, in the context of the analysis of preference, the vector x presents the overall individual scores of alternatives,
the problem of evaluating the scores is reduced to the above approximation
problem.
To solve problem (1) for a pairwise comparison matrix, several approaches are used, which include approximation with the principal eigenvector of the matrix [27, 29], least squares approximation [29, 2] and other
4

approximation techniques [1, 7, 12, 8]. These approaches normally provide
algorithmic solutions in the form of numerical procedures, such as the power
iterations in the principal eigenvector method, and the Newton algorithm
in the least squares approximation.
Another solution approach, based on the application of tropical mathematics, is proposed and investigated in [5, 6, 31, 13]. This approach consists
of approximating the pairwise comparison matrix by a consistent matrix defined by a tropical eigenvector, and hence constitutes a tropical counterpart
of the conventional principal eigenvector method. Moreover, the analysis in
[6] shows that the approximate consistent matrices, which solve the problem
in the tropical mathematics setting, can be provided not only by tropical
eigenvectors, but by other vectors as well. As one of the results of [6], a
technique to find new solutions is proposed, which, however, offers a computational algorithm, rather than gives a direct solution in an explicit form.
In subsequent sections, we formulate the problem of finding approximate
consistent matrices as a general problem of approximation by reciprocal
matrices of rank one in the topical mathematics setting. It is shown that
the problem can be considered as matrix approximation in the Chebyshev
or Chebyshev-like metrics. We apply recent results in tropical optimization
to offer complete, direct solutions of the approximation problems.

3

Basic Definitions, Notation and Results

In this section, we follow the presentation given in [18, 19, 20, 21] to outline
preliminary definitions and results of tropical mathematics, which offer an
analytical framework to the solutions in the subsequent sections. For further
details and discussion, one can consult recent publications [17, 10, 14, 16,
11, 24, 23].

3.1

Idempotent Semifield

Let X be a carrier set that is equipped with binary operations ⊕ and ⊗,
called addition and multiplication, which have neutral elements 0 and 1,
called the zero and identity. Both operations are associative and commutative, and multiplication is distributive over addition. Addition is idempotent, resulting in the equality x ⊕ x = x for all x ∈ X. Moreover, multiplication is invertible, implying that each nonzero x ∈ X has its inverse
x−1 such that x ⊗ x−1 = 1. Together with these operations, the carrier set
X forms the algebraic system (X, ⊕, ⊗, 0, 1), which is usually referred to as
the idempotent semifield.
The semifield is considered linearly ordered by an order that is consistent
with the partial order produced by idempotent addition to define x ≤ y if
and only if x⊕y = y . In addition, the semifield is assumed to be algebraically
complete, which means that the equation xp = a, where xp denotes the
5

iterated product, has solutions for any a ∈ X and integer p > 0, and thus
the powers with rational exponents are well-defined.
In the algebraic expressions below, the multiplication sign ⊗, as usual,
is omitted for the sake of brevity. The power notation is always understood
in the sense of tropical mathematics.
Examples of the idempotent semifield under consideration include
Rmax,× = (R+ ∪ {0}, max, ×, 0, 1),
Rmax,+ = (R ∪ {−∞}, max, +, −∞, 0),
where R is the set of reals, and R+ = {x ∈ R|x > 0}.
The semifield Rmax,× is equipped with the addition ⊕ defined as maximum, and the multiplication ⊗ defined as usual. The neutral elements 0
and 1 coincide with the arithmetic zero and one, respectively. The power
and inversion notations have the usual meaning.
The semifield Rmax,+ involves ⊕ = max , ⊗ = +, 0 = −∞ and 1 = 0.
For each x ∈ R, the inverse x−1 coincides with the conventional opposite
number −x. The power notation xy , where x, y ∈ R, corresponds to the
regular arithmetic product xy .
In both semifields, the order induced by idempotent addition corresponds
to the natural linear order on R.

3.2

Vector and Matrix Algebra

The column vectors with n elements over X form the set Xn . A vector
with all elements equal to 0 is the zero vector denoted 0. A vector is called
regular if it has no zero elements.
Vector addition and scalar multiplication follow the usual element-wise
rules, where the scalar operations ⊕ and ⊗ act as the standard addition
and multiplication.
A vector b is said to be linearly dependent on vectors a1 , . . . , am if there
are scalars x1 , . . . , xm such that b = x1 a1 ⊕ · · · ⊕ xm am . Vectors a and b
are collinear if b = xa for some x.
The system of vectors a1 , . . . , am is called linearly dependent if at least
one of the vectors is dependent on others, and independent otherwise. The
set of linear combinations x1 a1 ⊕ · · · ⊕ xm am for all x1 , . . . , xm is closed
under vector addition and scalar multiplication, and is referred to as the
idempotent vector space generated by the system.
The multiplicative conjugate transpose of a nonzero column vector x =
−
−1
(xi ) is a row vector x− = (x−
if xi 6= 0, and
i ) with the elements xi = xi
−
xi = 0 otherwise.
The set of matrices with m rows and n columns is denoted by Xm×n .
A matrix with all zero entries is the zero matrix. Matrix addition, matrix

6

multiplication and scalar multiplication are given by the conventional entrywise formulae, where the operations ⊕ and ⊗ play the role of the usual
addition and multiplication.
Consider a matrix A ∈ Xm×n . The transpose of A is the matrix denoted
by AT ∈ Xn×m . The multiplicative conjugate transpose of any nonzero
−1
−
matrix A = (aij ) is the matrix A− = (a−
ij ) with the entries aij = aji if
aji 6= 0, and a−
ij = 0 otherwise.
The rank of a matrix is defined as the maximum number of linearly
independent columns (rows) in the matrix. A matrix A has rank 1 if and
only if A = xy T , where x and y are regular column vectors.
Consider the square matrices of order n in the set Xn×n . A matrix that
has 1 along the diagonal and 0 elsewhere is the identity matrix denoted I .
The power notation indicates iterated products as A0 = I and Ap = Ap−1 A
for any matrix A and integer p > 0.
A matrix A that satisfies the condition A− = A is called symmetrically
reciprocal (or, simply, reciprocal). A reciprocal matrix A is of unit rank if
and only if A = xx− , where x is a regular column vector.
The trace of a matrix A = (aij ) ∈ Xn×n is given by
tr A = a11 ⊕ · · · ⊕ ann .
For any matrices A and B , and scalar x, the following equalities hold:
tr(A ⊕ B) = tr A ⊕ tr B,

tr(AB) = tr(BA),

tr(xA) = x tr A.

3.3

Distance Functions

The distance between two regular vectors x, y ∈ Xn is defined by the function
d(x, y) = y − x ⊕ x− y,
which attains the minimum value 1 when y = x.
In the semifield Rmax,+ , this function has the minimum 1 = 0 and
coincides with the Chebyshev metric
d∞ (x, y) = max |xi − yi |.
1≤i≤n

For Rmax,× , the function d becomes a Chebyshev distance in the log-log
scale after taking the logarithm,
d′∞ (x, y) = log d(x, y) = max | log xi − log yi |.
1≤i≤n

In the general case, the function d is called the Chebyshev-like distance.

7

For two matrices A, B ∈ Xn×n without zero entries, the Chebyshev-like
distance function is given by
d(A, B) = tr(B − A) ⊕ tr(A− B),

(2)

which takes the form of the Chebyshev metric in the semifield Rmax,+ , and
of a log-Chebyshev distance after logarithmic transformation in Rmax,× .

3.4

Eigenvalues and Eigenvectors of Matrices

A scalar λ ∈ X is an eigenvalue of a matrix A ∈ Xn×n if there exists a
nonzero vector x ∈ Xn such that the equality Ax = λx holds. The vector
x, which satisfies the equality, is an eigenvector of A, corresponding to λ.
The maximum eigenvalue of a matrix A = (aij ) is called the spectral
radius of A, and calculated as
λ = tr A ⊕ · · · ⊕ tr1/n (An ),
or, in terms of the entries of the matrix A, as
λ=

n
M

M

(ai1 i2 ai2 i3 · · · aik i1 )1/k .

(3)

k=1 1≤i1 ,...,ik ≤n

Any matrix A with nonzero entries has only one eigenvalue, which coincides with the spectral radius λ given by the above expressions. The
eigenvectors of A, which correspond to λ, are derived as follows. Calculate
the matrix Aλ = λ−1 A, and then find the matrices
A∗λ = I ⊕ Aλ ⊕ · · · ⊕ Aλn−1 ,
+
∗
and A×
λ = Aλ Aλ . Finally, the matrix Aλ is formed by taking those
∗
columns that coincide in both matrices Aλ and A×
λ . All eigenvectors of
the matrix A are given by
x = A+
λ u,

where u is any nonzero vector, and hence constitute an idempotent vector
space spanned by the columns in A+
λ.

3.5

Tropical Optimization Problem

Consider the following optimization problem in the tropical mathematics
setting: given a matrix A ∈ Xn×n , find regular vectors x = (xj ) ∈ Xn that
minimize

x− Ax,

subject to xj > 0,

j = 1, . . . , n.

(4)

The next complete, direct solution to the problem is obtained using
various arguments in [18, 20, 21].
8

Lemma 1. Let A be a matrix with spectral radius λ > 0, and Aλ = λ−1 A.
Then, the minimum value in problem (4) is equal to λ, and all regular
solutions are given by
u 6= 0.
x = A∗λ u,
From Lemma 1 it follows that the solutions (together with the zero
vector) form an idempotent vector space generated by the columns of the
matrix A∗λ .

4

Matrix Approximation Problems

In this section, we examine problems of approximating square matrices by
reciprocal matrices of unit rank. The problems are formulated in terms of
tropical mathematics, and then solved as tropical optimization problems.
Let A ∈ Xn×n be a matrix. Consider the approximation problem to find
regular vectors x = (xj ) ∈ Xn that
minimize

d(A, xx− ),

subject to xj > 0,

j = 1, . . . , n;

(5)

where d is the Chebyshev-like distance function (2), which is taken as a
measure of approximation error.

4.1

Approximation of One Matrix

We start with approximating a matrix that may not be reciprocal.
Theorem 2. Let A be a matrix such that the matrix B = A ⊕ A− has no
zero entries, µ be the spectral radius of B , and Bµ = µ−1 B . Then, the
minimum value in problem (5) is equal to µ, and all solutions are given by
x = Bµ∗ u,

u 6= 0.

Proof. Considering (xx− )− = xx− , we use properties of the trace to write
the objective function in (5) as
d(A, xx− ) = tr((xx− )− A) ⊕ tr(A− xx− ) = x− Ax ⊕ x− A− x = x− Bx.
Since the matrix B has no zero entries, it follows from (3) that B has
the spectral radius µ 6= 0. Therefore, we can define the matrix Bµ = µ−1 B ,
and then apply Lemma 1 to obtain the solution.
Suppose that the matrix A is reciprocal. Then, we have A− = A, and
the theorem reduces to the following result, which closely reproduces that
of Lemma 1.
Corollary 3. Let A be a reciprocal matrix with spectral radius λ, and
Aλ = λ−1 A. Then, the minimum in (5) is equal to λ, and all solutions are
given by
u 6= 0.
x = A∗λ u,
9

4.2

Approximation of Several Matrices

We now suppose that there are m matrices A1 , . . . , Am ∈ Xn×n to determine a reciprocal matrix of rank 1 that approximates these matrices
simultaneously. The approximation problem can be formulated in the form
minimize

max d(Ai , xx− ),

1≤i≤m

subject to xj > 0,

(6)

j = 1, . . . , n.

For nonreciprocal matrices, a solution is as follows.
Theorem 4. Let Ai be matrices for i = 1, . . . , m, such that the matrix
−
B = A1 ⊕ A−
1 ⊕ · · · ⊕ Am ⊕ Am has no zero entries, µ be the spectral radius
−1
of B , and Bµ = µ B . Then, the minimum value in problem (6) is equal
to µ, and all solutions are given by
x = Bµ∗ u,

u 6= 0.

Proof. For each i = 1, . . . , m, the same argument as in Theorem 2 yields
d(Ai , xx− ) = x− (Ai ⊕ A−
i )x. We replace max by ⊕, and rewrite the
objective function as
max d(Ai , xx− ) = x−

1≤i≤m

m
M
−
(Ai ⊕ A−
i )x = x Bx.
i=1

An application of Lemma 1 to the problem with the new objective function completes the proof.
If the matrices A1 , . . . , Am are reciprocal, the statement of Theorem 4
is valid in the next reduced form.
Corollary 5. Let Ai be reciprocal matrices for i = 1, . . . , m, the matrix
B = A1 ⊕ · · · ⊕ Am have spectral radius µ, and Bµ = µ−1 B . Then, the
minimum in (6) is equal to µ, and all solutions are given by
x = Bµ∗ u,

4.3

u 6= 0.

Weighted Approximation of Matrices

Let A1 , . . . , Am ∈ Xn×n be matrices and w1 , . . . , wm ∈ X be scalars. We
consider these scalars as weights to write the problem of weighted approximation in the form
minimize

max wi d(Ai , xx− ),

1≤i≤m

subject to xj > 0,

(7)

j = 1, . . . , n.

The next result provides a solution to the problem in the general case of
nonreciprocal matrices.
10

Theorem 6. Let Ai be matrices for i = 1, . . . , m, such that the matrix
−
B = w1 (A1 ⊕A−
1 )⊕· · ·⊕wm (Am ⊕Am ) has no zero entries, µ be the spectral
radius of B , and Bµ = µ−1 B . Then, the minimum value in problem (7) is
equal to µ, and all solutions are given by
x = Bµ∗ u,

u 6= 0.

Proof. In the similar way as before, we first write
max wi d(Ai , xx− ) = x−

1≤i≤m

m
M

−
wi (Ai ⊕ A−
i )x = x Bx,

i=1

and then apply Lemma 1 to complete the proof.
We conclude with the case of reciprocal matrices.
Corollary 7. Let Ai be reciprocal matrices for i = 1, . . . , m, the matrix
B = w1 A1 ⊕ · · · ⊕ wm Am have spectral radius µ, and Bµ = µ−1 B . Then,
the minimum in (7) is equal to µ, and all solutions are given by
x = Bµ∗ u,

5

u 6= 0.

Approximation by Consistent Matrices

In the framework of tropical mathematics, both multiplicative and additive
consistent matrices X can be represented in a common form of the reciprocal
matrix of rank 1, given by the condition
X = xx− ,
to be interpreted in terms of the semifields Rmax,× for the multiplicative
case, and Rmax,+ for the additive.
The problem of finding an approximate consistent matrix for pairwise
comparison matrices can then be solved as an approximation problem (5) in
the log-Chebyshev or Chebyshev sense. Theorems 2–6 and their corollaries
provide new complete direct solutions to problem (5) under various assumptions, and hence to the problem of evaluating the scores of alternatives from
pairwise comparisons in the analysis of preference.
The application of these results offers a further improvement of the
known solutions in [5, 6]. Specifically, the new solutions replace the computation of all the eigenvectors of a matrix A as the columns in the matrix
∗
∗
A+
λ obtained from the matrix Aλ to the calculation of Aλ alone. At the
same time, these solutions can provide a significant extension of the solution
set since the column space of A∗λ is known to include the eigenspace for A,
which is generated by columns in A+
λ .
Note that it may appear that the eigenspace of A coincides with the
column space of A∗λ suggested by the new solutions, as in the following
trivial example.
11

Example 1. Consider the reciprocal matrix


1 a
A=
.
a−1 1
Using formula (3) in the context of the semifield Rmax,× yields λ = 1.
Furthermore, we have
Aλ = A,

A∗λ = I ⊕ Aλ = A,

∗
A×
λ = Aλ Aλ = A.

+
∗
∗
Since A×
λ = Aλ , we can take Aλ = Aλ , and thus conclude that the
+
eigenspace of A (the column space of Aλ ) and the column space of A∗λ
coincide.

The next example shows that, in general, the column space of A∗λ is
larger than the eigenspace of A. Moreover, those columns of A∗λ which do
not belong to the eigenspace may offer better solutions to the problem of
evaluating scores than the eigenvectors.
Example 2. Let us examine the pairwise comparisons on a multiplicative
scale, given by the matrix


1
2 1/2 1/2
 1/2 1
2 1/2 

A=
 2 1/2 1 1/2  .
2
2
2
1
A simple analysis of the pairwise comparison matrix yields the conclusion
that the last alternative should be ranked first. The first three alternatives
have lower ranks, but cannot be further differentiated.
For a formal analysis in the setting of the semifield Rmax,× , we apply
(3), which gives
λ = (a12 a23 a31 )1/3 = 2.
Next, we define the matrix



1/2 1 1/4 1/4
 1/4 1/2 1 1/4 

Aλ = λ−1 A = 
 1 1/4 1/2 1/4  .
1
1
1 1/2
Furthermore, we calculate

1/4 1/2 1 1/4

1 1/4 1/2 1/4
A2λ = 
 1/2 1 1/4 1/4
1
1
1 1/4






1 1/4 1/2 1/4
 1/2 1 1/4 1/4 

A3λ = 
 1/4 1/2 1 1/4  .
1
1
1 1/4


,

12

Finally, we can obtain and compare the matrices

1 1 1 1/4

1 1 1 1/4
A∗λ = I ⊕ Aλ ⊕ A2λ ⊕ A3λ = 
 1 1 1 1/4
1 1 1 1


1 1 1 1/4
 1 1 1 1/4 
∗


A×
λ = Aλ Aλ =  1 1 1 1/4  .
1 1 1 1/2




,


The first three identical columns in A∗λ coincide with the same columns
in A×
λ , and thus present an eigenvector. However, in the context of decision
making, this eigenvector gives no chance to rank alternatives. Although the
last column in A∗λ is not an eigenvector, it assigns the highest score to the
last alternative, and equally lower scores for the others, which ranks the
alternatives in line with the given matrix A.
To conclude this section, we briefly comment on the computational complexity involved in the procedure of calculating the matrix A∗λ from a pairwise comparison matrix A of order n. We note that the most computationally intensive part of the calculations is evaluating the first n powers of the
matrix A. It is not difficult to see that these powers can be obtained with
no more than O(n4 ) scalar operations, which results at most in the same
order of complexity for the entire procedure.

6

Application to Evaluation of Scores

Below, we present examples that demonstrate the use of the tropical optimization technique to solve particular problems of finding the scores based
on pairwise comparisons on a multiplicative scale. Considering that, in the
general terms of tropical mathematics, the solutions have a common form for
both multiplicative and additive scales, examples that assume an additive
scale of comparison are omitted.

6.1

Evaluation of Scores Given by One Matrix

We start with an example of evaluating the score vector based on one reciprocal matrix. The case of a positive matrix that may not be reciprocal is
presented next.
Example 3. Consider a reciprocal

1
 1/3
A=
 1/4
1/2

matrix defined as

3 4
2
1 1/2 1/3 
.
2 1
4 
3 1/4 1
13

To approximate this matrix by a reciprocal matrix of unit rank, and
thus to evaluate a score vector x, we apply Corollary 3 in the setting of the
semifield Rmax,× . First, we find the spectral radius λ for A. Application
of (3) gives
λ = (a13 a34 a42 a21 )1/4 = 2.
Furthermore, we consider the matrix

1/2 3/2 2
1

1/6 1/2 1/4 1/6
Aλ = λ−1 A = 
 1/8 1 1/2 2
1/4 3/2 1/8 1/2
and then calculate the matrices

1/4
2
1
4

1/12
1/4
1/3
1/2
A2λ = 
 1/2
3 1/4 1
1/4 3/4 1/2 1/4






,





1
6 1/2 2
 1/8 3/4 1/6 2/3 

A3λ = 
 1/2 3/2 1 1/2  .
1/8 1/2 1/2 1


,


Finally, we obtain the matrix



1
6
2
4
 1/6 1 1/3 2/3 
.
A∗λ = I ⊕ Aλ ⊕ A2λ ⊕ A3λ = 
 1/2 3
1
2 
1/4 3/2 1/2 1
Note that the columns in the matrix A∗λ are collinear to each other.
Specifically, the second, third and fourth columns can be obtained by multiplying the first one by 6, 2 and 4, respectively. Since all columns generate
exactly the same vector space, it is sufficient to use only one of them to
represent all solution vectors. We take the first column and write the score
vector as


1
 1/6 

x=
 1/2  u,
1/4
where the factor u can be arbitrary set to a positive number in accordance
with the required form or desired interpretation of the result.
Assuming u = 1, the vector x = (1, 1/6, 1/2, 1/4)T shows that the first
alternative has the highest score x1 = 1, followed by the third and fourth
with scores x3 = 1/2 and x4 = 1/4. The second alternative has the lowest
score x2 = 1/6.
If the scores are considered as weights to sum up 1, we put u = 1/(1 +
1/6+1/2+1/4) = 12/23. Then, we have the vector x = (12/23, 2/23, 6/23, 3/23)T .

14

Example 4. Consider a nonreciprocal matrix obtained from that in Example 3 by a slight change in the entries in the form


1 4 3
2
 1/3 1 1/2 1/2 
.
A=
 1/4 2 1
3 
1/2 3 1/4 1
To apply Theorem 2, we calculate the matrices



1 3 4
2
 1/4 1 1/2 1/3 

 , B = A ⊕ A− = 
A− = 
 1/3 2 1


4
1/2 2 1/3 1

1
1/3
1/3
1/2


4 4
2
1 1/2 1/2 
.
2 1
4 
3 1/3 1

Evaluation of the spectral radius of the matrix B by using (3) results in
µ = (b13 b34 b42 b21 )1/4 = 2.
To find the matrix Bµ∗ , we take the matrix



1/2 2
2
1
 1/6 1/2 1/4 1/4 

Bµ = µ−1 B = 
 1/6 1 1/2 2  .
1/4 3/2 1/6 1/2
After calculating

1/3
2

1/12
3/8
Bµ2 = 
 1/2
3
1/4 3/4

the matrix powers



1
4
1
6
2/3 2
 1/8 3/4 1/6 2/3 
1/3 1/2 
,
,
Bµ3 = 

 1/2 3/2
1/3 1
1 3/4 
1/2 3/8
1/8 9/16 1/2 1

we arrive at the matrix



1
6
2
4
 1/6 1 1/3 2/3 
.
Bµ∗ = I ⊕ Bµ ⊕ Bµ2 ⊕ Bµ3 = 
 1/2 3
1
2 
1/4 3/2 1/2 1
It is easy to see that the obtained matrix coincides with the matrix A∗λ
in Example 3. Since this matrix completely determines the score vector x,
the solution is the same as in Example 3. Specifically, as a score vector, one
can take the vector x = (1, 1/6, 1/2, 1/4)T .

15

6.2

Evaluation of Scores From Several Matrices

The problem of simultaneous approximation of several matrices naturally
appears when multiple results of pairwise comparisons for the same set of
alternatives according to a single criterion must be combined to produce a
common score vector.
Example 5. Consider the problem of evaluating the scores on the
the simultaneous approximation of m = 2 reciprocal matrices



1 3 4
2
1 4 3
2
 1/3 1 1/2 1/3 
 1/4 1 1/2 1/2
,
A1 = 
A2 = 
 1/4 2 1
 1/3 2 1
3 
4
1/2 3 1/3 1
1/2 2 1/4 1

basis of



.


To solve the problem, we apply Corollary 5, which requires the calculation of the matrix


1 4 4
2
 1/3 1 1/2 1/2 
.
B = A1 ⊕ A2 = 
 1/3 2 1
4 
1/2 3 1/3 1
The matrix B is the same as in Example 4. This allows the use of
the results of this example, which offer the score vector in the form x =
(1, 1/6, 1/2, 1/4)T .
Example 6. Suppose that we have two matrices, which
and given by



1 4 3
2
1 3
 1/3 1 1/2 1/2 
 1/3 1
,
A1 = 
A2 = 
 1/4 2 1
 1/3 2
4 
1/2 3 1/4 1
1/2 2
Application of

1

1/4

A−
1 =  1/3
1/2

Theorem 4 involves the matrices


3 4
2
1

1 1/2 1/3 
1/3
,

A−
2 =  1/4
2 1
4 
2 1/4 1
1/2

to be used in the construction of the matrix


1
 1/3
−
−
B = A1 ⊕ A1 ⊕ A2 ⊕ A2 = 
 1/3
1/2

are nonreciprocal

4
2
1/2 1/3 
.
1
3 
1/4 1


3 3
2
1 1/2 1/2 

2 1
4 
3 1/3 1


4 4
2
1 1/2 1/2 
.
2 1
4 
3 1/3 1

The matrix B again coincides with the matrix in Example 4, which
provides the same solution.
16

6.3

Weighted Scores From Several Matrices

Suppose that there are several criteria for judging alternatives, and each
criterion has a weight that indicates its relative importance among the criteria. If we have a pairwise comparison matrix obtained according to each
criterion, a problem of weighted evaluation of scores arises, which is to find a
single common score vector by combining the results of pairwise comparisons
with the weights.
Example 7. We examine the problem of evaluating the
given by m = 3 reciprocal matrices



1 3 1
3
1
2
 1/3 1 1/4 1/2 
 1/2 1

A1 = 
A2 = 
 1 4 1 1/2  ,
 1 1/3
1/3 2 2
1
1/4 2


1 4 2 1/2
 1/4 1 1/2 1/3 

A3 = 
 1/2 2 1 1/4  ,
2 3 4
1

vector of scores

1
4
1/3 1/2 
,
1
1 
1
1

which have to be taken with the weights
w1 = 1,

w2 = 1,

w3 = 1/2.

To apply Corollary 7, we calculate the matrix


1 3 1
4
 1/2 1 1/3 1/2 
.
B = w1 A1 ⊕ w2 A2 ⊕ w3 A3 = 
 1 4 1
1 
1 2 2
1
Then, we find the spectral radius
µ = (b14 b43 b32 b21 )1/4 = 2,
and examine the matrix



1/2 3/2 1/2 2
 1/4 1/2 1/6 1/4 

Bµ = µ−1 B = 
 1/2 2 1/2 1/2  .
1/2 1
1 1/2
After calculating

1
2

1/8
3/8
Bµ2 = 
 1/2 1
1/2 2

the matrices

2
1
1/4 1/2 
,
1/2 1 
1/2 1




1
4
1
2
 1/4 1/2 1/2 1/4 
,
Bµ3 = 
 1/2 1
1
1 
1/2 1
1
1
17

we form the matrix


1

1/4
Bµ∗ = I ⊕ Bµ ⊕ Bµ2 ⊕ Bµ3 = 
 1/2
1/2


4 2
2
1 1/2 1/2 
.
2 1
1 
2 1
1

Considering that all columns in the matrix Bµ∗ are collinear, we take the
first one to form the score vector


1
 1/4 

x=
u > 0.
 1/2  u,
1/2

6.4

Tropical Analytical Hierarchy Process

The following example shows how the results obtained can be used to develop
a tropical analog of the Analytical Hierarchy Process (AHP) decision scheme
in multicriteria decision making.
Example 8. Suppose that the results of pairwise comparisons of four alternatives according to three criteria are given by the matrices A1 , A2 and
A3 from Example 7. Furthermore, the relative importance of the criteria is
also compared, which yields the pairwise comparison matrix


1
1 2
C= 1
1 2 .
1/2 1/2 1
Let us find a score vector w = (w1 , w2 , w3 )T from the matrix C . Denote
the spectral radius of the matrix C by ν . Then, we obtain
ν = 1,

Cν = ν −1 C = C,

Cν2 = Cν = C.

To apply Corollary 3, we calculate
Cν∗ = I ⊕ Cν ⊕ Cν2 = C.
Since all columns of Cν∗ are collinear, we take one of them, say the first
column. Finally, we have


1
w =  1 .
1/2
Note that the elements of the vector w coincide with the weights used in
Example 7. Clearly, the solution of the multicriteria problem under consideration is the same as in this example, and can be represented as the score
vector x = (1, 1/4, 1/2, 1/2)T .
18

7

Conclusions

The paper aimed at reporting new developments in the area of applications
of optimization techniques in tropical mathematics to pairwise comparison
judgment in decision making. Various problems were considered, which arise
in ranking alternatives from their pairwise comparisons. The proposed solution approach uses the approximation, in the Chebyshev or log-Chebyshev
sense, of pairwise comparison matrices by consistent matrices, and reduces
the problems of ranking alternatives to a tropical optimization problem.
By applying recent results in tropical optimization, we offered new direct, explicit solutions in the closed vector form, which is ready for practical
implementation and further analysis. The solutions involve a finite number
of simple matrix-vector operations, which offers a low polynomial computational complexity. An example was given to show that the new solution can
be more accurate than other solutions previously obtained in the framework
of tropical mathematics. Note that the numerical examples demonstrate low
sensitivity of the solution vector to small variations in the matrix entries.
A tropical analogue of the AHP decision scheme was also presented as an
application example.
The development of new applications of the results to solve real-world
problem of evaluating alternatives is considered as one of the main lines of
future research.

References
[1] J. Barzilai. Deriving weights from pairwise comparison matrices. J.
Oper. Res. Soc., 48(12):1226–1232, 1997. doi:10.2307/3010752.
[2] M. T. Chu. On the optimal consistent approximation to pairwise
comparison matrices. Linear Algebra Appl., 272(1-3):155–168, 1998.
doi:10.1016/S0024-3795(97)00329-7.
[3] R. A. Cuninghame-Green. Describing industrial processes with interference and approximating their steady-state behaviour. Oper. Res.
Quart., 13(1):95–100, 1962. doi:10.2307/3007584.
[4] H. David. Method of paired comparisons, volume 41 of Griffin’s Statistical Monographs and Courses. Oxford Univ. Press, London, 1988.
[5] L. Elsner and P. van den Driessche. Max-algebra and pairwise
comparison matrices.
Linear Algebra Appl., 385(1):47–62, 2004.
doi:10.1016/S0024-3795(03)00476-2.
[6] L. Elsner and P. van den Driessche. Max-algebra and pairwise comparison matrices, II. Linear Algebra Appl., 432(4):927–935, 2010.
doi:10.1016/j.laa.2009.10.005.
19

[7] A. Farkas, P. Lancaster, and P. Rózsa. Consistency adjustments for
pairwise comparison matrices. Numer. Linear Algebra Appl., 10(8):689–
700, 2003. doi:10.1002/nla.318.
[8] M. Gavalec, J. Ramı́k, and K. Zimmermann. Decision Making and Optimization, volume 677 of Lecture Notes in Economics and Mathematical
Systems. Springer, Cham, 2015. doi:10.1007/978-3-319-08323-0.
[9] B. Giffler.
Scheduling general production systems using schedule algebra.
Naval Res. Logist. Quart., 10(1):237–255, 1963.
doi:10.1002/nav.3800100119.
[10] J. S. Golan. Semirings and Affine Equations Over Them, volume 556
of Mathematics and Its Applications. Kluwer Acad. Publ., Dordrecht,
2003. doi:10.1007/978-94-017-0383-3.
[11] M. Gondran and M. Minoux. Graphs, Dioids and Semirings, volume 41
of Operations Research / Computer Science Interfaces. Springer, New
York, 2008. doi:10.1007/978-0-387-75450-5.
[12] J. Gonzalez-Pachon, M. I. Rodriguez-Galiano, and C. Romero. Transitive approximation to pairwise comparison matrices by using interval goal programming. J. Oper. Res. Soc., 54(5):532–538, 2003.
doi:10.1057/palgrave.jors.2601542.
[13] B. B. Gursoy, O. Mason, and S. Sergeev. The analytic hierarchy process,
max algebra and multi-objective optimisation. Linear Algebra Appl.,
438(7):2911–2928, 2013. doi:10.1016/j.laa.2012.11.020.
[14] B. Heidergott, G. J. Olsder, and J. van der Woude. Max Plus at
Work. Princeton Series in Applied Mathematics. Princeton Univ. Press,
Princeton, NJ, 2006.
[15] A. J. Hoffman. On abstract dual linear programs. Naval Res. Logist.
Quart., 10(1):369–373, 1963. doi:10.1002/nav.3800100131.
[16] I. Itenberg, G. Mikhalkin, and E. Shustin. Tropical Algebraic Geometry, volume 35 of Oberwolfach Seminars. Birkhäuser, Basel, 2007.
doi:10.1007/978-3-7643-8310-7.
[17] V. N. Kolokoltsov and V. P. Maslov. Idempotent Analysis and Its Applications, volume 401 of Mathematics and Its Applications. Kluwer
Acad. Publ., Dordrecht, 1997. doi:10.1007/978-94-015-8901-7.
[18] N. Krivulin. A constrained tropical optimization problem: Complete
solution and application example. In G. L. Litvinov and S. N. Sergeev,
editors, Tropical and Idempotent Mathematics and Applications, volume
616 of Contemporary Mathematics, pages 163–177. AMS, Providence,
RI, 2014. arXiv:1305.1454, doi:10.1090/conm/616/12308.
20

[19] N. Krivulin. Tropical optimization problems. In L. A. Petrosyan, J. V.
Romanovsky, and D. W.-K. Yeung, editors, Advances in Economics
and Optimization, Economic Issues, Problems and Perspectives, pages
195–214. Nova Sci. Publ., New York, 2014. arXiv:1408.0313.
[20] N. Krivulin. Extremal properties of tropical eigenvalues and solutions
to tropical optimization problems. Linear Algebra Appl., 468:211–232,
2015. arXiv:1311.0442, doi:10.1016/j.laa.2014.06.044.
[21] N. Krivulin.
A multidimensional tropical optimization problem with nonlinear objective function and linear constraints.
Optimization,
64(5):1107–1129,
2015.
arXiv:1303.0542,
doi:10.1080/02331934.2013.840624.
[22] N. Krivulin. Rating alternatives from pairwise comparisons by solving tropical optimization problems. In Z. Tang, J. Du, S. Yin,
L. He, and R. Li, editors, 12th Intern. Conf. on Fuzzy Systems
and Knowledge Discovery (FSKD 2015), pages 162–167. IEEE, 2015.
doi:10.1109/FSKD.2015.7381933.
[23] D. Maclagan and B. Sturmfels. Introduction to Tropical Geometry,
volume 161 of Graduate Studies in Mathematics. AMS, Providence,
RI, 2015.
[24] W. M. McEneaney. Max-Plus Methods for Nonlinear Control and
Estimation. Systems and Control: Foundations and Applications.
Birkhäuser, Boston, 2006. doi:10.1007/0-8176-4453-9.
[25] S. N. N. Pandit. A new matrix calculus. J. SIAM, 9(4):632–639, 1961.
doi:10.1137/0109052.
[26] I. V. Romanovskiı̆. Asymptotic behavior of dynamic programming processes with a continuous set of states. Soviet Math. Dokl., 5(6):1684–
1687, 1964.
[27] T. L. Saaty. The Analytic Hierarchy Process. Advanced Book Program.
McGraw-Hill, New York, 1980.
[28] T. L. Saaty.
On the measurement of intangibles: A principal
eigenvector approach to relative measurement derived from paired
comparisons.
Notices Amer. Math. Soc., 60(2):192–208, 2013.
doi:10.1090/noti944.
[29] T. L. Saaty and L. G. Vargas. Comparison of eigenvalue, logarithmic
least squares and least squares methods in estimating ratios. Math.
Modelling, 5(5):309–324, 1984. doi:10.1016/0270-0255(84)90008-3.

21

[30] L. L. Thurstone. A law of comparative judgment. Psychological Review,
34(4):273–286, 1927. doi:10.1037/h0070288.
[31] N. M. Tran. Pairwise ranking: Choice of method can produce arbitrarily
different rank order. Linear Algebra Appl., 438(3):1012–1024, 2013.
doi:10.1016/j.laa.2012.08.028.
[32] N. N. Vorob’ev. The extremal matrix algebra. Soviet Math. Dokl.,
4(5):1220–1223, 1963.

22

