Non-contradictory aggregation of quasi-order relations | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 45. DOI: 10.17223/20710410/45/13

The paper belongs to the “Collective choice” section of the mathematical theory of decision-making. A method for non-contradictory aggregation of expert preferences given by quasi-order relations is proposed. The aggregated relation is built according to the rule of “the ma jority of experts”, which satisfies the condition of the minimum distance from expert preferences. Let the expert preferences profile be given by the quasi-order relations ρ1,ρ2, . . .,ρm on the set of alternatives A = {a1,a2,. . . ,an}. Relations will be given by the preference matrices P¹, P², ... , P^m and the vertex adjacency matrices R¹, R²,. . . ,R^m of the corresponding digraphs. The preference matrix, in contrast to the adjacency matrix, contains elements 1/2 for equivalent alternatives. The algorithm for constructing a non-contradictory aggregate relation contains the following steps. 1. Construction of a weighted majority digraph G = (A, p∑). The adjacency matrix R_ς = ∖r∑∖ of the majority digraph is constructed on the basis of the matrix of total m preferences PΣ = P^k according to the majority rule k=1 rij = ¹₀^,_, " P^ij P^ji, where p_ij are the elements of the matrix P∑. if pij < pji, m The weights on the digraph arcs lij = (p_i^k_j -p_j^k_i) characterize the degree of superior- _k=1^{ij ji} ity of alternative a_i over a_j∙ and are used to destroy contradictory cycles (P^k = ∖∖p^kj ∣∣; 1. j = 1, . . . , n). 2. The destruction of contradictory cycles. Arcs are removed from the cycles that have a minimum weight (with minimal advantage in expert preferences) and belong to the asymmetric part of the relation. In this case, arcs connecting equivalent alternatives are saved. We get a digraph G' = (A, ρ}, R is the adjacency matrix. 3. Construction of aggregated quasi-order p. The adjacency matrix of an aggregate quasi-order is found by the formula R = E V Tr R, where Tr R is the adjacency matrix of the transitive closure of the relation ρ without contradictory cycles. The propositions about the uniqueness and non-contradictory of the constructed aggregated relation p are proved. The computational complexity of the algorithm is O(n³). Based on the constructed aggregated quasi-order relation, the ranking of alternatives is carried out. For this purpose, an algorithm for constructing digraph preference levels has been developed. The algorithm is based on the Demukron procedure of partitioning a digraph without contours into levels N0, N1, . . . , Nt, where k-1 k-1 No = {ai : ai ∈ A, Γai = 0}; Nk = {ai : ai ∈ ANj, Γai Nj}, k = 1,...,t. j=0 j=0 The propositions that allow to modify the Demukron procedure for partitioning into preference levels of an arbitrary digraph are proved. In this case, the condition that equivalent alternatives belong to the same level of preference is satisfied. Using this algorithm, it is possible in particular to build a nonstrict ranking of alternatives. The developed technique can be used to solve multi-criteria problems in case of verbal information about pairwise comparison of alternatives according to the quality criteria.