NON-CONTRADICTORY AGGREGATION OF QUASI-ORDER RELATIONS

The paper belongs to the "Collective choice" section of the ymathematical 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 majority 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 rho(1), rho(2),..., rho(m) on the set of alternatives A = {a(1), a(2),..., a(n)}. Relations will be given by the preference matrices P-1, P-2,..., P-m and the vertex adjacency matrices R-1, R-2,..., 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, rho(Sigma)>. The adjacency matrix R-Sigma = parallel to r(ij)(Sigma)parallel to of the majority digraph is constructed on the basis of the matrix of total preferences P-Sigma = Sigma(m)(k=1) P-k according to the majority rule r(ij) = {1, if p(ij) >= p(ji), 0, if p(ij) < p(ji), where p(ij) are the elements of the matrix P-Sigma. The weights on the digraph arcs l(ij) = Sigma(m)(k=1)(p(ij)(k)-p(ji)(k)) characterize the degree of superiority of alternative a(i) over a(j) and are used to destroy contradictory cycles (P-k = parallel to p(ij)(k)parallel to; i, 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, rho >, R is the adjacency matrix. 3. Construction of aggregated quasi-order (rho) over cap. The adjacency matrix of an aggregate quasi-order is found by the formula (R) over cap = E boolean OR Tr R, where Tr R is the adjacency matrix of the transitive closure of the relation rho without contradictory cycles. The propositions about the uniqueness and non-contradictory of the constructed aggregated relation (rho) over cap are proved. The computational complexity of the algorithm is O(n(3)). 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 N-0, N-1,..., N-t, where N-0 = {a(i) : a(i) is an element of A, Gamma a(i) = empty set}; N-k = {a(i) : a(i) is an element of A \ boolean OR(k-1)(j=0) N-j, Gamma a(i) subset of boolean OR(k-1)(j=0) N-j}, k = 1,...,t. 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.