Greedy Cheating Liars and the Fools who Believe Them

Evolutionary algorithms based on “tags” can be adapted to induce cooperation in selfish environments such as peer-to-peer systems. In this approach, nodes periodically compare their utilities with random other peers and copy their behavior and links if they appear to have better utilities. Although such algorithms have been shown to posses many of the attractive emergent properties of previous tag models, they rely on the honest reporting of node utilities, behaviors and neighbors. But what if nodes do not follow the specified protocol and attempt to subvert it for their own selfish ends? We examine the robustness of a simple algorithm under two types of cheating behavior: a) when a node can lie and cheat in order to maximize its own utility and b) when a node acts nihilistically in an attempt to destroy cooperation in the network. For a test case representing an abstract cooperative application, we observe that in the first case, a certain percentage of such “greedy cheating liars” can actually improve certain performance measures, and in the second case, the network can maintain reasonable levels of cooperation even in the presence of a limited number of nihilist nodes.