Speaker: Arkadii Slinko (University of Auckland, New Zealand)
Time and Place: 17 November 2006, 10:00am, 4369HP, Carleton University
Title: Optimal Lobbying in Multiple Referenda

Abstract: We show that lobbying in conditions of ``direct democracy'' is virtually impossible, even in conditions of complete information about voters preferences, since it would require solving a very computationally hard problem. We use the apparatus of parametrized complexity for this purpose. We envision that computational complexity may play a positive role in voting, protecting the integrity of social choice. Such a role would resemble the situation in public-key cryptography, where computational complexity protects the privacy of communication. As far as we know, this is the first paper which considers applications of parametrized complexity to social choice.