Is there any algorithm/protocol out there to solve/mitigate the free rider problem without requiring identification?

In a web system, I want to distribute exactly one virtual dollar per day to each person, without requiring identification when a person creates an account.

A solution of mitigation, would mean for example that a specific person may get up to $2 per day (in case he created more than one account), but not much more.

The algorithm needs to distribute to every person about the same amount of money per day. So the ratio between the money distributed to every two different people per day should be around 1.


The term for the problem you seem most focused on is a Sybil attack whose typical solution is some form of identity.

Another mitigation is a proof of work system that makes account creation expensive. The goal is to have the cost of creating multiple accounts not be worth the gains. This is more effective when one needs many Sybil accounts to really benefit. Anything that made getting two accounts disincentivizingly costly, probably makes getting one account too annoying for legitimate users.

The Wikipedia page list another approach to dealing with this that is a bit interesting, and is described, for example, in "Sybil Detection via Distributed Sparse Cut Monitoring" by Aditya Kurve and George Kesidis referenced there. This, however, requires some way for the users to interact in your system (or in a system you have visibility into). In particular, it requires users to implicitly or explicitly "vouch" for other users. This graph of "vouchings for" will usually have atypical properties for subgraphs of Sybil accounts (e.g. being fully connected rather than a small-world graph).

In your context, you could attempt to use techniques similar to the fraud detection banks do and try to find patterns that suggest abuse, e.g. a bunch of users all transferring virtual currency to a single user in a short time frame.

Alternatively, and this is somewhat in line with a proof of work scheme, you can only provide this virtual payment when the user is doing the intended behavior. As a simple baseline, you may provide it only to users who are active a certain amount in the day. This also leads into to the fraud detection angle as many online games have similar systems to detect bots that are just pretending to behave like normal users.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.