The complexity of probabilistic lobbying

DOI10.1016/j.disopt.2013.10.003zbMath1506.91049OpenAlexW2569303878WikidataQ59864911 ScholiaQ59864911MaRDI QIDQ1662102

Daniel Binkele-Raible, Jörg Rothe, Gábor Erdélyi, Nicholas Mattei, Henning Fernau, Judy Goldsmith

Publication date: 17 August 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2013.10.003

zbMATH Keywords

computational complexitycomputational social choiceparameterized complexityapproximability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Voting theory (91B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)

Related Items (8)

Complexity of control in judgment aggregation for uniform premise-based quota rules ⋮ How hard is safe bribery? ⋮ Weighted partial order oriented three-way decisions under score-based common voting rules ⋮ Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules ⋮ On the complexity of bribery and manipulation in tournaments with uncertain information ⋮ Local distance constrained bribery in voting ⋮ Approximation and hardness of shift-Bribery ⋮ Frugal bribery in voting

Uses Software

• Paramils
• SATzilla

Cites Work

• Parameterizing by the number of numbers
• The complexity of Kemeny elections
• Algorithms for the coalitional manipulation problem
• Dichotomy for voting systems
• On the complexity of bribery and manipulation in tournaments with uncertain information
• Anyone but him: the complexity of precluding an alternative
• Voting schemes for which it can be difficult to tell who won the election
• Single transferable vote resists strategic voting
• How hard is it to control an election?
• A heuristic technique for multi-agent planning
• Exact complexity of the winner problem for Young elections
• On the approximability of Dodgson and Young elections
• The all-pay auction with complete information
• The computational difficulty of manipulating an election
• The Turing way to parameterized complexity
• On complexity of lobbying in multiple referenda
• Parametrized complexity theory.
• Computational Aspects of Approval Voting
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
• Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
• Copeland Voting Fully Resists Constructive Control
• When are elections with few candidates hard to manipulate?
• The Complexity of Probabilistic Lobbying
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• How Hard Is Bribery in Elections?
• ParamILS: An Automatic Algorithm Configuration Framework
• Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
• Exact analysis of Dodgson elections
• A formal theory of lobbying behaviour
• A Richer Understanding of the Complexity of Election Systems
• Efficient probabilistically checkable proofs and applications to approximations
• Partial vs. Complete Domination: t-Dominating Set
• Financial Cryptography and Data Security
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of probabilistic lobbying