... 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:
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!
Post a Comment