Sunday, October 31, 2010

complexity and elections

I just read an interesting review article (Using Complexity to Protect Elections, by Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra) in the CACM on the complexity of election schemes, and various "attacks" on them, such as searching for voter manipulation opportunities. The article is aimed at a general computer-science audience, and written in quite a colourful style. It touches on a problem with this line of research, one that has bothered me since I started following its progress:
... perhaps the greatest single worry related to using NP-hardness to protect elections—a worry that applies to NP-hardness results not just about manipulation, but also about control and bribery. That worry is that NP-hardness is a worst-case theory, and it is in concept possible that NP-hard sets may be easily solved on many of their input instances even if P and NP differ.
They go on to mention the theory of average-case complexity, but it seems not to have been applied in this context. Is it ever going to be worth using a highly-artificial voting system, just to ensure that a potential manipulator gets a problem that is hard in worst case, but may generally be easy in practice? Perhaps one should look at other sources of difficulty for the manipulator, such as uncertainty about the other voters' preferences.

Added 1.11.10: Another nice survey that Ariel Procaccia pointed me to, ("AI’s War on Manipulation: Are We Winning?" by Piotr Faliszewski and Ariel D. Procaccia) — considers in more detail the problem of NP-hardness as just a worst-case problem for the manipulator, it reviews some work giving negative results, i.e. fundamental obstacles to the project of designing voting systems that are typically computationally resistant to manipulation.

1 comment:

quasimetric said...

Hey, this looks really interesting, but I removed it from the mathpsych reddit because it's not psychology-related.

Any psych-related contributions are welcome!