Replacing impossibility by infeasibility

One of the great conceptual breakthroughs in cryptography was the idea that an impossibility - this code cannot be cracked - can be replaced by infeasibility - this code is computationally hard to crack - with great success. Indeed, the notion that all you need to do is fool a computationally bounded adversary is at the core of derandomization.

It's an idea that transcends theoryCS - that you can model entities by computationally bounded objects, and can then prove interesting things about them that you couldn't have done if the entity was all powerful. And it's realistic ! As long as you're willing to believe in the effective variant of the Church-Turing thesis (all effective computations are in BPP; we'll pretent quantum computing doesn't exist for now), then it accurately models any computational entity you can choose to build.

Which brings us to social choice and voting theory. As you may well be aware, Arrow's theorem is a rather depressing impossibility result for designing a "fair" election. Either you lose some nice property (no dictatorship!), or some adversary can find a way to beat the system another way. But given all of the above, a more plausible question one might ask is: can a computationally bounded adversary crack an election ? (Disclaimer: I have no evidence that Diebold is a computationally bounded adversary; it certainly has no resource constraints)

What got my attention were two new papers on the arxiv, one by Faliszewski, Hemaspaandra, and Hemaspaandra, and the other by Hemaspaandra, Hemaspaandra, and Rothe.

The first paper asks the question that Katherine Harris must have surely wondered about, "How Hard Is Bribery in Elections?". The short answer is, "It depends", and the long answer is that depending on the type of voting scheme and who's doing the rigging (a briber or the voters themselves), the problem goes between being in P and being NP-Complete.

The second paper studies the problem of when the organizer of an election seeks to rig it:

Electoral control refers to attempts by an election's organizer (``the chair'') to influence the outcome by adding/deleting/partitioning voters or candidates.

In some circles, this is also known as the venue selection process for SODA. What the authors show is that by combining elections in a certain way, the overall election can be made resistant (i.e NP-hard) to control by the organizer.

Categories:

• research