2009/06/24 by Daniel Binkele-Raible, Gábor Erdélyi, Binkele-Raible, Daniel +9
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #cs.CC
paper · pdf · doi:10.48550/arxiv.0906.4431
35 pages
openalex publication_date 2009/06/24 · arxiv created 2011/02/26 · arxiv updated 2011/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.