رشوه خواری در رأی گیری
|کد مقاله||سال انتشار||تعداد صفحات مقاله انگلیسی||ترجمه فارسی|
|121204||2017||18 صفحه PDF||سفارش دهید|
نسخه انگلیسی مقاله همین الان قابل دانلود است.
هزینه ترجمه مقاله بر اساس تعداد کلمات مقاله انگلیسی محاسبه می شود.
این مقاله تقریباً شامل 15384 کلمه می باشد.
هزینه ترجمه مقاله توسط مترجمان با تجربه، طبق جدول زیر محاسبه می شود:
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Theoretical Computer Science, Volume 676, 9 May 2017, Pages 15-32
We show that the Frugal-bribery problem is polynomial time solvable for the k-approval, k-veto, and plurality with run off voting rules for unweighted elections. These results establish success in finding practically appealing as well as polynomial time solvable special cases of the sophisticated $Bribery and Swap-bribery problems. On the other hand, we show that the Frugal-bribery problem is NP-complete for the Borda voting rule and the Frugal-$bribery problem is NP-complete for most of the voting rules studied here barring the plurality and the veto voting rules for unweighted elections. Our hardness results of the Frugal-bribery and the Frugal-$bribery problems thus subsumes and strengthens the hardness results of the $Bribery problem from the literature. For the weighted elections, we show that the Frugal-bribery problem is NP-complete for all the voting rules studied here except the plurality voting rule even when the number of candidates is as low as 3 (for the STV and the plurality with run off voting rules) or 4 (for the maximin, the CopelandÎ± with Î±â[0,1), and the simplified Bucklin voting rules). In our view, the fact that the simplest Frugal-bribery problem becomes computationally intractable for many important voting rules (except the plurality voting rule) even with very few candidates is surprising as well as interesting.