Digg is a collaborative news site, much like Slashdot, where people post articles that seem interesting and topical. Through a voting scheme, articles get "dugg", and rise to the top of the site. In fact, getting "dugg" is now an inadvertent denial-of-service attack much like being "slashdotted" used to be.
The problem is that people attempt to game the system to bump up traffic to their sites, by forming voting coalitions, making fake accounts, etc etc. Needless to say, there can often be real money (in the form of advertising) behind this, so there's a lot of incentive to cheat the system.
This is not a new problem; Google and other search engines have battled search engine optimizers for a long time now. There are companies that claim to improve your location in a Google search result (for a small fee of course). An interesting side effect of all this gamesmanship is that search engines like Google and aggregators like Digg have to keep many details of their ranking process secret. Obviously, some of this is for IP protection, but protecting against vote riggers is also a major concern. A tertiary consequence of this lack of transparency is that such sites are now vulnerable to lawsuits by disgruntled sites complaining about bias in search results; Google has had to fend off lawsuits based on some claim of bias leading to monetary damage.
The latest such problem has hit Digg, where in an attempt to block out users trying to game votes on articles they want to push, the management has managed to freeze out and frustrate some of the most prolific users. A user-driven site like Digg that has many competitors can't really afford to be annoying its most valuable contributors.
So (finally), here's the technical question. Although Arrow's theorem tells us that in general, voting schemes can always be defeated, I don't know if the result is constructive. In other words, even if there is a voting strategy that can break one of the criteria for a reasonable voting scheme, it may not be easy to find such a scheme.
So, in the spirit of RSA, is there a way of designing a voting scheme that can be published (thus addressing issues of transparency), but is computationally intractable to game ? Any cryptographers know if this has been studied ?
Vince Conitzer has done some work in this area. If I remember correctly, it is possible to design voting schemes that are hard to manipulate in the worst case, but it is impossible to design schemes that are hard to manipulate "on average". See for example http://www.cs.cmu.edu/~conitzer/nonexistenceAAAI06.pdf
ReplyDeleteIt would be interesting to have something based on a cryptographic assumption and not NP-hardness.
Posted by Shuchi Chawla
Yes, a cryptographic assumption would work just fine. On a related note, what kinds of cryptographics assumptions *are* there that are weaker than NP hardness ?
ReplyDeletePosted by Suresh
hah! some prognosticator you are. This device already exists !
ReplyDeleteTouch Screen Hopping in Florida
Posted by Suresh
I think there may be a little bit of confusion between the different problems in constructing voting schemes:
ReplyDeleteArrow's theorem is a statement about the impossibility of finding a reasonable voting scheme that doesn't admit "paradoxes" (e.g., when using majority as the voting function: most voters can prefer A to B, B to C and C to A simultaneously). Arrow's theorem doesn't say anything about gaming a specific voting system (as in trying to bias it in favor of some candidate), or anything about "secure" implementations.
When constructing a voting protocol, usually the function is already known (e.g., plurality), and the problem is in securely implementing a computation of this function.
For internet sites such as digg, the most significant problem is identification: it's almost impossible to make sure every human is voting only once (or only as him/herself). Note that cryptography can't really solve this problem for sites which allow anyone to vote: one person can always pretend to be two or more people (although cryptography can help prevent automated cheaters using things like CAPTCHAs).
For "real-life" voting, identification is also a problem, but most of the cryptographic effort has gone into providing methods for "universal verifiability" (so any voter can verify that her vote was both cast and tallied according to her wishes) while still preserving ballot secrecy (in fact an even stronger "receipt-freeness" property is usually required, in order to prevent vote-buying and coercion). In this case there are quite a number of systems that use cryptography to prevent voters from cheating (see, for example, Chaum's scheme and Neff's scheme)
The game-theoretic version of "gaming" (systems where it is advantageous to falsely report your preference in order to bias the result) is far less studied, AFAIK. IIRC, there was some proof that deterministic systems can always be gamed in this way, but there are some probabilistic systems that cannot (a trivial example is to pick a voter at random and use only her choice).
P.S. for whoever's interested -- almost all cryptographic assumptions seem to be weaker than NP-hardness. In particular, there is some evidence that one-way functions (the most basic cryptographic assumption) cannot be based on P<>NP.
Posted by Aspiring Cryptographer
I'll ditto Aspiring Cryptographer. The real problem with manipulation at Digg is that it is trivial to add more users to vote for your preferred story. Bartholdi, Tovey, and Trick ("How Hard is it to Control an Election"), showed that this would be computationally easy for plurality. I don't see this particular aspect changing in sites like Digg unless they make it a LOT harder to get an account.
ReplyDeleteAnd, right, deterministic voting systems can always be manipulated - in the sense that one gets a more preferred result by lying in their preferences - this is known as the Gibbard-Satterthwaite theorem (follows from Arrow's). Some work has been done by Conitzer and Sandholm ("How many candidates are needed to make elections hard to manipulate?") on the computational difficulty of manipulation. For plurality it is always in P to do so, but for many voting systems it is NP-complete over three candidates.
Posted by eric
Aspiring cryptographer: just a language point, but I believe most people would say standard crypto assumptions are *stronger* than the assumption of worst-case hardness of NP-complete problems. It's the plausibility of those assumptions that's weaker.
ReplyDeletePosted by Andy D
designing search result
ReplyDeleteHere's some useful info on designing search result
which you might be looking for. The url is: http://www.jaldisearch.com/
Posted by shiv
hi suresh and others. If you are interested in tamper-proof voting systems, have a look at www.cd3wd.com/SEEV/ - this system is so good it was banned from a washington DC Global Electoral Organisation Conference March 2007. Best regards, mr alex weir, Guinea Conakry and Harare
ReplyDelete