Targeted Negative Campaigning: Complexity and Approximations

Avishai Zagoury, Orgad Keller, Avinatan Hassidim, Noam Hazon

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

Given the ubiquity of negative campaigning in recent political elections, we find it important to study its properties from a computational perspective. To this end, we present a model where elections can be manipulated by convincing voters to demote specific non-favored candidates, and study its properties in the classic setting of scoring rules. When the goal is constructive (making a preferred candidate win), we prove that finding such a demotion strategy is easy for Plurality and Veto, while generally hard for t-approval and Borda. We also provide a t-factor approximation for tapproval for every fixed t, and a 3-factor approximation algorithm for Borda. Interestingly enough—following recent trends in political science that show that the effectiveness of negative campaigning depends on the type of candidate and demographic—when assigning varying prices to different possible demotion operations, we are able to provide inapproximability results. When the goal is destructive (making the leading opponent lose), we show that the problem is easy for a broad class of scoring rules.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيف35th AAAI Conference on Artificial Intelligence, AAAI 2021
ناشرAssociation for the Advancement of Artificial Intelligence
الصفحات5768-5778
عدد الصفحات11
رقم المعيار الدولي للكتب (الإلكتروني)9781713835974
حالة النشرنُشِر - 2021
الحدث35th AAAI Conference on Artificial Intelligence, AAAI 2021 - Virtual, Online
المدة: ٢ فبراير ٢٠٢١٩ فبراير ٢٠٢١

سلسلة المنشورات

الاسم35th AAAI Conference on Artificial Intelligence, AAAI 2021
مستوى الصوت6B

!!Conference

!!Conference35th AAAI Conference on Artificial Intelligence, AAAI 2021
المدينةVirtual, Online
المدة٢/٠٢/٢١٩/٠٢/٢١

بصمة

أدرس بدقة موضوعات البحث “Targeted Negative Campaigning: Complexity and Approximations'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا