THE COMPLEXITY OF MANIPULATING κ-APPROVAL ELECTIONS

Andrew Lin

2011

Abstract

An important problem in computational social choice theory is the complexity of undesirable behavior among agents, such as control, manipulation, and bribery in election systems, which are tempting at the individual level but disastrous for the agents as a whole. Creating election systems where the determination of such strategies is difficult is thus an important goal. An interesting set of elections is that of scoring protocols. Previous work in this area has demonstrated the complexity of misuse in cases involving a fixed number of candidates, and of specific election systems on unbounded number of candidates such as Borda. In contrast, we take the first step in generalizing the results of computational complexity of election misuse to cases of infinitely many scoring protocols on an unbounded number of candidates. We demonstrate the worst-case complexity of various problems in this area, by showing they are either polynomial-time computable, NP-hard, or polynomial-time equivalent to another problem of interest. We also demonstrate a surprising connection between manipulation in election systems and some graph theory problems.

Paper Citation

in Harvard Style

Lin A. (2011). THE COMPLEXITY OF MANIPULATING κ-APPROVAL ELECTIONS . In Proceedings of the 3rd International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, ISBN 978-989-8425-41-6, pages 212-218. DOI: 10.5220/0003168802120218

in Bibtex Style

@conference{icaart11,
author={Andrew Lin},
title={THE COMPLEXITY OF MANIPULATING κ-APPROVAL ELECTIONS},
booktitle={Proceedings of the 3rd International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,},
year={2011},
pages={212-218},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003168802120218},
isbn={978-989-8425-41-6},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 3rd International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,
TI - THE COMPLEXITY OF MANIPULATING κ-APPROVAL ELECTIONS
SN - 978-989-8425-41-6
AU - Lin A.
PY - 2011
SP - 212
EP - 218
DO - 10.5220/0003168802120218