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
Verfasser: Yang, Yongjie
Sprache: Englisch
Erscheinungsjahr: 2015
SWD-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
Dokumentart : Dissertation
Kurzfassung: 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
SciDok-Publikation: 13-Nov-2015
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
Phdthesis_YongjieYang_MMCI_Saarland_University_2015.pdf1,69 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.