Bribery's Influence on Ranked Aggregation
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910085662375936 |
|---|---|
| author | Jain, Pallavi Thakur, Anshul |
| author_facet | Jain, Pallavi Thakur, Anshul |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_28574 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Bribery's Influence on Ranked Aggregation Jain, Pallavi Thakur, Anshul Computer Science and Game Theory Computational Complexity 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. |
| title | Bribery's Influence on Ranked Aggregation |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2603.28574 |