And if they can do that by, say, copying the ratings of an informative person,

and it's even this problem of separating gets even harder.

So whereas with just separating informative from uninformative raters,

we have to throw away the first few items

to separate the deliberate cheaters from the informative raters.

We would actually have to in some sense throw away the first few items

where they gave new, novel information that they couldn't have

gotten by copying anybody else and that starts to be quite a tall order.

So and I've done this in the very specific setting, but

we actually are able to prove a much more general theorem that says.

Any algorithm that is (n,c) robust, that is, preventing an attacker's

from doing more than (c) bits of damage, has to throw away at least this

omega( n log(n/c)) bits of information from the good people.

All right, you started by asking what can we do about it?

And I'm sort of saying well, we can't perfectly do anything,

we can't perfectly solve it.

And when we finish this maybe we can talk a little bit about some other things

that I know have been, we found,

other researchers have found on TripAdvisor reviews.

But we're not going to be able to perfectly do this,

given that there's this fundamental tradeoff.

What can we do?

Well, we can tradeoff, if we get better at keeping

the attackers from making fake accounts, by charging them for

accounts, or having CAPTCHA's that actually work, or something else.

We might limit then and

if we aren't worried about the attacker having more than 20 accounts, then

we only have to throw away omega of log n over c and that's small that's not so bad.

Another thing we can do is allow the attackers to have

a little bit more damage.

This log n over c, if c gets bigger

then we don't have to throw away as much information from the good guys.

Well, why is it okay to allow the attackers to do more damage maybe we have

some ways of recovering.