Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-26628
Titel: | A deep exploration of the complexity border of strategic voting problems |
VerfasserIn: | Yang, Yongjie |
Sprache: | Englisch |
Erscheinungsjahr: | 2015 |
Kontrollierte Schlagwörter: | Kollektiventscheidung Berechnungskomplexität NP-hartes Problem Mehragentensystem |
Freie Schlagwörter: | Manipulation computational social choice complexity NP-hard voting systems manipulation multiagent systems |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Dissertation |
Abstract: | Voting has found applications in a variety of areas. Unfortunately, in a voting activity there may exist strategic individuals who have incentives to attack the election by performing some strategic behavior. One possible way to address this issue is to use computational complexity as a barrier against the strategic behavior. The point is that if it is NP-hard to successfully perform a strategic behavior, the strategic individuals may give up their plan of attacking the election.
This thesis is concerned with strategic behavior in restricted elections, in the sense that the given elections are subject to some combinatorial restrictions. The goal is to find out how the complexity of the strategic behavior changes from the very restricted case to the general case. Abstimmungen werden auf verschiedene Gebiete angewendet. Leider kann es bei einer Abstimmung einzelne Teilnehmer geben, die Vorteile daraus ziehen, die Wahl durch strategisches Verhalten zu manipulieren. Eine Möglichkeit diesem Problem zu begegnen ist es, die Berechnungskomplexität als Hindernis gegen strategisches Verhalten zu nutzen. Die Annahme ist, dass falls es NP-schwer ist, um strategisches Verhalten erfolgreich anzuwenden, der strategisch Handelnde vielleicht den Plan aufgibt die Abstimmung zu attackieren. Diese Arbeit befasst sich mit strategischem Vorgehen in eingeschränkten Abstimmungen in dem Sinne, dass die vorgegebenen Abstimmungen kombinatorischen Einschränkungen unterliegen. Ziel ist es herauszufinden, wie sich die Komplexität des strategischen Handelns von dem sehr eingeschränkten zu dem generellen Fall ändert. |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291-scidok-62914 hdl:20.500.11880/26684 http://dx.doi.org/10.22028/D291-26628 |
Erstgutachter: | Guo, Jiong |
Tag der mündlichen Prüfung: | 2-Nov-2015 |
Datum des Eintrags: | 13-Nov-2015 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
Phdthesis_YongjieYang_MMCI_Saarland_University_2015.pdf | 1,69 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.