Almost 20 years ago, I, along with my co-authors John Bartholdi and Craig Tovey, looked at the social choice (or voting theory) literature through the lens of operations research. Over and over again, we would read “we tried to figure out the winner under this rule, but it got too complicated”, or “we think A is the winner, but we are not sure”. Of course, to those trained in OR (or computer science or other related fields) this is a sure sign of some form of computational complexity. And sure enough, we found a number of NP completeness results. My two favorites are
- For a rule proposed by Charles Dodgson (aka Lewis Carroll of “Alice in Wonderland” fame), it is NP-complete to determine a winner
- there are rules for which it is easy to determine a winner, but it is hard to determine how to “manipulate” your vote by misrepresenting your preferences so as to ensure a preferred outcome.
These results were published in the social choice literature (John has a page detailing these and other results that gives complete references), where they languished for a decade or so, before being rediscovered by a generation of computer scientists and computationally minded economists. Of course, complexity theory has moved along a lot (Complexity Zoo lists 462 complexity classes) so the issues looked at are now much more subtle than our work but it is heartening to go to conferences like COMSOC and see many papers reference our early work as “foundational”. Those papers have shot up my rankings in Google Scholar!
All this started when Bartholdi came across the voting system to elect the Venetian Doge. The rules are a little complex, involving ten rounds of “voting” with some of the rounds involving choosing winners at random. From the Wikipedia article:
Thirty members of the Great Council, chosen by lot, were reduced by lot to nine; the nine chose forty and the forty were reduced by lot to twelve, who chose twenty-five. The twenty-five were reduced by lot to nine and the nine elected forty-five. Then the forty-five were once more reduced by lot to eleven, and the eleven finally chose the forty-one who actually elected the doge.
What could be the reason for such a convoluted system? We never got back to looking at the Doge, but recently Miranda Mowbray and Dieter Gollmann have examined this in a paper presented at the IEEE Computer Security Foundations Symposium. They do a very thorough analysis of the rules and discuss its effect on minority representation and other issues. But at the end, they come up with a non-mathematical argument for the approach:
Schneier [in the book Beyond Fear] has used the phrase “security theatre” to describe public actions which do not increase security, but which are designed to make the public think that the organization carrying out the actions is taking security seriously. (He describes some examples of this in response to the 9/11 suicide attacks.) This phrase is usually used pejoratively.
However, security theatre has positive aspects too, provided that it is not used as a substitute for actions that would actually improve security. In the context of the election of the Doge, the complexity of the protocol had the effect that all the oligarchs took part in a long, involved ritual in which they demonstrated individually and collectively to each other that they took seriously their responsibility to try to elect a Doge who would act for the good of Venice, and also that they would submit to the rule of the Doge after he was elected.
The US system for President is also pretty convoluted, particularly when the Supreme Court gets involved, but we have a way to go before we get to the Venetian level. But there is some level of ritual and even randomness involved, making the article more pertinent to current systems than it might first appear.