December 16, 2008
Manipulating online voting
Is online anonymous (or at least, unauthenticated) voting ever a good idea? When there is no authentication, voters who care can go to the ballot box multiple times. And with scripted robots, won't voting become completely meaningless?
Perhaps. It appears that is more or less the case with the NHL All Star game balloting this year.
There has been a huge discussion about this in the blogosphere (see, e.g., the summary with links by NY Times blogger Stu Hackel). As reported in the "traditional" pages of the NYT, ballot stuffing has, of course, been known to occur as long as fan voting has been around, but this year it rose to new levels when fans started posting robot scripts and at least one (Pittsburgh) team executive started exhorting fans to get out the text messaging vote. At one point two players who had seen zero ice time this year were closing in on starting positions in the All Star game.
Online balloting is cheap, accessible, and participatory. But can it be made to work? What sort of incentives can be designed that lead to reliable results when secure authentication is not required?
One recent very interesting research paper on this topic is by Liad Wagman and Vince Conitzer (PhD candidate and Asst Prof. at Duke). (For more permanent reference, the paper was published in the proceedings of the AAAI 2008 conference, where it won a "Best Paper" award.) Their results are fairly limited and not yet applicable to real settings, but it is a key step forward. Their main insight is that if there is some cost to voting, then as the number of voters becomes large it may be possible to design a voting rule under which it is not in anyone's interest to vote multiple times.
Imposing a small cost on honest participants to screen out the dishonest is not a new idea in the broad area of incentive-centered design (Rick Wash and I have shown that it is a fundamental strategy realized in widely varying information system applications, such as passwords and CAPTCHAs, and of course, it's an application of screening and signaling theory, which goes back to at least Spence's seminal paper for which he won the Nobel Prize), but this is the first rigorous study of the idea in the area of online voting, to the best of my knowledge.
Unfortunately the Wagman-Conitzer results so far are somewhat negative when there are more than 3 alternatives (as, for example, is the case in sports all-star balloting) or when individuals can collude and act as a group. By casual intuition it is not surprising this problem is so hard. More work to be done.
This is too good to pass up. Today, one day after writing the above article, I received in my email an official mailing from the Detroit Red Wings, urging me (in traditional Chicago fashion), to help out: