Szczegóły publikacji
Opis bibliograficzny
The complexity of manipulative attacks in nearly single-peaked electorates / Piotr FALISZEWSKI, Edith Hemaspaandra, Lane A. Hemaspaandra // Artificial Intelligence ; ISSN 0004-3702. — 2014 — vol. 207, s. 69–99. — Bibliogr. s. 98–99, Abstr. — Publikacja dostępna online od: 2013-12-01
Autorzy (3)
- AGHFaliszewski Piotr
- Hemaspaandra Edith
- Hemaspaandra Lane A.
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 79081 |
|---|---|
| Data dodania do BaDAP | 2014-01-24 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.artint.2013.11.004 |
| Rok publikacji | 2014 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Artificial Intelligence |
Abstract
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. (C) 2013 Elsevier B.V. All rights reserved.
