Markus Brill: Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates
—
filed under:
Oberseminar
24.11.2009 10:15
| What |
|
|---|---|
| When |
Nov 24, 2009 from 10:15 AM to 11:45 AM |
| Where | Z1.09 (neu: L109) |
| Add event to calendar |
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
