Charles Dodgson (better known by his pen name, Lewis Carroll) suggested an appealing voting system in 1876. Unfortunately, at the time Dodgson did not take into account such futuristic considerations as computational complexity, and, as it turned out more than a century later, computing the Dodgson score of a candidate is NP-hard.
I will present two very different approximation algorithms, as well as inapproximability results, for the Dodgson score and a related problem, the Young score. I will also try to position this work in the context of a wider agenda: studying the desirability of approximation algorithms as voting rules. Care will be taken to present the necessary concepts from social choice theory using as many PowerPoint animations as humanly possible.
This talk is based on joint work with Ioannis Caragiannis, Jason Covey, Michal Feldman, Chris Homan, Christos Kaklamanis, Nikos Karanikolas, and Jeff Rosenschein.
Ariel Procaccia is a PhD student at the Hebrew University of Jerusalem. He is expected to graduate in October 2008, and will spend next year in the new Microsoft Research Israel Lab. He is mainly interested in algorithmic game theory and computational social choice, and has coauthored around 30 technical papers on these subjects.
Colloquia Series page.