کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141628 | 1489503 | 2014 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The complexity of probabilistic lobbying
ترجمه فارسی عنوان
پیچیدگی لابی احتمالاتی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی محاسباتی، پیچیدگی پارامتریک، تقریب پذیری، انتخاب اجتماعی محاسباتی،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 11, February 2014, Pages 1-21
Journal: Discrete Optimization - Volume 11, February 2014, Pages 1-21
نویسندگان
Daniel Binkele-Raible, Gábor Erdélyi, Henning Fernau, Judy Goldsmith, Nicholas Mattei, Jörg Rothe,