Bounding trust in reputation systems with incomplete information

Reputation mechanisms represent a major class of techniques for managing trust in decentralized systems. Quite a few reputation-based trust functions have been proposed in the literature for use in many different application domains. However, in many situations, one cannot always obtain all of the information required by the trust evaluation process. For example, access control restrictions or high collection costs might limit one's ability to gather every possible feedback that could be aggregated. Thus, one key question is how to analytically quantify the quality of reputation scores computed using incomplete information. In this paper, we start a first effort towards answering the above question by studying the following problem: given the existence of certain missing information, what are the worst and best trust scores (i.e., the bounds of trust) a target entity can be assigned by a given reputation function? We formulate this problem based on a general model of reputation systems, and then examine the ability to bound a collection representative trust functions in the literature. We show that most existing trust functions are monotonic in terms of direct missing information about the target of a trust evaluation, which greatly simplifies this process. The problem of trust bounding with the presence of indirect missing information is much more complicated. We show that many well-known trust functions are not monotonic regarding indirect missing information, which means that a case-by-case analysis needs to be conducted for each trust function in order to bound an entity's trust.