Accurate algorithms for identifying the median ranking when dealing with weak and partial rankings under the Kemeny axiomatic approach
Accurate algorithms for identifying the median ranking when dealing with weak and partial rankings under the Kemeny axiomatic approach
复制标题
DOI：
10.1016/j.ejor.2015.08.048
复制
发表时间：
2016-03-01
影响因子：
6.4
通讯作者：
Siciliano, R.
中科院分区：
文献类型：
--
作者：
Amodio, S.;D'Ambrosio, A.;Siciliano, R.
偏好排名几乎出现在所有科学领域（政治科学，行为科学，机器学习，决策等）。众所周知的社会选择问题在于试图找到一个合理的程序，使用受试者表达的总体偏好或排名来达成集体决策。这相当于从数据中估计共识（中心）排名，并且已知这是一个NP难问题。Emond和Mason在2002年通过Kemeny和Snell公理框架内的分支定界算法（BB）提出了一个有用的解决方案。事实上，当问题的复杂性变得难以处理时，BB是一个时间要求很高的过程，即大量的对象，具有弱和部分排名，存在低程度的共识。作为替代方案，我们提出了一个准确的启发式算法称为FAST，找到至少一个的共识排名解决方案，BB节省了大量的计算时间。此外，我们表明，FAST的构建块是一个算法，称为QUICK，发现已经BB的解决方案之一，使它可以被卓有成效地考虑，以加快整体搜索过程，如果对象的数量是低的。对真实的数据的仿真研究和应用表明了该方法的准确性和计算效率。(C)2015年，Elsevier B.V.和欧洲运筹学会协会（EURO）在国际运筹学会联合会（IFORS）内。All rights reserved.
Preference rankings virtually appear in all fields of science (political sciences, behavioral sciences, machine learning, decision making and so on). The well-known social choice problem consists in trying to find a reasonable procedure to use the aggregate preferences or rankings expressed by subjects to reach a collective decision. This turns out to be equivalent to estimate the consensus (central) ranking from data and it is known to be a NP-hard problem. A useful solution has been proposed by Emond and Mason in 2002 through the Branch-and-Bound algorithm (BB) within the Kemeny and Snell axiomatic framework. As a matter of fact, BB is a time demanding procedure when the complexity of the problem becomes untractable, i.e. a large number of objects, with weak and partial rankings, in presence of a low degree of consensus. As an alternative, we propose an accurate heuristic algorithm called FAST that finds at least one of the consensus ranking solutions found by BB saving a lot of computational time. In addition, we show that the building block of FAST is an algorithm called QUICK that finds already one of the BB solutions so that it can be fruitfully considered to speed up even more the overall searching procedure if the number of objects is low. Simulation studies and applications on real data allows to show the accuracy and the computational efficiency of our proposal. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.