Markus Brill: Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates
24.11.2009 10:15
For many election systems, bribery and manipulation attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. It is important to learn how robust these hardness protection results are, in order to find whether they can be relied on in practice. In this talk, we show that for voters who follow the most central political-science model of electorates—single-peaked preferences—several of those protections vanish.
Joint work with Felix Brandt, Edith Hemaspaandra, and Lane Hemaspaandra
Artikelaktionen
abgelegt unter:
Oberseminar