Llull and Copeland Voting Computationally Resist Bribery and Control
| dc.creator | Faliszewski, Piotr | |
| dc.creator | Hemaspaandra, Edith | |
| dc.creator | Hemaspaandra, Lane A. | |
| dc.creator | Rothe, Joerg | |
| dc.date | 2008-09-25 | |
| dc.date | 2008-09-28 | |
| dc.date.accessioned | 2026-07-07T10:05:38Z | |
| dc.date.available | 2026-07-07T10:05:38Z | |
| dc.description | The only systems previously known to be resistant to all the standard control types were highly artificial election systems created by hybridization. We study a parameterized version of Copeland voting, denoted by Copeland^α, where the parameter αis a rational number between 0 and 1 that specifies how ties are valued in the pairwise comparisons of candidates. We prove that Copeland^{0.5}, the system commonly referred to as "Copeland voting," provides full resistance to constructive control, and we prove the same for Copeland^α, for all rational α, 0 < α< 1. Copeland voting is the first natural election system proven to have full resistance to constructive control. We also prove that both Copeland^1 (Llull elections) and Copeland^0 are resistant to all standard types of constructive control other than one variant of addition of candidates. Moreover, we show that for each rational α, 0 \leq α\leq 1, Copeland^αvoting is fully resistant to bribery attacks, and we establish fixed-parameter tractability of bounded-case control for Copeland^α. We also study Copeland^αelections under more flexible models such as microbribery and extended control and we integrate the potential irrationality of voter preferences into many of our results. | |
| dc.description | This 2008/9/28 version is the same as both the 2008/9/25 version at arxiv.org and the 2008/9/25 revision of URCS TR-2008-933, except the present version corrects a minor typo in the penultimate paragraph of Section 3 | |
| dc.identifier | https://arxiv.org/abs/0809.4484 | |
| dc.identifier | http://arxiv.org/abs/0809.4484 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/170065 | |
| dc.subject | Computer Science and Game Theory | |
| dc.subject | Computational Complexity | |
| dc.subject | Multiagent Systems | |
| dc.subject | I.2.11; F.2.2; F.1.3 | |
| dc.title | Llull and Copeland Voting Computationally Resist Bribery and Control | |
| dc.type | text |