عنوان انگلیسی مقاله:
A new approach for identifying the Kemeny median ranking
ترجمه فارسی عنوان مقاله:
یک روش جدید برای شناسایی رتبه بندی متوسط Kemeny
Sciencedirect - Elsevier - European Journal of Operational Research, 281 (2020) 388-401: doi:10:1016/j:ejor:2019:08:033
Condorcet consistent rules were originally developed for preference aggregation in the theory of social choice. Nowadays these rules are applied in a variety of fields such as discrete multi-criteria analysis, defence and security decision support, composite indicators, machine learning, artificial intelligence, queries in databases or internet multiple search engines and theoretical computer science. The cycle issue, known also as Condorcets paradox, is the most serious problem inherent in this type of rules. Solutions for dealing with the cycle issue properly already exist in the literature; the most important one being the identification of the median ranking, often called the Kemeny ranking. Unfortunately its identification is a NP-hard problem. This article has three main objectives: (1) to clarify that the Kemeny median order has to be framed in the context of Condorcet consistent rules; this is important since in the current practice sometimes even the Borda count is used as a proxy for the Kemeny ranking. (2) To present a new exact algorithm, this identifies the Kemeny median ranking by providing a searching time guarantee. (3) To present a new heuristic algorithm identifying the Kemeny median ranking with an optimal trade-off between convergence and approximation .
Keywords : Decision analysis | Combinatorial optimisation | Social choice| Multiple criteria | Artificial intelligence| Defence and security| Big data