The complexity of probabilistic lobbying

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

19 Scopus citations


We propose various models for lobbying in a probabilistic environment, in which an actor (called "The Lobby") seeks to influence the 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 three 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 in a stochastic environment, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria. 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 (in)approximability results.

Original languageEnglish
Title of host publicationAlgorithmic Decision Theory - First International Conference, ADT 2009, Proceedings
Number of pages12
StatePublished - 2009
Event1st International Conference on Algorithmic Decision Theory, ADT 2009 - Venice, Italy
Duration: Oct 20 2009Oct 23 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5783 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference1st International Conference on Algorithmic Decision Theory, ADT 2009

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 .

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)


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

Cite this