The Measurable Belief of Trust in Social Networks ∗ Sanguk Noh School of Computer Science and Information Engineering, The Catholic University of Korea, Bucheon, Korea sunoh@catholic.ac.kr Abstract. As Web-based online communities are rapidly growing, the agents in social groups need to know their measurable belief of trust for safe and success- ful interactions. In this paper, we propose a formal model of reputation result- ing from available feedbacks in online communities. The notion of trust can be defined as an aggregation of consensus given a set of reputations. The expected trust of an agent further represents the center of gravity of the distribution of its trustworthiness and untrustworthiness. And then, we precisely describe the rela- tionship between reputation, trust, and expected trust through a concrete exam- ple of their computations. We apply our trust model to online Internet settings in order to show how the trust is involved in a rational decision-making of the agents. Keywords: Trust within social networks, consensus aggregation, Dempster- Shafer, adaptive multi-agent systems 1 Introduction Traditional notion of trust [3] refers to an agent’s belief that other agents towards itself intend to be honest and positive, and can be usually built up through direct interactions in person. As online communities on the Internet are rapidly growing, the agents have exposed to virtual interactions as well as face-to-face interactions. The agents in online social networks communicate anonymously and have only limited inspections. These features have made the agents hard to decide whether or not other agents may be positive or benevolent to them. Thus, it is essential that they could have a tangible model of trust for safe and successful interactions, even in the case that they don’t have prior and direct interactions. This paper addresses how to assess trust in social networks, particularly applicable to the online community. We build up the computational model of trust as a measurable concept. Our approach to the computational model of trust starts with the lesson from “Tit for Tat” strategy in game theory for the iterated Prisoner’s Dilemma [1], which en- courages social cooperation among agents. As a result of mutual behaviors in online multi-agent settings, agents will get more positive feedbacks from other agents if the ∗ This work has been supported by the Catholic University of Korea research fund, and de- partment specialization fund, respectively, granted in the program year of 2006. agents are willing to cooperate with others and, otherwise, they will receive more negative feedbacks from others. We translate the feedbacks resulting from social activities into the agent’s reputation as a quantitative concept. The next steps for our trust model are to apply aggregation rules to given reputation values to reach a con- sensus, and calculate the expected trust interpreted as the center of gravity of the distributions of trustworthiness and untrustworthiness. The notion of trust in our framework then represents positive expectations about others’ future behaviors. In the following section of this paper, we briefly compare our approach to related research. Section 3 is devoted to our trust model that defines reputation, trust, and expected trust. We precisely describe the relationship among them through a concrete example of their computations. In Section 4, we apply our trust model to online Inter- net transactions showing how trust affects a rational decision-making of buyers and sellers. In the concluding Section 5, we summarize our work and mention further research issues. 2 Related Work Our work builds on efforts by several other researchers who have made the social concept of trust computable in a society of multi-agents. In the field of multi-agent community, there have been several approaches to support a computational model of trust. Marsh [10] introduces a simple, computational model of trust, which is a sub- jective real number ranging from -1 to 1. His model has trouble with handling nega- tive values of trust and their propagation. Mui et al. [11] describe trust in a pseudo- mathematical expression and represent it as posteriors using expected utility notation. Their scheme only counts the number of cooperations (or positive events). In a dis- tributed reputation system [8], they use aging factor, distance factor, and new experi- ence to update trust. However, the assumption of these components of trust is not likely to be realistic. As they pointed out, their scheme does not correctly handle negative experiences. Our model of trust represents an aggregation of consensus without any problem of fusion, and effectively deals with the agent’s trustworthiness and untrustworthiness in the range of 0 and 1, respectively, which are based on actual positive and negative feedbacks in social networks. Other rigorous efforts have also focused on the formulation of measurable belief representing trust. One of them is to use a subjective probability [4, 7] that quantifies trust as a social belief. In the subjective logic, an agent’s opinion is presented by degrees of belief, disbelief, and uncertainty. Handling uncertainty in various opera- tions is too intuitive to be clear. And further, the subjective logic provides not a cer- tain value of trust but a probability certainty density function. However, our trust model provides a specific trust value as an expected trust considering agent’s trust- worthiness and untrustworthiness together. In another approach, a simple e-Bay feed- back system [13] uses a feedback summary, which is computed as arithmetically subtracting the number of negative feedbacks from the number of positive feedbacks. The contribution of our work is to precisely define the notion of trust as a measurable social belief, and to clearly describe the relationship between reputation, trust, and expected trust in social multi-agent settings. 3 A Computational Model of Trust We propose a formal model of reputation resulting from feedbacks in social networks. The notion of trust then can be defined as an aggregation of consensus given a set of reputations. The calculation of expected trust, further, results in a precise trust value as a metric. In this section, we describe the relationship between reputation, trust, and expected trust through a concrete example of their computations. 3.1 Modeling Reputation Feedbacks in social networks [6, 13] represent reputation associated with the society of multiple agents. The cumulative positive and negative events or feedbacks for an agent, thus, constitute the agent’s reputation [8, 11]. The reputation can be described by a binary proposition 1 p, for example, “A seller deals with only qualified products and delivers them on time.” in the field of online Internet transactions. Given a binary proposition p and an agent-group i judging an agent in p, the reputation of the agent in p, ωi , can be defined as follows: p (1) ωip = {Ti , U i } where • Ti = PFi/Ni and 0≤Ti≤1; • PFi is the number of positive feedbacks for p within an agent-group i; • Ui = NFi/Ni and 0≤Ui≤1; • NFi is the number of negative feedbacks for p within an agent-group i; • ZFi is the number of neutral feedbacks for p within an agent-group i; • Ni is the total number of feedbacks for p within an agent-group i and Ni = PFi+NFi+ZFi. In the definition of reputation, as described in (1), we assume that the feedbacks given by agents within an agent-group evaluating p are independent, and further, the opinions supporting p can be only loosely related to the possible opinions supporting ¬p, since there could be neutral feedbacks from the agent-group. The notion of repu- tation, thus, is based on independent opinions and the sum of Ti and Ui is not neces- sarily being 1. The cumulative positive feedbacks in social networks result from cooperativeness, i.e., trusting interactions, and establish trustworthiness of an agent in p, while the possible number of negative feedbacks from the society affects untrustworthiness of the agent. The trustworthiness and untrustworthiness together constitute a reputation function as a quantitative concept. The reputation of an agent varies with time and size of society, and clearly influences its trust. Given a set of reputations, which is 1 Any reputation in the form of proposition can be expressed according to the contexts as fol- lows: “A buyer has an intention and capability to pay,” “The network system could be safe from any intrusions,” “A car could be reliable for ten years,” and so on. collected at different times and from various interactions made by other agent-groups, the trust as a representative reputation will be derived. 3.2 Calculating Trust Using Aggregation Rules We define trust as a consensus from an aggregation of reputations. The trust 2 ω p for an agent in a proposition p is defined as (2) ω p = ωip ⊗ ω jp = {T , U } where • ωip and ω jp represent reputations accumulated from an agent-group i and an agent-group j, respectively; • T is the trustworthiness of the agent in a proposition p and 0≤T≤1; • U is the untrustworthiness of the agent in a proposition p and 0≤U≤1. The trust, as described in (2), consists of trustworthiness and untrustworthiness. These two components are determined by a set of reputations, as previously defined in (1). To formulate the agent’s trust from reputations, expressed in degrees of trust- worthiness and untrustworthiness which may or may not have the mathematical prop- erties of probabilities, therefore, we propose a set of aggregation rules [9]. Given reputations of ωi and ω j , the aggregation operators, ⊗ = {Ψ1 ,..., Ψn } , in the p p paper, are as follows: 1. Minimum (Ψ1): T = min(Ti , T j ), U = min(U i , U j ) ; 2. Maximum (Ψ2): T = max(Ti , T j ), U = max(U i , U j ) ; 3. Average (Ψ3): T = (Ti + T j ) / 2, U = (U i + U j ) / 2 ; 4. Product (Ψ4): T = TiT j , U = U iU j ; 5. Dempster-Shafer theory [5, 14, 15] (Ψ5): TiT j U iU j T = , U = . 1 − (TiU j + T jU i ) 1 − (TiU j + T jU i ) The trust representing the degrees of belief on agent’s truthfulness can be obtained by applying aggregation rules to a set of reputations. The goal of aggregation is to combine reputations when each of them estimates the probability of trustworthiness 2 For the sake of simplicity, we explain our trust model in a much simpler case of two agent- groups i and j. Our model of trust can be simply extended in more complicated settings in- volving multiple agent-groups without loss of generality. and untrustworthiness for an agent, and to produce a single probability distribution that summarizes the various reputations. The minimum and maximum aggregation rules provide a single minimum and maximum value for T and U, respectively. The average aggregation operator simply extends a statistic summary and provides an average of Tk’s and Uk’s coming from different agent-groups. The product rule summarizes the probabilities that coincide in T and U, respectively, given a set of reputations. Dempster’s rule 3 for combining degrees of belief produces a new belief distribution that represents the consensus of the original opinions [15]. Using Dempster’s rule, the resulting values of T and U indicate the degrees of agreement on trustworthiness and untrustworthiness of origi- nal reputations, respectively, but completely exclude the degrees of disagreement or conflict. The advantage of using the Dempster’s rule in the context of trust is that no priors and conditionals are needed. Among the possible outputs of trust, we denote the trust as the consensus output using a specific aggregator, which is defined as ˆ (t , u ) = Ψ ( Ψ (t , u ),..., Ψ (t , u )) (3) Ψ 1 n where • Ψ is a function determining a specific aggregation rule; • ˆ (t , u ) is the aggregation rule selected with the inputs of t∈Tk and u∈Uk. Ψ Example 1. Let ω1 = {0.80, 0.10}, ω2 = {0.70, 0.20}. This is interpreted that p p there are two agent-groups evaluating p and, in each group, the resulting number of positive feedbacks is much greater than that of negative feedbacks, respectively. Given reputations, aggregation rules can be applied to get trust, as defined in (2), denoting a consensus out of agent-groups’ opinions. The possible outputs of trust using the aggregation rules are summarized in Table 1. Table 1. The example computation of trust using five aggregation rules. ω1p = {0.80, 0.10}, ω2p = {0.70, 0.20} Aggregation rules Trust ω p Minimum (Ψ1) {0.70, 0.10} Maximum (Ψ2) {0.80, 0.20} Average (Ψ3) {0.75, 0.15} Product (Ψ4) {0.56, 0.02} Dempster-Shafer theory (Ψ5) {0.73, 0.03} For example, when we use Ψ5 as an aggregation rule, the trust given reputations is calculated as follows: 3 In this paper, a set of original reputations embedded in social networks are assumed to be consistent in measuring them. This assumption avoids the counterintuitive results obtained using Dempter’s rule in the presence of significantly conflicting evidence, which was origi- nally pointed out by Lotfi Zadeh [15]. (0.8)(0.7 ) T = = 0.73; 1 − [(0.8)(0.2) + (0.7 )(0.1)] (0.1)(0.2) U = = 0.03. 1 − [(0.8)(0.2) + (0.7)(0.1)] Among possible outputs of trust, the trust can be denoted as ω ={0.70, 0.10}, when p ˆ (t , u ) =Ψ1. When minimum, maximum, and average aggregators are used, the Ψ resulting distribution of the trust similarly reflects the distributions of the reputation. In cases of product and Dempster-Shafer theory, however, the T’s (0.56 and 0.73) of the trusts are much bigger than their U values (0.02 and 0.03), compared with the original distributions of the reputation. The resulting T value in Ψ5 is interpreted that there is a 0.73 chance that the agent in p has the trustworthiness, while the resulting U value indicates that there is only a 0.03 chance that the agent is negatively estimated. As we mentioned above, thus, normalizing the original values of trustworthiness and untrustworthiness, which is corresponding to the denominator in the above equation, makes the opinions associated with conflict being away from the trust as a consensus. To show how the aggregation rules could be adapted to various distributions of reputation, we consider additional set of reputations. The possible outputs of trust with two different set of reputations are displayed in the second and the third column of Table 2, respectively. Table 2. The possible outputs of trust with two different set of reputations. ω1pp = {0.20, 0.80}, ω1pp = {0.30, 0.30}, Aggregation rules ω2 = {0.30,p0.70} ω2 = {0.50,p0.50} Trust ω Trust ω Minimum (Ψ1) {0.20, 0.70} {0.30, 0.30} Maximum (Ψ2) {0.30, 0.80} {0.50, 0.50} Average (Ψ3) {0.25, 0.75} {0.40, 0.40} Product (Ψ4) {0.06, 0.56} {0.15, 0.15} Dempster-Shafer theory (Ψ5) {0.10, 0.90} {0.21, 0.21} The example of second column shows the case that the number of positive feedbacks is much less than that of negative feedbacks, and the third column is an example that the number of both feedbacks is identical. Note that the resulting distributions of trustworthiness and untrustworthiness, as displayed in Table 2, mirror their distribu- tions in the original set of reputations.  Since the available feedbacks from multiple agent-groups in social networks are classified into positive, negative, and neutral ones, the positive and negative feed- backs among them are adopted for the components of our trust model. However, these two values contradicting each other are still not enough to represent the trust itself as degrees of belief on agent’s truthfulness. From practical perspective, the trust is required to be a precise value as a metric. 3.3 Expected Trust We define expected trust as the center of gravity of the distribution of beliefs, i.e., the degrees of trustworthiness and untrustworthiness for an agent. The expected trust ω̂ p is given as T (4) ω̂ p = T +U taking into account both trustworthiness and untrustworthiness of an agent. The ex- pected trust, thus, represents the average beliefs on agent’s truthfulness or coopera- tiveness, and translates the agent’s trust into a specific value where 0 ≤ ωˆ ≤ 1 . In p the notion of expected trust, the higher the expected trust level for the agent, the more the expectation that the agent will be truthful or cooperative in future interactions. The calculation of expected trust using equation (4) gives social insight on the agent’s trust. Example 1 (cont’d). Given a set of reputations in the three agent-groups above, the expected trusts are shown in Table 3. Table 3. The expected trust values in three example sets of reputation. ω1pp = {0.80, 0.10}, ω1pp = {0.20, 0.80}, ω1pp = {0.30, 0.30}, Aggregation ω2 = {0.70, 0.20} ω2 = {0.30, 0.70}p ω2 = {0.50, 0.50} rules Expected trust ω̂ Minimum (Ψ1) 0.88 0.22 0.50 Maximum (Ψ2) 0.80 0.27 0.50 Average (Ψ3) 0.83 0.25 0.50 Product (Ψ4) 0.97 0.10 0.50 Dempster-Shafer 0.96 0.10 0.50 theory (Ψ5) This example illustrates that the expected trust provides a metric for the agent’s overall truthfulness, which consists of trustworthiness and untrustworthiness. The simple aggregation rules, i.e., minimum, maximum, average, and product, give a pretty representative trust value considering both trustworthiness and untrustworthi- ness, even though it is not clear which one is good for a particular setting. This may be the reason that these simple but surprisingly well applicable rules keep on being popular in any contexts [9]. The product rule and Dempster-Shafer theory highly rate the agent’s expected trust than the other simple rules. We attribute this sharp contrast between trustworthiness (refer to 0.97 and 0.96 in Table 3) and untrustworthiness (0.10 and 0.10, respectively, in Table 3) to their purely conjunctive operation with completely ignoring the degrees of disagreement or conflict.  4 Applying Trust Model to Online Internet Transactions We apply our trust model to online Internet transactions. Given the actual feedbacks of agent-groups in online multi-agent settings, we can convert the feedbacks into the agent’s reputation, denote its trust as an aggregation of reputations, and compute the expected trust for a measurable belief on the agent’s truthfulness. In this section, we pursue how the trust is involved in a rational decision-making of buyers and sellers. Suppose that there are sellers and buyers in online Internet settings. Let R be a contract price, s be the quantitative size of the contract, V(s) be the buyer’s benefit (or value) function, which reflects his/her satisfaction acquired by purchasing a number of commodities, and C(s) be the seller’s cost function, which indicates the cost to produce the amount of the commodities. Given the expected trust of the buyer ω̂ , M the expected utility of the buyer is given by 4 (5) EU M ( s ) = V ( s ) − ωˆ M R. Given the expected trust of the seller ω̂ , and also, the expected utility of the seller N is defined as (6) EU N ( s ) = ωˆ N R − C ( s ). In equations (5) and (6), the expected trust is interpreted as the average beliefs on the buyer’s and the seller’s truthfulness or cooperativeness, respectively. The Nash equi- librium [2, 12] in online transactions, then, provides a solution concept when the buyer and the seller have no incentives in case of choosing other alternatives. The Nash bargaining solution is (7) arg max R (V ( s) − ωˆ M R)(ωˆ N R − C ( s )) so that the buyer and the seller are beneficial to each other if they agree on their bar- gaining behavior. Note that equation (7) has a unique Nash equilibrium, since an R can be determined given expected trusts of the buyer and the seller, V(s), and C(s). Example 2. To derive R given the Nash bargaining solution, as defined in (7), let us take the first derivative of equation (7) as follows: 4 Our notation follows [2]. d (V ( s ) − ωˆ R )(ωˆ R − C ( s )) = 0; M N dR ωˆ V ( s ) + ωˆ C ( s ) N M ∴R = . 2ωˆ ωˆ M N Thus, the contract price R that they agree on can be determined in a Nash equilibrium. Substituting the above into (5) and rearranging terms, we get ωˆ N V ( s ) − ωˆ M C ( s ) EU M ( s ) = . 2ωˆ N In similar way, the expected utility of the seller is ωˆ N V ( s ) − ωˆ M C ( s ) EU N ( s ) = . 2ωˆ M Suppose that the buyer’s benefit function V(s) is 24ln(2s) and the seller’s cost func- tion C(s) is s2-2s+3 as usual. 5 When ωˆ = ωˆ = 0.8 , the quantitative size of the M N contract s can be determined by d d (ωˆ V ( s ) − ωˆ C ( s )) = (0.8 × 24 ln(2 s ) − 0.8 × ( s − 2 s + 3)) = 0. N M 2 ds ds That is, they both maximize their expected utilities and, once the buyer’s benefit function and the seller’s cost function are decided, the quantitative size of the contract is computed as the above. Thus, s=4. The expected utilities of the buyer and the seller also can be calculated, and, in this case, those are 19.45. Consider now that the seller’s expected trust is low, say, ωˆ = 0.2 . Then, s=2.31, and their expected utili- N ties are EU M ( s ) = 10.94 and EU N ( s ) = 2.73 . Calculated above, both the overall quantitative size of contract and the expected utilities of the buyer and the seller are larger, when the expected trust values of the agents are higher.  5 We assume that the buyer’s benefit does not necessarily increase in proportion to the quanti- tative size of commodities while the seller’s cost proportionally increases to produce a cer- tain amount of commodities. 5 Conclusion The model of trust in social networks has been continuously studied for safe and successful interactions. Our work contributes to a computational model of trust as an aggregation of consensus associated with multiple agent-groups. We formulated repu- tation based on available feedbacks resulting from social interactions, calculated trust among a set of reputations using aggregation rules, and represented expected trust as a metric for the agent’s truthfulness or cooperativeness. We have shown how our trust model can be calculated in a detailed example. To show how the trust is involved in a rational decision-making of interactive agents, our trust model has been applied to online Internet transactions. We believe the trust model should be applicable to real societies of multi-agent environments. As part of our ongoing work, we are applying our trust model to online Internet transactions. Given the actual feedbacks of customers in online multi-agent settings, for example, e-Bay and Auction, we will convert the feedbacks into the agent’s repu- tation, denote its trust as an aggregation of reputations, and pursue how trust affects a rational decision-making of buyers and sellers. Toward this end, we will benchmark the amount of interactions between the buyers and the sellers, when they have higher trust values and/or they have lower trust values. The experiments that we are per- forming will also measure the global profits in a set of agent-groups employed with different trust values. References 1. R. Axelrod, The Evolution of Cooperation, Basic Books, New York (1984) 2. S. Braynov and T. Sandholm, Contracting with Uncertain Level of Trust, Computational Intelligence, Vol. 18, No. 4 (2002) 501 - 514 3. J. Coleman, Foundations of Social Theory, Harvard University Press, Cambridge, MA (1990) 4. A. Daskalopulu, T. Dimitrakos, and T. Maibaum, Evidence-Based Electronic Contract Performance Monitoring, INFORMS Journal of Group Decision and Negotiation, Vol. 11 (2002) 469-485 5. A.P. Dempster, A Generalization of Bayesian Inference, Journal of the Royal Statistical Society, Series B, Vol. 30 (1968) 205-247 6. J. Golbeck, Generating Predictive Movie Recommendations from Trust in Social Networks, Proceedings of the Fourth International Conference on Trust Management, Pisa, Italy (2006) 7. A. Josang and S.J. Knapskog, A Metric for Trusted Systems, Proceedings of the 21st Na- tional Information Systems Security Conference, Virginia, USA (1998) 8. M. Kinateder and K. Rothermel, Architecture and Algorithms for a Distributed Reputation System, LNCS Vol. 2692, Springer-Verlag (2003) 1-16 9. L.I. Kuncheva, J.C. Bezdek, and R. Duin, Decision Templates for Multiple Classifier Fu- sion: An Experimental Comparison, Pattern Recognition, Vol. 34 (2001) 299-314 10. S. Marsh, Formalizing Trust as a Computational Concept, Ph.D. thesis, University of Stir- ling, UK (1994) 11. L. Mui, M. Mohtashemi, and A. Halberstadt, A Computational Model of Trust and Reputa- tion, Proceedings of the 35th Hawaii International Conference on System Sciences (2002) 12. J. Nash, The Bargaining Problem, Econometrica, Vol. 28 (1950) pp 155-162 13. P. Resnick and R. Zeckhauser, Trust Among Strangers in Internet Transactions: Empirical Analysis of eBay's Reputation System, The Economics of the Internet and E-Commerce, Vol. 11, Advances in Applied Microeconomics, Elsevier (2002) 14. G. Shafer, Perspectives on the Theory and Practice of Belief Functions, International Jour- nal of Approximate Reasoning, Vol. 3 (1990) 1-40 15. G. Shafer and J. Pearl, eds., Readings in Uncertain Reasoning, Chapter 3 Decision Making, Chapter 7 Belief Functions, Morgan Kaufmann Publishers (1990) 16. L.A. Zadeh, Review of Books: A Mathematical Theory of Evidence, AI Magazine, Vol. 5, No. 3 (1984) 81-83