Non-contradictory aggregation of quasi-order relations

V. N. Nefedov ; S. O. Smerchinskaya ; N. P. Yashina

Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 113-126

Résumé

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 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,\ldots ,\rho_m$ on the set of alternatives $A=\{a_1,a_2,\ldots ,a_n\}$. Relations will be given by the preference matrices $P^1,P^2,\ldots ,P^m$ and the vertex adjacency matrices $R^1,R^2,\ldots ,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=\langle A,\rho_\Sigma\rangle$. The adjacency matrix $R_\Sigma=\|r_{ij}^\Sigma\|$ of the majority digraph is constructed on the basis of the matrix of total preferences $P_\Sigma=\sum\limits_{k=1}^m P^k$ according to the majority rule $$ r_{ij}=\begin{cases} 1, & \text{if } p_{ij}\geq p_{ji},\\ 0, & \text{if } p_{ij} < p_{ji},\\ \end{cases}\, \text{where } p_{ij} \text{ are the elements of the matrix } P_\Sigma. $$ The weights on the digraph arcs $l_{ij}=\sum\limits_{k=1}^m (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=\|p_{ij}^k\|$; $i,j=1,\ldots ,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'=\langle A,\rho\rangle$, $R$ is the adjacency matrix. 3. Construction of aggregated quasi-order $\widehat{\rho}$. The adjacency matrix of an aggregate quasi-order is found by the formula $\widehat{R}=E\vee \text{Tr}\,R$, where $\text{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 $\widehat{\rho}$ 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,\ldots ,N_t$, where $$ N_0=\{a_i: a_i\in A,\ \Gamma a_i=\varnothing\};N_k=\{a_i: a_i\in A\setminus \textstyle\bigcup\limits_{j=0}^{k-1} N_j,\ \Gamma a_i\subseteq\bigcup\limits_{j=0}^{k-1} N_j\},\ k=1,\ldots ,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.

Détail

Keywords: collective choice, weighted majority graph, aggregated relation, contradictory cycle, preference levels.
Mots-clés : quasi-order

Bibliographie

[1] Larichev O., Moshkovich H., Verbal Decision Analysis for Unstructured Problems, Kluwer Acedemic Publishers, Boston, 1997, 272 pp. | MR | MR | Zbl

[2] Petrovskiy A. B., Decision Making Theory, Akademiya Publ., M., 2009, 400 pp. (in Russian)

[3] Mirkin B. G., Group Choice, V. H. Winston Sons Publ., 1979, 252 pp. | MR | MR

[4] Moulin H., Axioms of Cooperative Decision Making, Cambridge University Press, Cambridge, 1988, 348 pp. | MR | Zbl

[5] Nefyodov V. N., Osipova V. A., Smerchinskaya S. O., Yashina N. P., “Non-contradictory aggregation of strict order relations”, Russian Mathematics, 62 (2018), 61–73 | DOI | MR | Zbl

[6] Nefyodov V. N., Smerchinskaya S. O., Yashina N. P., “Constructing an aggregated relation with a minimum distance from the expert preferences”, Prikladnaya Diskretnaya Matematika, 2018, no. 42, 120–132 (in Russian)

[7] Schreider Ju. A., Equality, Resemblance and Order, Mir Publ., M., 1979, 279 pp. | MR | MR

[8] Smerchinskaya S. O., Yashina N. P., “An algorithm for pairwise comparison of alternatives in multi-criteria problems”, Intern. J. Modeling, Simulation, and Scientific Computing, 9:1 (2018) | DOI

[9] Nefedov V. N., Osipova V. A., Discrete Mathematics Course, MAI Publ., M., 1992, 262 pp. (in Russian)