Bribery's Influence on Ranked Aggregation
This addresses computational complexity issues in social choice theory for researchers, but it is incremental as it builds on known hardness results.
The paper tackles the problem of manipulating rankings to achieve a desired Kemeny Score, showing that it can be solved in polynomial time for various manipulation actions, whereas similar manipulations are computationally hard for Kemeny Consensus.
Kemeny Consensus is a well-known rank aggregation method in social choice theory. In this method, given a set of rankings, the goal is to find a ranking $Î $ that minimizes the total Kendall tau distance to the input rankings. Computing a Kemeny consensus is NP-hard, and even verifying whether a given ranking is a Kemeny consensus is coNP-complete. Fitzsimmons and Hemaspaandra [IJCAI 2021] established the computational intractability of achieving a desired consensus through manipulative actions. Kemeny Consensus is an optimisation problem related to Kemeny's rule. In this paper, we consider a decision problem related to Kemeny's rule, known as Kemeny Score, in which the goal is to decide whether there exists a ranking $Î $ whose total Kendall tau distance from the given rankings is at most $k$. Computation of Kemeny score is known to be NP-complete. In this paper, we investigate the impact of several manipulation actions on the Kemeny Score problem, in which given a set of rankings, an integer $k$, and a ranking $X$, the question is to decide whether it is possible to manipulate the given rankings so that the total Kendall tau distance of $X$ from the manipulated rankings is at most $k$. We show that this problem can be solved in polynomial time for various manipulation actions. Interestingly, these same manipulation actions are known to be computationally hard for Kemeny consensus.