Exact algorithms for weighted and unweighted Borda manipulation problems

DOI10.1016/J.TCS.2016.02.003MaRDI QIDQ5964076zbMATH OpenOpenAlexFDO

Authors Yongjie Yang, Jiong Guo

Publication date 26 February 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.3145

zbMATH Keywords

exact algorithmcomputational social choicesingle-peaked electionsBorda manipulation

Mathematics Subject Classification ID

Social choice (91B14) Analysis of algorithms and problem complexity (68Q25) Voting theory (91B12)

Abstract: Both weighted and unweighted Borda manipulation problems have been proved $mathcalNP$-hard. However, there is no exact combinatorial algorithm known for these problems. In this paper, we initiate the study of exact combinatorial algorithms for both weighted and unweighted Borda manipulation problems. More precisely, we propose $O^{\ast }((mcdot{2}^m{)}^{t+1})$time and $O^{\ast }(t^{2m})$timefootnote{$O^{\ast }()$ is the $O()$ notation with suppressed factors polynomial in the size of the input.} combinatorial algorithms for weighted and unweighted Borda manipulation problems, respectively, where $t$ is the number of manipulators and $m$ is the number of candidates. Thus, for $t=2$ we solve one of the open problems posted by Betzler et al. [IJCAI 2011]. As a byproduct of our results, we show that the {{unweighted Borda manipulation}} problem admits an algorithm of running time $O^{\ast }(2^{9m^{2}logm})$, based on an integer linear programming technique. Finally, we study the {{unweighted Borda manipulation}} problem under single-peaked elections and present polynomial-time algorithms for the problem in the case of two manipulators, in contrast to the $mathcalNP$-hardness of this case in general settings.

Recommendations

• A note on the complexity of manipulating weighted Schulze voting
• Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
• Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
• New Approximations for Coalitional Manipulation in Scoring Rules
• Weighted manipulation for four-candidate Llull is easy

Cites work

• A Polynomial Time Algorithm for Unidimensional Unfolding Representations
• Algorithms for the coalitional manipulation problem
• Cloning in elections: finding the possible winners
• Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
• Integer Programming with a Fixed Number of Variables
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• Manipulation of Voting Schemes: A General Result
• Minkowski's Convex Body Theorem and Integer Programming
• Multivariate complexity analysis of Swap Bribery
• On Representatives of Subsets
• Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems
• Recognizing single-peaked preferences on a tree
• Stable matching with preferences derived from a psychological model
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• Studies in Computational Aspects of Voting
• The complexity of manipulative attacks in nearly single-peaked electorates
• The computational difficulty of manipulating an election
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control
• When are elections with few candidates hard to manipulate?

Cited in

(2)

• The nonmanipulative vote-deficits of voting rules
• Strategic voting in negotiating teams

This page was built for publication: Exact algorithms for weighted and unweighted Borda manipulation problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5964076)