Markus Brill: Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates
—
abgelegt unter:
Oberseminar
24.11.2009 10:15
| Was |
|
|---|---|
| Wann |
24.11.2009 von 10:15 bis 11:45 |
| Wo | Z1.09 (neu: L109) |
| Termin übernehmen |
vCal
iCal
|
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
