Complexity of Voting COMSOC 2008

Voting is the archetypical form of making a collective decision. As we have seen last week, there are a range of different voting rules, all either satisfying or violating various properties. Today we will concentrate on some of the computational questions that arise in the context of voting. For instance: • For a complex voting rule (think of the Dodgson rule), how do we actually compute the winner (; algorithms)? And what is the computational complexity of doing so? • The Gibbard-Satterthwaite Theorem tells us that manipulation is always possible. But how hard is it, computationally, to actually find a manipulating ballot? We will concentrate on discussing a few complexity results concerning manipulation in detail, and then give a broad overview over (some of) the other recent work in the field