کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10332775 | 687777 | 2014 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The complexity of online manipulation of sequential elections
ترجمه فارسی عنوان
پیچیدگی دستکاری آنلاین انتخابات متوالی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی محاسباتی، انتخاب اجتماعی محاسباتی، انتخابات دستکاری الگوریتم های آنلاین، اولویت ها، رأی توزیع،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Most work on manipulation assumes that all preferences are known to the manipulators. However, in many settings elections are open and sequential. We introduce a framework, in which manipulators can see the past votes but not the future ones, to model online coalitional manipulation of sequential elections, and we show that here manipulation can be extremely complex even for election systems with simple winner problems. We also show that for some of the most important election systems such manipulation is simple in certain settings. Among our highlights are: Depending on the size of the manipulative coalition, the online manipulation problem can be complete for each level of the polynomial hierarchy or even for PSPACE. We obtain the most dramatic contrast to date between the nonunique-winner and unique-winner models: Online weighted manipulation for plurality is in P in the nonunique-winner model, yet is coNP-hard (constructive case) and NP-hard (destructive case) in the unique-winner model. And we obtain what to the best of our knowledge are the first PNP[1]-completeness and PNP-completeness results in computational social choice, in particular regarding 3-candidate and 4-candidate (and unlimited-candidate) online weighted coalition manipulation of veto elections.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 80, Issue 4, June 2014, Pages 697-710
Journal: Journal of Computer and System Sciences - Volume 80, Issue 4, June 2014, Pages 697-710
نویسندگان
Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe,