کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6853264 | 658336 | 2014 | 31 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The complexity of manipulative attacks in nearly single-peaked electorates
ترجمه فارسی عنوان
پیچیدگی حملات دستکاری در انتخابات ریاست جمهوری تقریبا به طور یکجانبه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم و پیچیدگی، انتخاب اجتماعی محاسباتی، کنترل انتخاب / دستکاری، سیستم های چندگانه، تقریبا تک تنظیمات اوج،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
چکیده انگلیسی
Many electoral control and manipulation problems-which we will refer to in general as “manipulative actions” problems-are NP-hard in the general case. It has recently been noted that many of these problems fall into polynomial time if the electorate is single-peaked, i.e., is polarized along some axis/issue. However, real-world electorates are not truly single-peaked. There are usually some mavericks, and so real-world electorates tend merely to be nearly single-peaked. This paper studies the complexity of manipulative-action algorithms for elections over nearly single-peaked electorates. We do this for many notions of nearness and for a broad range of election systems. We provide instances where even one maverick jumps the manipulative-action complexity up to NP-hardness, but we also provide many instances where some number of mavericks can be tolerated without increasing the manipulative-action complexity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 207, February 2014, Pages 69-99
Journal: Artificial Intelligence - Volume 207, February 2014, Pages 69-99
نویسندگان
Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra,