{'fraction_non_alphanumeric': 0.035172102810762065, 'fraction_numerical': 0.007703291748083571, 'mean_word_length': 4.699935746412508, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Algebraic solution to constrained bi-criteria decision problem of rating alternatives through pairwise comparisons

We consider a decision-making problem to evaluate absolute ratings (priorities, scores) of alternatives (choices, decisions) from the results of their pairwise comparisons according to two equally weighted criteria, subject to constraints on the rates. First, we formulate the problem as a bi-objective optimization problem that consists in the simultaneous constrained approximation, in the Chebyshev sense in logarithmic scale, of pairwise comparison matrices for each criteria by a common consistent matrix of unit rank, which determines the vector of ratings. Furthermore, we represent and solve the optimization problem in the framework of tropical (idempotent) algebra, which deals with the theory and applications of idempotent semirings and semifields. The solution approach involves the introduction of two parameters that represent the minimum values of approximation error for each matrix and thereby describe the Pareto frontier for the bi-objective problem. The optimization problem then reduces to a parametrized vector inequality. The necessary and sufficient conditions for solutions of the inequality serve to derive the Pareto frontier for the optimization problem. All solutions of the inequality, which correspond to the Pareto frontier, are taken as a complete Pareto-optimal solution to the optimization problem.


Introduction
This paper is concerned with the application of tropical (idempotent) algebra, which deals with the theory and applications of algebraic systems with idempotent operations, to a bi-criteria decision problem of rating alternative through pairwise comparisons. Since the first publications in 1950-60s, models and methods of tropical mathematics have found increased use in operations research, computer science and other fields. Rapid advances in the area are demonstrated in many works, including the recent monographs and textbooks [8,11,22,9,3].
One of the current research directions in tropical mathematics is the optimization problems, which are defined and solved in terms of tropical algebra. These optimization problems are often formulated as the minimization or maximization of functions defined on idempotent semifields, which are algebraic systems with idempotent addition and invertible multiplication. For some notable real-world applications, including time constrained project scheduling, minimax location problems with Chebyshev and rectilinear distances, and decision making trough pairwise comparisons, tropical optimization can provide a direct complete solution that explicitly describes all solutions of the problem in a compact parametric form, ready for formal analysis and instant computations with a decent polynomial time complexity.
The problem of evaluating absolute ratings (priorities, scores) of alternatives (choices, decisions) from the results of their pairwise comparisons according to several criteria is of great practical importance in multi-criteria decision making. The most commonly used approach to handle this decisionmaking problem is based on the Analytical Hierarchy Process (AHP) method [27,28], which uses conventional mathematics to calculate a unique numerical solution to the problem. In the framework of tropical algebra, the problem is examined in the papers [6,7,10,30]. A new solution approach is proposed in [14,15,17,18,19], which offers direct complete solutions to the problem in a explicit parametric form. Specifically, a tropical implementation of the AHP is developed in [15,19], and a constrained single-criterion problem is solved in [14]. Finally, in [18], a complete Pareto-optimal solution is obtained for an unconstrained bi-criteria problem of rating alternatives through pairwise comparisons.
In this paper, we consider a decision-making problem to evaluate absolute ratings of alternatives from the results of their pairwise comparisons according to two equally weighted criteria, subject to constraints on the ratings. First, we formulate the problem as a bi-objective optimization problem that consists in the simultaneous constrained log-Chebyshev approximation (approximation in the Chebyshev sense in logarithmic scale) of both pairwise comparison matrices by a common consistent matrix of unit rank, which determines the solution vector. Furthermore, we represent and solve the optimization problem in the framework of tropical algebra. The solution approach involves the introduction of two parameters that represent the minimum values of approximation error for each matrix and thereby describe the Pareto frontier for the bi-objective problem. The optimization problem then reduces to a parametrized vector inequality. The necessary and sufficient conditions for solutions of the inequality serve to derive the Pareto frontier for the optimization problem. All solutions of the inequality, which correspond to the Pareto frontier, are taken as a complete Pareto-optimal solution of the optimization problem.

Constrained Bi-Criteria Decision Problem
The purpose of this section is to describe and discuss the decision-making problem, which serves to motivate and illustrate the study. Suppose that one needs to evaluate alternatives (choices, options, possibilities) in the decision making process of selecting alternatives that have the highest rating (priority, score, weight). Given relative results of pairwise comparison of alternatives, obtained according to two criteria, the problem is to derive absolute ratings of alternatives, subject to constraints imposed on the ratings.

Unconstrained Pairwise Comparisons Under Single Criterion
First, assume that n alternatives are compared in pairs under a single criteria, which results in a pairwise comparison matrix A = (a ij ), where the entry a ij > 0 indicates that alternative i is a ij times superior (more preferred) than j . The entries of the matrix satisfy the equality a ij = 1/a ji , and thus the pairwise comparison matrix A is positive and symmetrically reciprocal. A pairwise comparison matrix A is called consistent if its entries possess the transitivity property a ij = a ik a k , which corresponds to the natural transitivity of judgments: if alternative i is a ik times more preferable than k and alternative k is a kj times more than j , then i should be a ik a k times more preferable than j . If the matrix A is consistent, then there exists a unique (up to a positive factor) positive vector x = (x i ), which determines the entries of A by the conditions a ij = x i /x j . It follows from these conditions that the entries of the vector x directly specify the individual ratings of alternatives, and thus this vector completely solves the problem of interest.
However, the pairwise comparison matrices, which are encountered in real-world problems, are commonly not consistent due to various cognitive or technical limitations of the comparison process. To overcome this difficulty, several techniques, which range from various heuristic procedures to matrix approximation, are used to estimate and then replace a given inconsistent matrix of pairwise comparisons by a consistent matrix that is close to the former matrix in some sense [29,27,4].
The heuristic solutions are often based on different schemes of aggregating columns in the pairwise comparison matrix, such as weighted column sum methods. A commonly used technique of deriving weights from pairwise comparison is the principal eigenvector method [26,27,28]. The method exploits the principal (Perron) eigenvector of the pairwise comparison matrix as a vector of absolute weights, which produces an estimating consistent matrix. In spite of the wide applications of the principal eigenvector method and other similar methods, and of many convincing arguments in favor of them, these methods cannot guarantee, in a mathematically strict sense, that the solution obtained is optimal.
In contrast to the heuristic methods, approximation techniques that derive approximating matrices by minimizing a distance between matrices (approximation error) offer a commonly accepted and mathematically justified approach to the problem. The available procedures differ according to their distance functions and measurement scales used to evaluate approximation error. The conventional application of the Euclidean (Frobenius), rectilinear (Manhattan) and Chebyshev metrics on the standard linear scale in the approximation of pairwise comparison matrices normally leads to complicated multiextremal nonlinear optimization problems that are hard to solve [29,4], and thus has no wide use.
The approximation in logarithmic scale with logarithm to a base greater than 1 leads to optimization problems that can usually be solved numerically by an appropriate computational algorithm, and sometimes analytically [29,1,4]. Minimization of the Euclidean distance in logarithmic scale (log -Euclidean approximation) results in a unique (up to a positive factor) solution, which is given parametrically in an exact analytical form. Due to the simplicity of solution and the rigorous formal justification, the log -Euclidean approximation finds extensive application in decision problems of rating alternatives from pairwise comparisons, where it is known as the method of geometric means.
Both log -rectilinear and log -Chebyshev approximation problems can be reduced by an appropriate transformation to linear programs and then numerically solved by one of the computational algorithms available in linear programming. This approach, however, cannot guarantee the derivation of a complete solution, which allows describing all solutions analytically in a direct explicit form.
The implementation of log -Chebyshev approximation involves minimizing the maximum absolute differences between the logarithms of the corresponding entries of the pairwise comparison matrix A = (a ij ) and a consis- Note that this problem can be reduced to an equivalent problem in the same variables, which does not involve the logarithm at all (see also [17,18,19]). Indeed, representing the absolute value as the maximum of two opposite values, and using the monotonicity of the logarithmic function turn the objective function into Moreover, the monotonicity property allows replacing the minimization of the logarithm by minimizing its argument. With the condition a ij = 1/a ji , the objective function to minimize becomes As a result, the problem of log -Chebyshev approximation at (1) takes the form of a problem to find positive vectors Finally note that solving problem (2) is equivalent to minimizing the maximum relative error [6,24,18], given by max 1≤i,j≤n A solution approach to handle problem (2) is proposed in [14,15,17,19] in the framework of tropical algebra. Using this approach, a complete analytical solution is derived, which describes all solution vectors in a compact parametric vector form.

Constrained Pairwise Comparisons Under Two Criteria
Suppose now that n alternatives are compared in pairs according to two equally weighted (unweighted) criteria, which results in two pairwise comparison matrices A = (a ij ) and B = (b ij ). The problem of rating alternatives changes to finding a common consistent matrix X = (x i /x j ) that is close to (approximates) both matrices A and B simultaneously. The new problem has two objectives that, in general, are in conflict, and thus essentially requires the application of multi-objective optimization techniques.
A wide accepted approach to solve the multi-criteria problems of pairwise comparisons uses the AHP decision method [27,28], which is based on the principal eigenvector calculation. In the case of the bi-criteria problem in question, the method produces a unique numerical solution in the form of the direct sum of normalized principal eigenvectors of the matrices A and B to be the vector x of absolute ratings of alternatives.
Another solution, which applies log -Chebyshev approximation, and provides a direct analytical representation of the result in terms of tropical algebra, is developed in [14,15,17,19] as a tropical implementation of the AHP method. The solution follows a scalarization approach to reduce the vector-valued bi-criteria problem to a single criterion problem in the form of (2) with the matrix A replaced by Since no single solution generally exists to satisfy all objectives simultaneously, a set of solutions that yield the best compromise between objectives are normally considered as a complete solution of multi-objective problems. A common approach to handle these problems is based on the derivation of a set of Pareto-optimal (Pareto-efficient, non-dominated) solutions, at which none of the objective can be improved without making another objective worse [5,20,2,23]. In bi-objective problems, the image of the Paretooptimal set (the Pareto frontier) can often be visualized as a trade-off curve in the plane of objectives, and then used to describe all Pareto optimal solutions [25].
In the framework of log -Chebyshev approximation, the bi-criteria problem of pairwise comparisons takes the form of the bi-objective optimization problem minimize max 1≤i,j≤n A complete Pareto-optimal solution to this unconstrained problem in the tropical algebra setting is obtained in [18], where the set of solutions is explicitly described in a parametric vector form.
Furthermore, assume that, for some reason, the absolute ratings of alternatives must satisfy additional constraints, which restrict possible relations between individual ratings. Given real numbers c ij ≥ 0, the constraints take the form of the inequalities where c ij specifies that the rating of alternative i must be not less than c ij times the rating of j . The value c ij = 0 indicates that no lower bound is defined on the rating of alternative i with respect to that of j .
Combining the inequalities for all j at each i into one yields the inequalities max Finally, with these constraints added, the bi-objective problem turns to the following constrained problem: given symmetrically reciprocal positive matrices A = (a ij ) and B = (b ij ), and a non-negative matrix C = (c ij ), find positive vectors In the subsequent sections, a complete Pareto-optimal solution of problem (3) is derived in the framework of tropical algebra in a direct parametric form.

Preliminary Definitions and Results
We start with a brief overview of main definitions, basic facts and preliminary results of tropical algebra, based mainly on [12,13,16], to provide a formal framework to the solution of the bi-objective optimization problem in what follows. For further details on tropical mathematics and its applications one can consult, e.g., the recent monographs and textbooks [8,11,22,9,3,21].
In the semifield, addition is idempotent, which means that x ⊕ x = x for all x ∈ X. Multiplication is invertible: for each x = 0, there exists its inverse x −1 such that xx −1 = 1 (here and hereafter the multiplication sign ⊗ is, as usual, omitted for the sake of brevity).
The power notation with integer exponents specifies iterated products defined for each x = 0 and integer p > 0 as 0 p = 0, Moreover, the equation x p = a is assumed to have a unique solution x for any a ∈ X and integer p > 0, which extends the power notation to rational exponents.
Idempotent addition introduces a partial order on X by the rule: x ≤ y if and only if x ⊕ y = y . With this order, both addition and multiplication are isotone in each arguments, which means that the inequality x ≤ y yields the inequalities x ⊕ z ≤ y ⊕ z and xz ≤ yz for all x, y, z ∈ X. Furthermore, inversion is antitone: the inequality x ≤ y results in x −1 ≥ y −1 for all x, y = 0. Addition possesses the extremal property that x ≤ x ⊕ y and y ≤ x ⊕ y . Finally, the inequality x ⊕ y ≤ z is equivalent to the pair of inequalities x ≤ z and y ≤ z .
In what follows, the above partial order is assumed to turn into a compatible linear order to make the semifield totally ordered.
A typical example of idempotent semifields is the system (R + , max, ×, 0, 1), where R + is the set of non-negative reals. This semifield, which is often called the max-algebra, has addition defined as maximum, and multiplication as usual. The zero 0 and one 1 respectively coincide with the arithmetic 0 and 1, the power notation and the notion of inversion have the ordinary interpretation, the order induced by idempotent addition corresponds to the natural order on R + .

Matrices and Vectors
Matrices over X are introduced in the ordinary way. The set of matrices with m rows and n columns is denoted X m×n . A matrix with all entries equal to 0 is the zero matrix. A matrix without zero columns is called column-regular.
Addition, multiplication and scalar multiplication of matrices follow the conventional rules with the arithmetic addition and multiplication replaced by ⊕ and ⊗. For any conforming matrices A = (a ij ), B = (b ij ), C = (c ij ) and a scalar x, matrix addition, multiplication and scalar multiplication are given by The scalar inequalities, which represent properties of scalar operations, extend to the matrix operations, where the inequalities are interpreted entrywise.
Consider square matrices of order n from X n×n . A matrix with all diagonal entries equal to 1 and the off-diagonal entries to 0 is the identity matrix I .
The power notation with non-negative integer exponents specifies repeated multiplication of a matrix by itself, and is defined as A 0 = I and A p = AA p−1 for any matrix A and integer p > 0. The trace of a matrix A = (a ij ) is given by tr A = a 11 ⊕ · · · ⊕ a nn .
For any conforming matrices A, B and C , and a scalar x, the following identities hold: tr(AC) = tr(CB), tr(xA) = x tr A.
For any matrix A, a tropical analogue of matrix determinant is a function that is given by Provided that Tr(A) ≤ 1, the asterate operator (Kleene star) is defined as A matrix that consists of only one column (row) is a column (row) vector. The set of column vectors of order n is denoted by X n . All vectors below are column vectors if not explicitly transposed. A vector with all elements equal to 0 is the zero vector denoted 0. A vector without zero elements is called regular.
For any nonzero vector x = (x j ), multiplicative conjugate transposition yields the row vector x − with the entries A scalar λ is an eigenvalue of a matrix A if there exists a vector x = 0 (eigenvector) such that Ax = λx.
The maximum eigenvalue (with respect to the order induced by idempotent addition) is called the spectral radius of the matrix and calculated as λ = tr A ⊕ · · · ⊕ tr 1/n (A n ).
Consider matrices and vectors over max-algebra (R + , max, ×, 0, 1). The zero and identity matrices in the max-plus algebra have the same form as in conventional linear algebra. The matrix and vector operations are performed by the standard rules with the arithmetic addition replaced by the operation of taking maximum. The regular vectors are positive vectors.

Vector Inequalities
We conclude with preliminary results that play a key role in the solution of the bi-objective tropical optimization problem in the next section. First, assume that, given a matrix A ∈ X m×n and a vector d ∈ X m , we need to solve, with respect to the unknown vector x ∈ X n , the inequality A direct solution is provided by the following statement (see, e.g., [12]).

Lemma 1.
For any column-regular matrix A and regular vector d, all solutions to inequality (4) are given by Next, suppose that, for a given matrix A ∈ X n×n , we seek to find regular vectors x ∈ X n to satisfy the inequality The next result, which is obtained in [13], offers a complete solution.
Theorem 2. For any matrix A, the following statements hold.

Identities and Inequalities for Traces
Finally, we present binomial identities for matrices and their traces, that allow to simplify subsequent algebraic manipulations. We start with a binomial identity that is valid for any square matrices A, B ∈ X n×n and positive integer m in the following form (see also [16]): Taking trace of both sides and using properties of traces yield After summing over m = 1, . . . , n, and rearranging terms, we obtain the identity where the first and the last terms are given by

Constrained Bi-Objective Optimization Problem
We now offer a complete Pareto-optimal solution to a constrained bi-objective optimization problem, which is formulated in terms of an arbitrary tropical semifield, and solved under rather general conditions. Suppose that, given matrices A, B, C ∈ X n×n , the problem is to find regular vectors x ∈ X n that Before solving the problem, we note that, by Theorem 2, the inequality constraint has nontrivial solutions only under the condition Tr(C) ≤ 1, which we have to take as a necessary assumption.
To describe the solution in a compact form, we use the following notation. For any matrices A, B, C ∈ X n×n , we introduce the scalars and note that λ and µ indicate the spectral radii of the matrices A and B . Next, for any l = 1, . . . , k , m = 1, . . . , n − k and k = 1, . . . , n, we denote We observe that both functions G and H monotonically decrease as their arguments increase. Moreover, it is not difficult to verify that the solution of the inequality G(s) ≤ t is given by H(t) ≤ s and vice versa. Suppose, for instance, that the inequality G(s) ≤ t holds. This inequality is equivalent to the system of inequalities By combining these inequalities into one, we obtain the inequality H(t) ≤ s.
We are now in a position to formulate and proof the main result of the paper.
Theorem 3. Let A and B be matrices with respective spectral radii λ > 0 and µ > 0, and C is a matrix with Tr(C) ≤ 1. Then, the following statements hold.
2. If H(µ ⊕ θ) > λ ⊕ σ , then the Pareto frontier is a segment defined by 3. All Pareto-optimal solutions are given in parametric form by Proof. First, we denote the optimal values of the objective functions x − Ax and x − Bx in the Pareto frontier of the problem by α and β respectively. The corresponding solutions x are then given by the parametrized system Since the parameters α and β are assumed to take minimum values that cannot be improved, the set of solution vectors x does not change if the equalities are replaced by inequalities, which results in the system Furthermore, we use Lemma 1 to solve the first inequality with respect to Ax and the second with respect to Bx, and then rearrange the parameters. The system now becomes Finally, we combine the inequalities into one parametrized inequality By Theorem 2, the inequality obtained has regular solutions if and only if the following condition holds: Under this condition, all regular solutions are given in the parametric form Consider the existence condition at (8) and apply identity (6) to expand the left-hand side of the inequality as The existence condition is equivalent to the system of inequalities We now solve these inequalities with respect to the parameters α and β . We take the first inequality and replace it with the inequalities α −k tr A k ≤ 1, k = 1, . . . , n.
After solving the inequalities for α and combining the results, we obtain the solution α ≥ n k=1 tr 1/k (A k ) = λ.
Next, we examine the second inequality at (10). An application of identity (6) to the left-hand side yields The inequality under examination reduces to the system n k=1 β −k tr B k ≤ 1, where the inequality Tr(C) ≤ 1 holds by the assumption of the theorem. Solving the first and third inequalities in the system in the same way as above, we obtain We now turn to the third inequality at (10), given by We consider the left-hand side and note that the trace under summation can be expressed as After substitution of this expression, we use the symbol r k,l,m to rewrite the inequality as the system of two inequalities We solve the first inequality with respect to the parameter α to obtain Finally, we combine all inequalities for α and β into the following system: Taking into account that G(α) decreases as α increases, we see that this system defines an area on the αβ -plane, which is bounded from the left and from below by the lines α = λ ⊕ σ and β = µ ⊕ θ , and lies above the graph of the function β = µ ⊕ θ ⊕ G(α).
To describe the Pareto frontier for the problem, we note that any interior point of the area can be improved and hence cannot belong to the frontier. For the same reason, the left and bottom boundary half-lines cannot be parts of the frontier, except for their corresponding bottommost and leftmost points. Both points may coincide in the single point (λ⊕σ, µ⊕θ) if the graph of the function G(α) lies below this point, or be the ends of a segment that is cut out from the graph by the lines α = λ ⊕ σ and β = µ ⊕ θ , otherwise.
The Pareto frontier shrinks to a single point, where the parameters are fixed at the values α = λ ⊕ σ, β = µ ⊕ θ.
Substitution of these values for the parameters in the solution at (9) yields all corresponding Pareto-optimal solutions of the problem in this case.
If we assume the parameter α to satisfy the inequality α ≤ H(µ ⊕ θ), then the Pareto frontier takes the form of a non-linear segment, given by In this case, a complete Pareto-optimal solution is given in the general form defined by (9).

Application to Bi-Criteria Decision Problem
Consider the bi-criteria decision problem at (3), and represent it in terms of the semifield with the maximum in the role addition (max-algebra) as follows: subject to 1≤j≤n c ij x j ≤ x i , i = 1, . . . , n.
Furthermore, with the vector-matrix notation the vector objective function to minimize becomes

whereas the inequality constraints do
Cx ≤ x.
After combining the objective and constraints, the problem takes the form of the bi-objective tropical optimization problem at (7), and thus has the solution given by Theorem 3.

Conclusion
In this paper, a new application of tropical (idempotent) algebra has been developed to solve a bi-criteria problem of rating alternatives through pairwise comparisons according to two criteria, subject to constraints on the relative values of ratings. A complete Pareto-optimal solution of the problem has been obtained analytically in a compact vector form. This result extends previous solutions of an unconstrained bi-criteria problem and a constrained single-criterion problem.
The future research can focus on extending the results to bi-criteria problems with additional constraints and to problems with more than two criteria. The evaluation of computational complexity of the solution is also of great interest.