The Trust Game: from Anonymity to Reputation
Professor Ioanis Nikolaidis, University of Alberta

Trust is usually seen as a pre-existing property between transacting entities. The question of how trust came to be established in the first place is usually left unspecified. There exist purely mechanistic ways to extending trust but are based on pre-existing trust to somebody else (e.g., CAs in PKI). Yet, in everyday life trust relationships are formed in a much more flexible manner and trust is established and dissolved all the time. Interestingly, identity and trust are not so strongly inter-related as one might think at first. For example, we trust people who are anonymous (or rather pseudonymous) as long as they behave in the manner that we expect them to, or have been "nice" to us in the past. In some cases trust is established when we risk transaction(s) at the benefit of collecting information (via feedback) to form a good or bad impression about a transacting peer. Mapping the maintenance of trust relationships to automated processes (protocols) adhered to by mobile wireless devices (the closest we have to ad hoc "social" devices) is a challenging task. Networks of such devices are also severely limited in terms of scalability, further limiting our options in designing appropriate protocols (we want to be frugal in terms of bandwidth). Therefore, available solutions favor peer-to-peer one-hop transactions. Starting with one such protocol, a practical anonymous P2P file sharing protocol, we will motivate the discussion about schemes for trust establishment and maintenance, we will then review some of the proposed reputation-based schemes (like CORE), provide a critique on their strengths as well as their blind spots, and also consider how societies of such devices, that rely on cooperation, survive (or not) when subjected to "noisy" observations of their peers' actions.