Local distance constrained bribery in voting

DOI10.1016/J.TCS.2020.10.005MaRDI QIDQ2215965zbMATH OpenOpenAlexFDO

Authors Palash Dey

Publication date 15 December 2020

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

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

zbMATH Keywords

algorithmvotingtheorybriberycomputational social choicelocal distance restriction

Mathematics Subject Classification ID

Social choice (91B14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Voting theory (91B12) Computational methods for problems pertaining to game theory, economics, and finance (91-08)

Abstract: Studying complexity of various bribery problems has been one of the main research focus in computational social choice. In all the models of bribery studied so far, the briber has to pay every voter some amount of money depending on what the briber wants the voter to report and the briber has some budget at her disposal. Although these models successfully capture many real world applications, in many other scenarios, the voters may be unwilling to deviate too much from their true preferences. In this paper, we study the computational complexity of the problem of finding a preference profile which is as close to the true preference profile as possible and still achieves the briber's goal subject to budget constraints. We call this problem Optimal Bribery. We consider three important measures of distances, namely, swap distance, footrule distance, and maximum displacement distance, and resolve the complexity of the optimal bribery problem for many common voting rules. We show that the problem is polynomial time solvable for the plurality and veto voting rules for all the three measures of distance. On the other hand, we prove that the problem is NP-complete for a class of scoring rules which includes the Borda voting rule, maximin, Copeland${}^{a}lpha$ for any $alphain[0,1]$, and Bucklin voting rules for all the three measures of distance even when the distance allowed per voter is $1$ for the swap and maximum displacement distances and $2$ for the footrule distance even without the budget constraints (which corresponds to having an infinite budget). For the $k$-approval voting rule for any constant $k>1$ and the simplified Bucklin voting rule, we show that the problem is NP-complete for the swap distance even when the distance allowed is $2$ and for the footrule distance even when the distance allowed is $4$ even without the budget constraints.

Recommendations

• How hard is bribery with distance restrictions?
• On the complexity of bribery with distance restrictions
• Frugal bribery in voting
• How hard is bribery in elections?
• Voting and bribing in single-exponential time

Cites work

• scientific article; zbMATH DE number 4204092 (Why is no real title available?)
• scientific article; zbMATH DE number 3584785 (Why is no real title available?)
• scientific article; zbMATH DE number 1288298 (Why is no real title available?)
• A NEW MEASURE OF RANK CORRELATION
• Approximating weighted and priced bribery in scoring rules
• Barriers to manipulation in voting
• Bribery in voting with CP-nets
• Campaign management under approval-driven voting rules
• Control and bribery in voting
• Determining possible and necessary winners given partial orders
• Frugal bribery in voting
• How hard is bribery in elections?
• Introduction to algorithms.
• Large-scale election campaigns: combinatorial shift bribery
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• Multivariate complexity analysis of Swap Bribery
• On the hardness of bribery variants in voting with CP-nets
• Prices matter for the parameterized complexity of shift bribery
• Swap bribery
• The complexity of probabilistic lobbying
• The computational difficulty of manipulating an election
• When are elections with few candidates hard to manipulate?

Cited in

(8)

• On the complexity of bribery with distance restrictions
• Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
• How hard is safe bribery?
• A parameterized perspective on protecting elections
• Distance restricted manipulation in voting
• Swap bribery
• How hard is bribery with distance restrictions?
• Frugal bribery in voting

This page was built for publication: Local distance constrained bribery in voting

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