the physics arXiv blog

[Technology Review Feed - arXiv blog]

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-AkQPASPmDmlGQ

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