Complexity of computing median linear orders and variants |
| |
Institution: | 1. Norwegian University of Science and Technology (NTNU), Department of Architectural Design, History and Technology, Trondheim, Norway;2. Norwegian University of Science and Technology (NTNU), Department of Energy and Process Engineering, Trondheim, Norway;1. Business School, Shenzhen Technology University, China;2. Federation Business School, Federation University, Australia |
| |
Abstract: | Given a finite set X and a collection Π of linear orders defined on X, computing a median linear order (Condorcet-Kemenyʼs problem) consists in determining a linear order minimizing the remoteness from Π. This remoteness is based on the symmetric distance, and measures the number of disagreements between O and Π. In the context of voting theory, X can be considered as a set of candidates and the linear orders of Π as the preferences of voters, while a linear order minimizing the remoteness from Π can be adopted as the collective ranking of the candidates with respect to the votersʼ opinions. This paper studies the complexity of this problem and of several variants of it: computing a median order, computing a winner according to this method, checking that a given candidate is a winner and so on. We try to locate these problems inside the polynomial hierarchy. |
| |
Keywords: | Complexity Turing transformation NP-completeness NP-hardness polynomial hierarchy linear order Condorcet-Kemeny problem Slater problem voting theory pairwise comparison method median order linear ordering problem feedback arc set majority tournament |
本文献已被 ScienceDirect 等数据库收录! |
|