View source for Tit-For-Tat & EigenTrust Incentives

= Problem =
File-sharing networks like KaZaA and [[Gnutella]] have popularized the peer-to-peer (P2P) resource sharing model. Based on the altruistic behaviour of its users, principles of P2P systems sometimes conflict user's rational individuality. The individual's utility function is also influenced by negative factors like e.g. upload costs, limited upload bandwidth, enviousness or egoism. Hence some users use P2P networks without sharing own resources (free-riding).

= Incentive systems =

== Point incentive system ==

Simple point incentive mechanisms as in e.g. the [[The Maze Peer-To-Peer System|Maze]]-network don't prevent users from cheating. Two kinds of user collusion are observed. 
*'''Pair-wise collusion'''
:Two users mutually exchange large amounts of data to increase their points. This kind of collusion profits from the rule that uploading earns more points that downloading consumes.

*'''Spam account collusion'''
:A user registers a number of spam-accounts to download from his main-account. Thus he transfers initial points given to new accounts to his main-account.

== EigenTrust ==

EigenTrust is an incentive system based on traffic history of each peer. Uploading data to peer A increases the reputation of peer B from peer A's perspective. The reputation between all peers can be pictured using a trustmatrix <math>M</math> with elements <math>c_{i,j}</math>. <math>c_{i,j}</math> is peer ''j'' 's rank from ''i'' 's perspective related to normalized download volumes that ''i'' has received from ''j'' during a certain time period. In order to increase its local view of reputation, each peer takes into account his friends view (<math>M^2</math>). Thus the coverage of the rank matrix gets larger and it becomes less sparse. Continuing this step to its extreme (<math>M^{\infty}</math>), each column of <math>M</math> consists of the same values (= EigenTrust-vector), meaning that each peer has the same global view to other peers.    
{| style="float:center; background:transparent; padding:0px; margin:0px;"
|[[Image:trustmatrix.jpg|thumb|center|300px|Downloadtraffic s mapped to a Trustmatrix M]]
|-
|}
A peer with large global reputation (EigenRank) gets higher download bandwidth and less latency. Moreover, peers with large EigenRank are preferred to download from.

=== Simulation Results ===
Examined in [[The_Maze_Peer-To-Peer_System|Maze-P2P-Network]], EigenTrust helped to punish colluding peers by branding them with low EigenRank. However, there are also some misinterpration. 
High reputation peers (super peers), which randomly download from "spam"-accounts, boost the EigenRank of these colluding peers. 
On the other hand, peers inside satellite clusters like university networks are unfairly punished. A university network as a whole consumes by downloading much more than it uploads. Neglecting and underestimating internal cluster traffic, EigenTrust underrates cluster peers EigenRank.

== Tit-for-Tat ==
Solving satellite cluster problem requires that peers utilize personalized rankings. A simple approach is the private history based Tit-for-Tat. Peers rank their neighbors by normalized download traffic during a certain time period. Thus, future up- and download traffic is influenced by private experience, giving higher priority to "generous" peers.

=== Simulation Results ===
Used in large scaled networks like [[The_Maze_Peer-To-Peer_System|Maze]], Tit-for-Tat suffers from its small coverage. Even with long private history only a tiny percentage of peers is known to a user. Hence the majority are "blind" uploads, which bring a lot of opportunity to free-riders. This encourage peers to use "spam"-accounts than establishing long term trust relations.



= Links =
* [http://research.microsoft.com/asia/dload_files/group/system/2006/Lian-maze06.pdf Robust Incentives via Multilevel Tit-For-Tat]