This paper addresses the problem of ordering multi-attribute alternatives using lexicographic criteria. It proposes a method for determining the numerical values of criteria weights when applying a lexicographic approach to ranking such alternatives. The method includes a rationale for deriving weighting coefficients based on a posteriori analysis of criterion values. The concept of exact approximation of weights calculated in cardinal scales is introduced. The paper explores the potential applications and directions for using these relative importance coefficients. A formalized approach to computing the rankings of alternatives-based on solving a multicriteria problem with lexicographic criteria-is presented. Depending on the chosen heuristic for criteria aggregation, metrized values of criteria are derived. In this context, methods for the automated recovery of numerical criteria weights are proposed. The paper also provides a justification for the proposed approach and outlines prospects for future research in this area.
Lexicographic ordering problems are a well-established area of scientific research [1, 2]. They are widely and successfully applied in various practical contexts, attracting attention from both domestic and international researchers across different classes of such problems [3, 4]. Applications include the optimization of complex systems composed of interdependent subsystems, marketing research, the determination of ratings or rankings in competitive sports, admissions to higher education institutions, and many other areas of human activity.
The method presented in this paper can be interpreted as a solution to a recovery problem. It may also be viewed as a technique for the a posteriori determination of attribute weights for alternatives, or the relative importance of decision-making criteria in multicriteria optimization problems [5, 6].
Developing tools to address common applied problems is both a pressing and often underappreciated task [7]. There will always be critics who question the necessity or usefulness of introducing yet another method, especially when dozens of established approaches already exist and appear to perform adequately. As a result, it becomes essential to justify the new method’s effectiveness, highlight its advantages, and demonstrate its superiority over existing approaches [8].
However, for so-called instrumental methods—that is, auxiliary techniques intended to support, rather than directly solve, primary problems—traditional evaluation criteria such as “better,” “more efficient,” or “more accurate” may not always apply. Nonetheless, it is clear that in certain unique situations, the development or application of equally unique methods is both reasonable and necessary.
An important stage in expert evaluation involves determining the balance between experts’ subjective opinions and “objective” data [9, 10]. Numerous studies have demonstrated that seemingly obvious subjective judgments can differ significantly from objective or a posteriori assessments. In such cases, indirect methods have shown particular promise [11].
In many real-world problems across various applied fields, the subjective perceptions of experts and decision-makers often differ significantly from the corresponding “objective” assessments. In such cases, identifying the heuristics an expert used to organize alternatives becomes a problem of inference. The resulting mathematical model is considered more objective when the outcomes of applying a particular aggregation of criteria closely align with the expert’s ranking of alternatives.
The lexicographic method is based on the principle that partial optimization criteria are first ranked according to their relative importance. Then, using expert-defined preference ratios among the criteria, a sequence of single-criterion optimization problems is solved iteratively, starting with the most important criterion. It is worth noting that the initial auxiliary task of ranking the criteria on an ordinal scale is generally nontrivial [12, 13], although numerous methods have been developed to address this challenge [14, 15].
Lexicographic ordering of alternatives follows an approach in which criteria are considered in descending order of importance, with the most important criterion taking precedence over equal values of all others. Such strict prioritization often emerges when additional criteria are introduced sequentially into conventional scalar optimization problems that may lack a unique solution. An optimization problem with strictly ordered criteria is referred to as a lexicographic optimization problem.
A preliminary step in solving the multicriteria optimization problem underlying lexicographic ordering is to rank the partial criteria in decreasing order of importance. By assigning numerical labels to the criteria, we can—without loss of generality—assume that the first criterion is the most important. In many practical cases, the lexicographic method produces a unique solution after optimizing with respect to the first criterion, allowing the process to terminate at that point [16, 17]. However, such trivial cases are not considered in this paper.
Problems in which the criteria are ranked by importance and renumbered such that each preceding criterion is incomparably more important than all subsequent ones are referred to as lexicographic optimization problems. In such problems, the resulting non-strict preference relation adheres to a lexicographic order [12, 18].
Suppose we have a multi-attribute selection problem xij X , i I 1,..., k, j J 1,..., n , , X Rk
F f1,..., fk , fi fi x x, i 1,..., k .
It is necessary to rank the alternatives of type (
Accordingly, the weighting factors that represent the relative importance of the criteria in
ranking (
1 2 ... k1 k .
The vectors of criteria values for different alternatives will be denoted by
(
Based on the application of the lexicographic criterion, the alternatives in set (
Without diminishing the generality, we will assume that as a result of applying the lexicographic
criterion (
The task is to determine the quantitative values of the weighting coefficients (
Heuristic H1. The aggregating criterion for ordering the alternatives is the additive convolution
of the weighted values of the attributes of the alternatives. That is, to determine the generalized
indicators of each alternative of the form (
Heuristic H2. When applying the quantitative weighting coefficients of the criteria [19, 20], the order established by applying the lexicographic criterion should be preserved. That is, the system of inequalities must be fulfilled: or
F1 F 2 ... F n1 F n k k k k i xi1 i xi2 ... i xin1 i xin i1 i1 i1 i1 .
When applying lexicographic criteria, it is believed that the difference between the ordered criteria is so great that the next criterion in the series is considered only if it is not possible to find an answer according to the older criteria and there is no question of concessions at all [17]. In this case, the optimization problem or the problem of ordering a set of alternatives with strictly ordered criteria is called lexicographic.
Heuristic H3. When applying quantitative weighting coefficients of the criteria, the system of
inequalities can be fulfilled:
k i xi1 k i xi2 ... k i xin1 k i xin (
We will analyze all the ratios specified in heuristics H2-H3 in order to determine the system
(
From a mathematical point of view, there is no ideal method or way to solve such problems. Each of them has its own specific advantages and disadvantages and scope. According to the set of goals C C1,...,Ck ,
facing the researcher, the following class of expert evaluation tasks is distinguished [12] - ranking, i.e., ordering the entire set of alternatives [21, 22]. The lexicographic method is based on the fact that the criteria are taken into account in descending order of importance, with the advantage of the extremum of the highest criteria over the same value of all others [16, 23]. It is clear that this method has disadvantages that limit the application of this method, such as the complexity and subjectivity of ranking criteria, inapplicability in case of their equivalence, etc.
Lexicographic multi-criteria ordering is widely used in various practical applications [22, 23]. In certain fields, it represents the only natural method for structuring a set of alternatives. Some examples of its application are presented in Table 1. Clearly, this list is not exhaustive and could be significantly extended. Providing a comprehensive overview of all possible applications of the lexicographic criterion was not the author’s objective. Accommodation Benefit categories Remoteness of the Student success is
in a student - lexicographical place of residence minimized dormitory with a organization, is minimized limited number of depending on the beds category of benefits ROI (Return on The campaign Campaign name Investment) is budget is organized minimized minimized lexicographically 12 Marketing:
Analyzing advertising campaigns 13 Ranking of The company's Company name companies by income is lexicographically revenue and minimized in ascending order
name 14 Sorting bank The account Client's surname
customers by balance is lexicographically account balance minimized in ascending order and last name 15 Sort products by Category - Brand category, brand, lexicographical lexicographically
and price 16 Creating a list of Wages are Company name - Position
vacancies minimized lexicographically lexicographically 17 Sorting orders by Order status: from Date of order - Client's name priority "urgent" to primarily early lexicographically "regular" orders are
preferred 18 Sorting logistics Delivery priority: The length of the Name of the delivery routes from highest to route is destination lowest maximized lexicographically
Price - maximized
Remark 1. Lexicographic ordering is often used to establish rules of precedence, priority, etc. Remark 2: In lexicographic organization, ordinal scales with several gradations are often used.
The method is used in problems in which individual goals have different weights and can be arranged in a certain hierarchical order. In such problems, the first stage of optimization determines the set of solutions that optimizes the highest-ranked objective. The resulting set D of solutions is narrowed at the second stage by optimizing the second most important objective. This process continues until there is only one single solution. If a single solution cannot be found when optimizing the lowest ranked objective, a subjective choice is made from the set of remaining solutions [24], or an additional criterion is introduced. This method is widely used, but it assumes a hierarchy of goals [25, 26].
It should be noted that partial criteria can be qualitative, quantitative, and lexicographic [27, 28].
Remark 3: For situations of ordering by qualitative criteria, there may be variations with a different number of gradations or clusters, depending on the specifics of the application area, approaches developed by the authors of the task, and other factors.
Remark 4. Of course, there may be various variations of multicriteria lexicographic organization along the lines shown in the table. But the table demonstrates the breadth and diversity of the application of multicriteria lexicographic organization.
Remark 5. In order to achieve fairness, it is sometimes correct to move from quantitative criteria to interval criteria, to the construction of membership functions, to the creation of clusters, and to solve auxiliary problems beforehand. It is clear that such procedures should be supported by a strong justification. In addition, for sound work in these classes of problems, appropriate mathematical support must be developed.
Definition 1. The special points for the exact approximation of the preference structure on the set of
criteria (
Definition 2. An exact approximation is a situation where inequalities are generated at special points, and to transform them into an order ratio with respect to the corresponding weighting coefficients, some sufficiently small number must be subtracted.
Heuristic H4. In order to apply an accurate approximation and comply with the requirements of strict ordering, a sufficiently small fixed deviation from the found values of the weighting coefficients can be expertly set, if necessary: . i i , i 1,..., k, 0
Heuristic H5. The value of the correction to the respective weighting factors can be calculated, for example, as the inverse of the highest ranking of alternatives determined by the results of solving the lexicographic ordering task.
Remark 6. With an inaccurate approximation, the ordering of alternatives on the set (
It is worthwhile to examine the correlation between subjective perceptions and the "objective"
data derived from accurately approximating the structure of preferences induced by the ordering of
alternatives in set (
Heuristic H6. We will use the lexicographic criterion to descend the ordering of some structure.
Heuristic H7. The aggregating criterion for ordering alternatives is the additive convolution of the weighted values of the attributes of alternatives.
Heuristic H8. Equality in the weighted convolution values of alternative attributes is possible only when the corresponding attribute vectors are completely equivalent. In all other cases, once the weights of the partial criteria have been determined, they should be incremented by a specified small value. The resulting adjusted weights are then considered an accurate approximation of the structure of the set of alternatives.
Let's assume that, according to formula (
The algorithm is based on analyzing the structure of preferences, beginning with the comparison of attribute values for the least important criteria. Below, we present the algorithm for determining the weighting coefficients of criteria in a lexicographic ordering of alternatives as a sequence of steps.
Step 1. Set the year to 1.
Step 2. Cycle through i k 1 to 2.
Step 2.1. Set the counter of special situations for the index i : s 0 .
Step 2.2. Loop for j 1 to n 1 .
Step 2.2.1. If the values of the attributes of the alternatives of set (
Step 2.2.2. If there is an inequality xij xij1, then we determine the value of the ratio: is xij1 xij / xij1 xij11
Step 2.2.3. Increase the counter of special situations s s 1.
Step 2.3. If the counter of special situations is s 0, then the presence of a quasi-series is stated - a loose ordering of partial criteria. In this case, equivalent criteria are combined and k k 1 is assumed.
Step 2.5. Set the counter of special situations for the index i 1 : s 0. Step 2.6. Cycle through j 1 to n 1 .
Step 2.6.1. If the values of the attributes of the alternatives of set (
Step 2.6.3. Increase the counter of special situations s s 1 .
Step 3. End of the cycle for i .
Step 4. Increase the values of partial weighting coefficients by some small predefined real number: i i , for i 1,..., k 1.
Step 5. Displaying the calculated values of the partial criteria: i , i 1,..., k. .
Step 6. End of the algorithm.
Let us consider the team medal standings from one edition of the Olympic Games—the 2024 Paris Olympics. Using publicly available data [32], we analyzed the medal standings of both the Olympic and Paralympic Games from 2008 to 2024.
Number 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
In Table 3, the situations that give rise to special points of lexicographic ordering of alternatives are marked on the yellow background, and the analysis of these points allows for an accurate approximation of the structure of preferences created by applying the lexicogaphy ordering of the set of multi-attribute alternatives.
To calculate the metrized values of the criteria weights when analyzing the structure of the set of Olympic medalists by their affiliation with different countries at the 2024 Olympics, it is advisable to use an exact approximation. We will use the algorithm described above. Based on open data [33], we analyzed the results of team medal competitions at the Olympic and Paralympic Games from 2008 to 2024 and summarized them in Table 4.
When applying the H2 heuristic to fulfill the system of inequalities of the form (
Similarly, we analyzed the tables of the number and nationality of medalists from other Olympics: Beijing 2008, London 2012, Rio 2016, and Tokyo 2020. An analysis of the results of the relevant Paralympic Games from 2008 to 2024 was also carried out. The results of all the calculations are summarized in Table 4.
Paralympic Games 2024 (Paris) Olympics 2020 (Tokyo) Paralympic Games 2020 (Tokyo) Olympics 2016 (Rio de Janeiro) Paralympic Games 2016 (Rio de Janeiro) Olympics 2012 (London) Paralympic Games 2012 (London) Olympics 2008 (Beijing) Paralympic Games 2008 (Beijing)
Gold/ Silver/B Gold/ Bronze ronze Silver 92 5 18,4 53 6 8,8 60 8 7,5 160 5 32 71 8 8,9 59 4 14,8 43 141 74 92 3 9 6 7 14,3 15,7 12,3 13,1
Bronze 124,16 69,39 45,57 179,49 83,03 95,01 52,5 114,34 70,65 96,81
In Table 4, when applying the H3 heuristic, taking into account the system of inequalities of the
form (
The ratio of the weighting coefficients of gold and silver medals in relation to bronze medals at
different Olympics when applying the H2 heuristic according to formula (
Based on the data presented in Table 4, using the H2 heuristic and formula (
0,017 0,014 0,016 0,007 0,010
If we apply the heuristic H3 and formula (
If we build a linear convolution of the form (
This paper addresses the problem of lexicographic ordering of multi-attribute alternatives. A method for precisely approximating the structure of the ordered set of alternatives is proposed. Based on the analysis of this structure, a method for determining the quantitative values of the weighting coefficients is presented, ensuring an accurate approximation of the preference relations on the set of criteria in an ordinal scale.
A calibration method for representing weighting coefficients is proposed, offering a convenient visualization for certain classes of expert evaluation tasks. The calibration of the presented weighting coefficients is achieved by dividing the normalized coefficients by the smallest value among all the coefficients.
Sorting by multiple lexicographical criteria enables the organization of data across several parameters simultaneously, a method commonly used in real-world systems such as databases, user interfaces, logistics, accounting, banking, and many other industries. This approach facilitates easy navigation and quick access to relevant information. The paper illustrates this by presenting the unofficial team standings of national Olympic teams, ranked by the number of medals of various types they won during the competition. The attribute weights calculated by the author help explain why these standings are considered unofficial.
The author presents a well-reasoned illustration of the inefficiency of using a linear convolution of criteria. In fact, the "infinity" of the advantages attributed to more important criteria in lexicographic ordering, as often claimed in many textbooks, is critically examined. The analysis demonstrates that logical and reasonable heuristics can lead to results that sharply contrast with subjective human perceptions.
The author demonstrates that when the ranking of alternatives is determined using weighting coefficients set a priori by experts, the ordering established by the lexicographic criterion may be violated. This underscores the potentially misleading nature of commonly held notions such as fairness and validity. The findings suggest that, in many practical situations, widely accepted standards are neither always logical nor universally acceptable. Ultimately, subjective perceptions often differ significantly from "objective" evaluations—those defined by two heuristics: the lexicographic ordering of partial criteria and the conventional additive convolution of weighted attributes of alternatives.
The author has not employed any Generative AI tools. [24] J. Dombi, C. Imreh, N. Vincze, "Learning Lexicographic Orders", European Journal of Operational
Research, vol. 183, pp. 748–756, 2007. https://doi.org/10.1016/j.ejor.2006.10.009 [25] T. Todorov, G. Bogdanova, T. Yorgova, "Lexicographic Constant-Weight Equidistant Codes over the Alphabet of Three, Four and Five Elements", Intelligent Information Management, vol. 2, pp. 183–187, 2010. https://doi.org/10.4236/iim.2012.23021 [26] K.-W. Jee, D.L. McShan, B.A. Fraass, "Lexicographic Ordering: Intuitive Multicriteria Optimization for IMRT", Physics in Medicine and Biology, vol. 52, no. 7, pp. 1845–1861, 2007. https://doi.org/10.1088/0031-9155/52/7/008 [27] S. Hess, J.M. Rose, J.W. Polak, "Non-Trading, Lexicographic, and Inconsistent Behavior in SP Choice Data", Transportation Research Part D: Transport and Environment, vol. 15, no. 7, pp. 405– 417, 2010. https://doi.org/10.1016/j.trd.2010.05.004 [28] R. Kohli, K. Jedidi, "Representation and Inference of Lexicographic Preference Models and Their
Variants", Marketing Science, vol. 26, pp. 380–399, 2007. https://doi.org/10.1287/mksc.1060.0262 [29] Sergii Kadenko, Vitaliy Tsyganok, Zsombor Szádoczki, Sándor Bozóki, Patrik Juhász and Oleh Andriichuk Improvement of Pair‐wise Comparison Methods Based on Graph Theory Concepts CEUR Workshop Proceedings (ceur-ws.org). Vol. 3241 urn:nbn:de: 0074-3241-0. Selected Papers of the XXI International Scientific and Practical Conference "Information Technologies and Security" (ITS 2021), Kyiv, Ukraine, December 9, 2021. pp. 46-55. [http://ceur-ws.org/Vol3241/paper5.pdf] [30] Oleh Andriichuk, Vitaly Tsyganok, Sergii Kadenko, Yaroslava Porplenko Experimental Research of Impact of Order of Pairwise Alternative Comparisons upon Credibility of Expert Session Results Proceedings of the 2nd IEEE International Conference on System Analysis & Intelligent Computing, (SAIC), 05-09 October, 2020, Kyiv, Ukraine, pp. 1-5. https://doi.org/10.1109/SAIC51296.2020.9239126 [31] F. Yaman, T.J. Walsh, M.L. Littman, M. Desjardins, "Democratic Approximation of Lexicographic Preference Models", in Proc. of the 25th Int. Conf. on Machine Learning (ICML 2008), 2008. https://doi.org/10.5555/1390678.1390755 [32] Hnatiienko H., Snytyuk V., Tmienova N., Zatonatskiy D. and Zhylinska O. Mathematical Support of the Task of Determining the Strategic Directions of Development and Priorities of the Organization / CEUR Workshop Proceedings, Volume 3347, Pages 169 – 184, 2022 // 9th International Scientific Conference "Information Technology and Implementation", IT and I 2022, Kyiv, November 30 - December 02, 2022 [33] Paris 2024 Olympic Medal Table – Gold, Silver & Bronze, International Olympic Committee, archived Aug. 12, 2024. Accessed Aug. 11, 2024. Available: https://www.olympics.com/en/olympic-games/paris-2024/medals