The complexity of probabilistic lobbying

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

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

Abstract

We propose models for lobbying in a probabilistic environment, in which an actor (called "The Lobby") seeks to influence voters' preferences of voting for or against multiple issues when the voters' preferences are represented in terms of probabilities. In particular, we provide two evaluation criteria and two bribery methods to formally describe these models, and we consider the resulting forms of lobbying with and without issue weighting. We provide a formal analysis for these problems of lobbying, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria and on various natural parameterizations. Specifically, we show that some of these problems can be solved in polynomial time, some are NP-complete but fixed-parameter tractable, and some are W[2]-complete. Finally, we provide approximability and inapproximability results for these problems and several variants.

Original languageEnglish
Pages (from-to)1-21
Number of pages21
JournalDiscrete Optimization
Volume11
Issue number1
DOIs
StatePublished - Feb 2014

Bibliographical note

Funding Information:
The second and sixth authors were supported in part by DFG grants RO 1202/11-1 , RO 1202/12-1 (within the European Science Foundation’s EUROCORES program LogICCC), and RO 1202/15-1 , and the Alexander von Humboldt Foundation’s TransCoop program. The fourth and fifth authors were supported in part by NSF grants CCF-1049360 and ITR-0325063 . The second author was supported in part by National Research Foundation (Singapore) under grant NRF-RF 2009-08 and DFG grant ER 738/1-1 .

Keywords

  • Approximability
  • Computational complexity
  • Computational social choice
  • Parameterized complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'The complexity of probabilistic lobbying'. Together they form a unique fingerprint.

Cite this