Technology Review Feed - arXiv blog /////////////////////////////////////////// How to fix an election Posted: 20 Sep 2009 09:10 PM PDT http://feedproxy.google.com/~r/arXivblog/~3/cnS1ZKdcUIg/click.phdo Manipulating election results may not be as hard as previously thought In recent years, computer scientists have begun an aggressive program to study elections using both theoretical models and agent-based simulations. Their motivation is not just that elections are crucial for the proper functioning of a democratic society but that elections are playing an increasingly important role for things like collaborative decision-making, artificial intelligence and recommendation systems on websites. So the question of how to fix an election is of some concern. However, one of the recent key insights is that it is possible to design election systems that make this kind of rigging NP-hard. (By fixing, computer scientists mean either the blatant adding and deleting of votes/candidates or the more subtle strategy in which groups of voters change their allegiances to achieve a specific goal.) This result gives succor to those who worry that elections can easily be fixed. What it means is that rigging is so complex that it is computationally impractical to achieve. It's as if the election has a built-in shield that prevents fixing. Now Piotr Faliszewski from the AGH University of Science and Technology in Poland and a few buddies say they have found a special case in which this protection vanishes. The special case is in elections where the vote is dominated by a single issue such as war or economics. This is known as a single-peakedness. And the worry is that it may be a common feature of human elections. In fact, many political institutions seem designed to achieve single-peakedness and so may be more vulnerable to manipulation than we imagined. But it by no means guarantees it. One potential weakness of Faliszewski and co's approach is that while many human elections are dominated by a single issue such as defence or taxes, there are always a few extreme individuals whose vote is determined by some other issue such as the sex of the candidates or the color of their skin. It may be that these extreme individuals protect the veracity of elections by ensuring that the single-peak weakness does not apply. Faliszewski and co are working on their idea to see if it can be extended to elections that are almost single-peaked. Until then, we can but wonder that we may end up relying on extremists to make our elections more robust. Ref: http://arxiv.org/abs/0909.3257: The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control -- You are subscribed to email updates from "Technology Review Feed - arXiv blog." To stop receiving these emails, you may unsubscribe now: http://feedburner.google.com/fb/a/mailunsubscribe?k=118r9-S4Z0vJg-AkQPASPmDm... Email delivery powered by Google. Google Inc., 20 West Kinzie, Chicago IL USA 60610 ----- End forwarded message ----- -- Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE