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 to ensure the proper functioning of a democratic
society but also to investigate the increasingly important role of elections in
areas such as collaborative decisionmaking, artificial intelligence, and
recommendation systems on websites.
So the question of how to fix an election is of some concern. However, one recent
key insight is that it is possible to design election systems that make this
kind of rigging NP-hard.
Advertisement
(By fixing, computer scientists mean either the blatant adding and deleting
of votes/candidates or a more subtle strategy in which groups of voters change
their allegiances to achieve a specific goal.)
This story is only available to subscribers.
Don’t settle for half the story.
Get paywall-free access to technology news for the here and now.
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 defense 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