The Complexity of Probabilistic Lobbying

Details The Complexity of Probabilistic Lobbying The Complexity of Probabilistic Lobbying

2009-06-24

arxiv.org/abs/0906.4431v4

Computer Science

Computational Complexity

35 pages

Scientific paper

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 in a stochastic environment, 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.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Probabilistic Lobbying does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of Probabilistic Lobbying, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Probabilistic Lobbying will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-105782