Szczegóły publikacji
Opis bibliograficzny
Using complexity to protect elections / Piotr FALISZEWSKI, Edith Hemaspaandra, Lane A. Hemaspaandra // Communications of the ACM ; ISSN 0001-0782 . — 2010 — vol. 53 no. 11, s. 74–82. — Bibliogr. s. 82
Autorzy (3)
- AGHFaliszewski Piotr
- Hemaspaandra Edith
- Hemaspaandra Lane A.
Dane bibliometryczne
| ID BaDAP | 55129 |
|---|---|
| Data dodania do BaDAP | 2010-12-01 |
| Tekst źródłowy | URL |
| DOI | 10.1145/1839676.1839696 |
| Rok publikacji | 2010 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Communications of the ACM |
Abstract
In this article, we discussed some of the main streams-control, manipulation, and bribery-in the study of how complexity can be used as a shield to protect elections (see Faliszewski et al.26 for a more technical survey). This line was started by the striking insight of Bartholdi, Orlin, Tovey, and Trick (see also Simon45 for even earlier roots) that although economics proves we cannot make manipulation impossible, we can seek to make it computationally infeasible. As we have seen, many hardness results have been obtained, as have many polynomial-time attacks. Election systems and settings vary greatly in the behaviors one can establish. It is natural to consider an election system's computational weaknesses and strengths, as one factor among many, when choosing an election system for a given task, and in particular to choose a system carefully in light of the types of attacks one most needs it to thwart. Yet the work on computational protection of elections has also energized the search for end runs around that protection, such as approximation algorithms and heuristics having provably frequent good performance, and one must also worry about such potential end runs when making one's election-system choice. This work all falls within the emerging area known as computational social choice (see Chevaleyre et al.10 for a superb survey), an area that links AI, systems, and theory within computer science, as well as economics, political science, mathematics, and operations research. Elections have been important for thousands of years, and with the current and anticipated increase of electronic agency, elections become more important- and more open to attacks- with each passing year. The current push-pull between using complexityas a shield and seeking holes in and paths around that shield is a natural, exciting part of the drama of science, and is likely to continue for decades to come as new models, techniques, and attacks are formulated and studied. This study will clearly benefit from the broadest possible participation, and we urge any interested readers-and most especially those early in their careers-to bring their own time and skills to bear on the many problems that glimmer in the young, important, challenging study of the complexity of elections. © 2010 ACM 0001-0782/10/1100 $10.00.
