Please use this identifier to cite or link to this item:
doi:10.22028/D291-26628
Title: | A deep exploration of the complexity border of strategic voting problems |
Author(s): | Yang, Yongjie |
Language: | English |
Year of Publication: | 2015 |
SWD key words: | Kollektiventscheidung Berechnungskomplexität NP-hartes Problem Mehragentensystem |
Free key words: | Manipulation computational social choice complexity NP-hard voting systems manipulation multiagent systems |
DDC notations: | 004 Computer science, internet |
Publikation type: | 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 to this record: | urn:nbn:de:bsz:291-scidok-62914 hdl:20.500.11880/26684 http://dx.doi.org/10.22028/D291-26628 |
Advisor: | Guo, Jiong |
Date of oral examination: | 2-Nov-2015 |
Date of registration: | 13-Nov-2015 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
Phdthesis_YongjieYang_MMCI_Saarland_University_2015.pdf | 1,69 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.