Szczegóły publikacji
Opis bibliograficzny
The complexity of losing voters / Tomasz Perek, Piotr FALISZEWSKI, Maria Silvia Pini, Franscesca Rossi // W: AAMAS 2013 [Dokument elektroniczny] : proceedings of the 12th international conference on Autonomous Agents and Multiagent Systems : May, 6–10, 2013, Saint Paul, Minnesota, USA / eds. Takayuki Ito, [et al.]. — Wersja do Windows. — Dane tekstowe. — [USA] : International Foundation for Autonomous Agents and Multiagent Systems, cop. 2013. — Dysk Flash. — e-ISBN: 978-1-4503-1993-5. — S. 407–414. — Wymagania systemowe: Adobe Reader. — Bibliogr. s. 414, Abstr.
Autorzy (4)
- AGHPerek Tomasz
- AGHFaliszewski Piotr
- Pini Maria Silvia
- Rossi Francesca
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 74633 |
|---|---|
| Data dodania do BaDAP | 2013-08-09 |
| Rok publikacji | 2013 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencja | International Joint Conference on Autonomous Agents and Multiagent Systems 2013 |
Abstract
We consider the scenario of a parliament that is going to vote on a specific important issue. The voters are grouped in parties, and all voters of a party vote in the same way. The expected winner decision is known, because parties declare their intentions to vote, but before the actual vote takes place some voters may leave the leading party to join other parties. We investigate the computational complexity of the problem of determining how many voters need to leave the leading party before the winner changes. We consider both positional scoring rules (plurality, veto, k-approval, k-veto, Borda) and Condorcet-consistent methods (maximin, Copeland), and we study two versions of the problem: a pessimistic one, where we want to determine the maximal number of voters that can leave the leading party without changing the winner; and an optimistic one, where we want the minimal number of voters that must leave the leading party to be sure the winner will change. These two numbers provide a measure of the threat to the expected winner, and thus to the leading party, given by losing some voters. We show that for many positional scoring rules these problems are easy (except for the optimistic version with k-approval, for k at least 3, and Borda). Instead, for Condorcet-consistent rules, they are both computationally difficult, with both Maximin and Copeland. Copyright © 2013, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
