Exact algorithms for weighted and unweighted Borda manipulation problems
详细信息 查看全文
- 作者：Yongjie Yang yyongjie@mmci.uni-saarland.de" class="auth_mail" title="E-mail the corresponding author ; Jiong Guo ; jguo@mmci.uni-saarland.de" class="auth_mail" title="E-mail the corresponding author
- 关键词：Exact algorithm ; Computational social choice ; Borda manipulation ; Single-peaked elections
- 刊名：Theoretical Computer Science
- 出版年：2016
- 出版时间：4 April 2016
- 年：2016
- 卷：622
- 期：Complete
- 页码：79-89
- 全文大小：473 K
文摘
- •
We derive exact combinatorial algorithms for both weighed and unweighted Borda manipulation problems.
- •
We derive an FPT algorithm for the unweighted Borda manipulation problem with respect to the number of candidates.
- •
We prove that Borda manipulation with two manipulators is polynomial-time solvable in single-peaked elections.