=Paper=
{{Paper
|id=Vol-1578/paper8
|storemode=property
|title=Trust Dynamics Analysis of CTR Scheme Subversion under Virtual Anonymity and Trust-Unaware Partner Selection
|pdfUrl=https://ceur-ws.org/Vol-1578/paper8.pdf
|volume=Vol-1578
|authors=Jerzy Konorski
|dblpUrl=https://dblp.org/rec/conf/atal/Konorski16
}}
==Trust Dynamics Analysis of CTR Scheme Subversion under Virtual Anonymity and Trust-Unaware Partner Selection==
https://ceur-ws.org/Vol-1578/paper8.pdf
Trust Dynamics Analysis of CTR Scheme Subversion
under Virtual Anonymity and Trust-Unaware Partner
Selection
Jerzy Konorski
Faculty of ETI, Gdańsk University of Technology
ul. Narutowicza 11/12, 80-233 Gdańsk, Poland
jekon@eti.pg.gda.pl
Abstract
We propose a framework to study Markovian trust value dynamics in
a centralized Computational Trust and Reputation (CTR) scheme un-
der trust-unaware partner selection using a mean-value approximation.
Analytically founded answers are sought to questions like: Can dishon-
est agents subvert the CTR scheme (i.e., acquire higher trust values
than honest agents)? Is indirect reciprocity incentivized? Is there a
qualitative impact of a growing proportion off dishonest agents and
collusion among them?
1 Introduction
A number of tenets of Computational Trust and Reputation (CTR) scheme design are recognized, but have yet
to be captured analytically. In this paper we develop an analytical framework to study the trust dynamics for a
centralized CTR scheme under trust-unaware partner selection. Our CTR scheme features a single Reputation
Aggregation Engine (RAE). Agents occasionally interact to exchange service. Each interaction involves two
partners, a service provider and a service recipient; the latter decide on service providers according to a partner
selection policy and after an interaction report to RAE the amount of received service (called reputation data or
reported service). RAE aggregates reputation data into agents’ trust values, which it subsequently disseminates.
Agents enjoy virtual anonymity [Del00], [Sei04], i.e., use time-varying pseudonyms that only RAE can map to
agents’ permanent identities. A service policy dictates the treatment of the partner–the amount of provided or
reported service subject to available service. If treatments depend on partners’ trust values, the service policy
is called trust-aware, otherwise it is trust-unaware. In the former case, a closed loop containing the RAE to
service policy link is created in Figure 1a (symbols are explained in Sec. 2). By goodwill we mean the sensitivity
of treatments to partners’ trust values. Favorable treatments disregarding trust values signify utmost goodwill,
whereas nonzero treatments only of high-trust partners signify scant goodwill. Better treatment of agents with
higher trust values rewards their favorable past treatments of third-party agents; such a service policy exhibits
indirect reciprocity. We view a trust value as a reputation-based decision-support variable governing who to
interact with and how–hence close to ”standing” [Now98], [Oht04].
Likewise, a partner selection policy can be trust-aware or trust-unaware. In the former, a closed loop containing
the RAE to partner selection policy link is created in Figure 1a, and a distinction between pooled and partitioned
Copyright c by the paper’s authors. Copying permitted only for private and academic purposes.
In: J. Zhang, R. Cohen, and M. Sensoy (eds.): Proceedings of the 18th International Workshop on Trust in Agent Societies,
Singapore, 09-MAY-2016, published at http://ceur-ws.org
1
service availability is relevant. With partitioned service availability, separate resources are reserved for each
service recipient being interacted with. With pooled service availability all recipients draw on a common resource
pool and high reputation can backfire on an agent, who can then experience reputation damage [Yu13]. Figure 1b
summarizes the main goals of CTR schemes assuming agents divide into intrinsically good and bad. Under trust-
unaware partner selection and service policies a CTR scheme is open-loop, and only aims at raising red flags on
bad agents. Trust-aware partner selection enables ostracizing bad agents subject to reputation damage control.
Trust-aware service policy enables differentiation of provided service (also of reported service, which is not
important under trust-aware partner selection).
(a) (b)
Figure 1: (a) Multi-agent CTR scheme with closed loops; (b) Goals of CTR schemes in open- and closed-loop
models
We assume trust-unaware, e.g., random partner selection, as appropriate in systems like mobile ad hoc net-
works, where interactions are restricted by connectivity rather than trustworthiness, or communities from which
bad agents cannot be entirely removed since they possess some scarce resource [Hen15]. Compared to trust-
aware partner selection this is a more challenging setting, since bad agents never cease to receive and report
service the way they want, which can easily confuse RAE. Good agents’ defense then lies in trust-aware service
policy. We call intrinsically good and bad agents honest and skimp & slander (s&s), respectively; we also speak
of an honest or s&s service policy. The latter entails (selfish or malicious) skimp and/or slander attacks, i.e.,
providing and/or reporting less service than honest service policy dictates. Selfish s&s agents strive to maximize
own trust values, whereas malicious s&s agents strive to minimize those of honest agents. In a collusion sce-
nario, s&s agents recognize one another despite virtual anonymity and apply towards fellow colluders cronyism
and/or undue appraisal attacks, i.e., provide and/or report more service than honest service policy dictates.
RAE aggregates reputation data weighted by current trust values and runs a clustering algorithm producing two
levels of trust values. Ideally, the higher level will be acquired by honest agents and the lower by s&s agents. In
the opposite case we say that a CTR scheme subversion occurs. We only allow time-invariant service policies,
reflecting the notion of constant attacks in [Zha12]. The proposed simple framework for Markovian trust value
dynamics gives analytically founded answers to questions like:
• Can s&s agents subvert the CTR scheme and under what conditions?
• Is indirect reciprocity incentivized, i.e., will honest agents condition treatments upon trust values?
• Is there a qualitative impact of a growing proportion of s&s agents and collusion among them?
Our analysis should also capture or somehow relate to well-known tenets of CTR scheme design; several of
them, listed below as T1 through T6, can be deduced from the above discussion and literature.
T1. A CTR scheme should bring honest agents better treatments than they would get without it, assuming all
agents self-optimize. Since treatments are not differentiated in a trust-unaware system, tenet T1 simply
postulates no CTR scheme subversion.
2
T2. Trust values may fail to reflect agents’ intrinsic qualities, CTR scheme subversion being an extreme case.
T3. Goodwill prescribed by an honest service policy should be scant enough to defend against selfish s&s agents,
but enough to defend against malicious ones.
T4. Good reputation is a fiat currency: it only increases an agent’s fitness if reciprocity norms are observed
[Now98]. A CTR scheme should incentivize indirect reciprocity among honest agents, cf. [Wan12].
T5. Increased and more coordinated input from s&s agents to RAE makes it hard to differentiate between honest
and s&s agents: as the proportion of s&s agents grows and collusion among them sets in, a CTR scheme
becomes less effective, cf. [Zha12].
T6. A CTR scheme relies upon reporting received service, for which endogenous incentives should be sought:
reporting received service should help honest agents acquire higher trust values.
The remainder of the paper is organized as follows. Section 2 details the model of the multi-agent system and
CTR scheme. Section 3 presents the trust value dynamics for weighted averaging of reputation data and a class
of service policies. In Section 4 we investigate steady-state trust values and give analytical foundation for some
tenets of CTR scheme design. A beneficial model extension is discussed in Section 5. Section 6 briefly discusses
selected related works. Section 7 concludes and outlines directions of future work.
2 Model Specifics
Consider a large set N of agents and a single RAE. We make the following assumptions, cf. Figure 1a:
(i) Time is divided into cycles t = 1, 2, . . .; in each one service recipients select partners to request service
from. Received service is reported to RAE and aggregated into agents’ trust values, denoted Vi (t) ∈ [0, 1].
(ii) In cycle t agent j selects a random set of partners Ij (t) ⊆ N \{j}.
(iii) Aij (t) ∈ [0, 1] is the amount of service available at a service provider i for a service recipient j in cycle
t, relative to the amount requested by j. Due to temporary resource shortages, variable requested service
etc., Aij (t) are modeled as exogenous random variables with the iid property across t = 1, 2, . . ., and
public-knowledge probability distributions Fij (a) = P rob(Aij (t) < a). They are also independent across
j ∈ N \{i} (partitioned service availability).
(iv) Pij (t) ∈ [0, 1] and Rij (t) ∈ [0, 1] denote treatments in cycle t, respectively the amount of service provided
by i to j and reported by j as received from i. In general, Pij (t) 6= Aij (t) as prescribed by i’s service policy,
(e.g., may depend on Vj (t)), and Rij (t) 6= Pij (t) as prescribed by j’s service policy (e.g., may depend on
Vi (t)).
(v) N = S ∪ H, where S and H are disjoint sets of s&s (selfish or malicious) and honest agents; let ξ =
|S|/|N | > 0.
(vi) In a collusion scenario s&s agents can tell fellow s&s agents and selectively apply cronyism and/or undue
appraisal; in a non-collusion scenario they cannot differentiate treatments other than based on trust values.
Note that RAE cannot reliably guess agents’ intrinsic qualities (s&s or honest): deciding if a record of Rij (t), t =
1, 2, . . . ”looks honest” given Fij (·) would need the knowledge of both agents’ intrinsic qualities.
3 Analytical Framework
In this section we construct trust value dynamics for a class of service policies; asymptotic trust values can then
be obtained as fixed points of a corresponding nonlinear mapping.
3
3.1 Reputation Aggregation and Trust Value Dynamics
RAE uses in each cycle an eigenvector-type reputation aggregation algorithm that obtains a weighted average of
reputation data regarding agent i :
X
Ri,avg (t) = Vj (t)δ ∆ij (t) Rij (t − ∆ij (t)) , (1)
j∈N \{i}
where δ ∈ [0, 1] is a decay factor and ∆ij (t) is the number of cycles since i last provided service to j (∆ij (t)
= 0 for i ∈ Ij (t)). RAE distinguishes just two levels of trust values and assigns them to subsets Nhigh (t) and
Nlow (t) of agents with ”high” and ”low” Ri,avg (t) values. To determine these subsets, RAE applies a clustering
algorithm such that if i ∈ Nhigh (t) and j ∈ Nlow (t) then Ri,avg (t) ≥ Rj,avg (t). Normalization is applied so that
agents in Nhigh (t) acquire trust values equal to 1. This yields (with 0/0 defined to be 0):
P
l∈Ni (t) Rl , avg(t)/|Ni (t)|
Vi (t + 1) = P , (2)
l∈N high(t) Rl , avg(t)/|Nhigh (t)|
where Ni (t) is the subset containing i. If s&s and honest service policies differ substantially then Nhigh (t) = S
and Nlow (t) = H or vice versa, i.e., s&s and honest agents are accurately partitioned; otherwise the partition
is not very relevant. Due to possible CTR scheme subversion, RAE cannot pinpoint s&s agents with certainty.
Given Vi (0), (1) and (2) produce explicit trust value dynamics in the form of a multidimensional homogeneous
discrete-time Markov chain on [0, 1]|N | . There may be absorbing states: e.g., zero trust values may tend to
spread among agents, reflecting a denial of service. It is not clear whether such an absorbing state will ever be
reached; even so, one can speak of a wide-sense steady state of (2) if, for all i ∈ N and a long enough time, the
variability range of Vi (t) is much narrower than the interval [0, 1]. (An absorbing state is a special case.) For
large |N |, a wide-sense steady state can be observed almost indefinitely, as illustrated in Sec. 3.4.
3.2 Service Policy
A service provider i interacting with a service recipient j is limited by Pij (t) ≤ Aij (t) and its service policy;
assume that the latter moreover implies Pij (t) ≤ pij , where pij ∈ [0, 1] is a threshold. The above two constraints
can be met, e.g., by Pij (t) = σi (Aij (t), pij ), where σi (a, p) = min(a, p) or ap (a discriminative or multiplicative
policy, respectively). For Rij (t), we assume Rij (t) ≤ Pij (t) and let j’s service policy moreover imply Rij (t) ≤ rij ,
where rij ∈ [0, 1] is a threshold. Thus:
Rij (t) = σj (Pij (t), rij ) = σj (σi (Aij (t), pij ), rij ) . (3)
The thresholds pij and rij quantify agents’ goodwill (propensity for skimp, cronyism, slander, or undue
appraisal). It is natural that pij increases with Vj (t) and rij increases with Vi (t). If both i and j are s&s and
collude then i applies cronyism and j applies undue appraisal–respectively, pij = rij = 1. Finally, towards an
honest partner, or any partner in a non-collusion scenario, an s&s service policy applies discretionary thresholds.
3.3 Symmetric System Model
Assume in addition that (vii) service policy only distinguishes between s&s and honest partners, and (viii)
Fij (·) ≡ F (·). Assumption (vii) simplifies the description of a service policy, since now only σs(·, ··) and σh(·, ··),
as well as pqq 0 and rqq 0 , need to be distinguished, where q,q’ ∈ {s, h}. All Vi (t), i ∈ S, are now represented as
V s(t), and all Vi (t), i ∈ H, as V h(t). We take
ỹ q = s and q’ = s
z̃ q = s and q’ = s
pqq’ = y q = s and q’ = h rqq’ = z q = h and q’ = s (4)
wL(Vq’ (t), x) q=h wL(Vq (t), x) q’ = h
where ỹ = y and z̃ = z in a non-collusion scenario (s&s agents cannot tell s&s partners from honest), and
ỹ = z̃ = 1 in a collusion scenario; y, z ∈ [0, 1] are discretionary thresholds imposed by s&s agents (y = z = 0
and y = z = 1 signify scant and utmost goodwill, respectively). Honest agents offer goodwill (limit the amount
of provided or reported service) depending on the partner’s current trust value through a function L : [0, 1]2 →
[0, 1]; L(v, x) is returned for the trust value v given the goodwill shape factor x ∈ [0, 1], whereas w ∈ [0, 1] is the
4
goodwill downscale factor. Goodwill is calibrated from utmost, with x = w = 1 (trust values are disregarded and
no downscaling applies), to scant, with x = 0 and w ≈ 0 (only highest-trust agents receive nonzero service w).
We take L(v, x) to be continuous and nondecreasing in v and x > 0, converging point-wise to 1(v ≤ 1) as x → 1
and to 1(v = 1) as x → 0, where 1(·) is the indicator function. Examples are unit-step functions, which produce
an intuitive “binary” honest service policy only offering goodwill if the partner has a large enough trust value:
Pij (t) = Aij (t) · w·1(Vj (t) ≥ 1 − x) and Rij (t) = Pij (t) · w·1(Vi (t) ≥ 1 − x); the type of honest service policy
(discriminative or multiplicative) is then irrelevant. Note that indirect reciprocity occurs for x < 1.
3.4 Mean-Value Dynamics
We note that in our model, (1) is statistically indistinguishable from j∈N \{i} Vj (t)δ ∆ij (t) Rij (t). We substitute
P
the latter into (2) and use the law of large numbers to obtain approximate deterministic trust value dynamics:
∆lj (t)
P P
j∈N Vj (t)Eδ ERlj (t)|l∈ Ni (t) j∈N Vj (t)ERlj (t)|l∈ Ni (t)
Vi (t + 1) ≈ P ∆ (t)
=P , i ∈ N, (5)
j∈N Vj (t)Eδ ERlj (t)|l∈ Nhigh (t) j∈N Vj (t)ERlj (t)|l∈ Nhigh (t)
lj
where E denotes the statistical expectation of F (·). We group the summands assuming that s&s and honest
agents are accurately partitioned, and replace Vj (t) by Vq (t) and Rij (t) by Rqq’ (t), where q,q’ ∈ {s, h}. Then
(5) becomes:
ξVs (t)ERqs (t) + (1 − ξ)Vh (t)ERqh (t)
Vq (t + 1) = , q = s, h, (6)
M (t)
where M (t) is the larger of the two numerators. Thus max{Vs (t), Vh (t)} = 1.
To account for the s&s and honest service policies introduce R p a continuous, nondecreasing and quasi-concave
function Ψ : [0, 1] → [0, EA], where Ψ(p) = Emin{A, p} = 0 (1 − F (a))da and A ∼ F (·); we have Ψ(0) = 0,
Ψ(1) = EA, and Ψ(pr) ≥ pΨ(r) for any p, r ∈ [0, 1]. Let mean reported service be represented by Ωqq’ : [0, 1]2 →
[0, EA], with Ωqq’ (p, r) = ERqq’ (t)|pqq’ =p,rqq’ =r . From (3),
discriminative σq(·, ··) and σq 0 (·, ··)
Ψ(min{p, r}),
discriminative σq(·, ··) , multiplicative σq 0 (·, ··)
rΨ(p),
Ωqq’ (p, r) = (7)
pΨ(min{1, r/p}), multiplicative σq(·, ··) , discriminative σq 0 (·, ··)
prΨ(1), multiplicative σq(·, ··) and σq 0 (·, ··).
Hence Ωqq’ (·, ··) is continuous and nondecreasing in both variables, with Ωqq’ (0, r) = Ωqq’ (p, 0) = 0 and
Ωqq’ (1, 1) = Ψ(1) = EA. Based on (4), (6) can be rewritten as
ξVs (t)Ωss (ỹ, z̃) + (1 − ξ)Vh (t)Ωsh (y, wL(Vs (t), x))
Vs (t + 1) = ,
M (t)
(8)
ξVs (t)Ωhs (wL(Vs (t), x), z) + (1 − ξ)Vh (t)Ωhh (wL(Vh (t), x), wL(Vh (t), x))
Vh (t + 1) = ,
M (t)
Equation (8) defines a deterministic fixed-point iteration process for a nonlinear continuous mapping of (Vs , Vh ),
where the compact convex set [0, 1]2 maps to itself. By Brouwer’s theorem, a fixed point exists. Since RAE is
unable to distinguish s&s and honest agents, necessarily Vs (0) = Vh (0) = 1. If iterations converge to a fixed
point, the limits Vso = Vs (∞) and Vho = Vh (∞) approximate the wide-sense steady-state of (2); possible other
fixed points are then irrelevant.
P In Figure 2 we compare P the mean-value trajectories (8) subject to Vs (0) = Vh (0) = 1, and the averages
i∈S i V (t)/|S| and V
i∈H i (t)/|H| of the Markovian trajectories (2) subject to Vi (0) = 1. RAE adopts a simple
clustering algorithm: having ordered the averages of reputation data (1) so that Ri1 ,avg ≥ . . . ≥ Ri|N | ,avg ,
minimize the sum of the ”high” and ”low” subset diameters, i.e., find µ* = argmin1+m<µ<|N |−m (Ri1+m ,avg −
Riµ ,avg + Riµ+1 ,avg − Ri|N |−m ,avg ), where m ≥ 0 eliminates possible outliers (we take m = 1). Then Nhigh (t) =
{i1 , . . . , iµ* }.
To warrant the law of large numbers, there should be enough nonnegligible summands in (2), hence δ should
be large enough. When δ = 1 and x = 0.25 (Figure 2a,b), the clustering is perfect, i.e., Ni (t) = S iff i ∈ S,
hence (8) quickly converges to a wide-sense steady state of (2) (with honest agents absorbed at Vi (t) = 0). For y
= 0.89, Vh (t) = 0 is approximated rather inaccurately as it converges, yet its steady-state behavior is captured.
5
Decreasing δ to 0.8 (Figure 2c,d) has little effect if y = 0.89, but for y = 0.51 causes a CTR scheme subversion
and a discrepancy between the Markovian and mean-value trajectories; this is because the clustering algorithm
fixes upon incorrect clusters after t = 32. A further decrease of δ to 0.6 (Figure 2e) confuses the clustering
algorithm altogether and drives the Markovian trajectories to a denial of service. In Figure 2f, x = 0.65, δ = 1,
and s&s agents offer high goodwill: y = z = 0.9. The clustering algorithm is again confused and no wide-sense
steady state occurs; nevertheless the discrepancies between the Markovian and mean-value trajectories are mild.
(a) (b) (c)
(d) (e) (f)
Figure 2: Markovian and mean-value trust value trajectories in a collusion scenario; ξ = 25%, unit-step L(·, ··),
multiplicative σs (·, ··)
4 Mean-Value Analysis
The results in Figure 2 encourage the use of (8) instead of (2) for investigation of some qualitative properties of
agents’ trust values. First we verify that our CTR scheme is in a sense ”fair” to s&s agents.
Proposition 1. If s&s agents do not apply skimp attacks then there exists an s&s service policy (namely,
extreme slander, z = 0) that yields them V so = 1 regardless of the honest service policy (x and w ). If they
do apply skimp attacks with a small enough y while being in the minority (ξ < 1/2) then there exists a honest
service policy (namely, a large enough w with any x ) that drives V so arbitrarily close to 0.
Proof : To satisfy the premise of the first part, one substitutes wL(Vh (t), x) for y in (8), moreover, it must
be that either (a) σs (·, ··) and σh (·, ··) are of the same type (discriminative or multiplicative), or (b) σs (·, ··) is
discriminative and σh (·, ··) is multiplicative. Let z = 0. Recall that Vs (0) = Vh (0) = 1 and assume Vh (t) ≤
Vs (t) = 1 for some t ≥ 0. For brevity denote Ls = L(Vs (t), x) and Lh = L(Vh (t), x) (Lh ≤ Ls = 1 by the
properties of L(·, ··)). Then Ωhh (wLh , wLh ) ≤ Ωsh (wLh , wLs ): in case (a) by the properties of Ωqq’ (·, ··), and in
case (b) by (7) and the properties of Ψ(·). Consequently, Vh (t + 1) ≤ Vs (t + 1) and by induction, Vso = 1. For
the second part observe that for a small enough y and a non-collusion scenario, Vs (t) is arbitrarily close to 0 for
all t. For a collusion scenario assume Vs (t) ≤ Vh (t) = 1 for some t. Then from the first equation of (8),
cΨ(1) Ωhh (y, wLs )
Vs (t + 1) ≤ Vs (t) + (9)
Ωhh (w, w) Ωhh (w, w)
where c = ξ/(1 − ξ) < 1. Let α = cΨ(1)/Ωhh (w, w). In a generic equation v = αv + Ωsh (y, wL(v, x))/Ωhh (w, w),
the right-hand side can be made arbitrarily close to αv with a small enough y, cf. (7). On the other hand, taking
w close enough to 1 makes α arbitrarily close to c, hence Vs (t + 1) < Vs (t), Vh (t + 1) = 1, and the largest root of
the equation is arbitrarily close to 0 depending on the behavior of the last term at v = 0. Thus if the fixed-point
iteration process (9) for t0 > t converges to some Vso then Vso is arbitrarily close to 0.
6
Analyzing (8) similarly one sees that lack of indirect reciprocity (x = 1) enables s&s agents to acquire trust
values equal to honest agents’, which illustrates tenets T1 and T4. The following two propositions show a
qualitative difference between a collusion and a non-collusion scenario as regards CTR scheme subversions.
Proposition 2. In a non-collusion scenario with ξ < 1/2, taking w = 1 prevents CTR scheme subversion, i.e.,
Vso ≤ Vho = 1 for any x, y, and z.
Proof : To use the inductive argument assume Vs (t) ≤ Vh (t) = 1 for some t ≤ 0. Rewrite (8) substituting
ỹ = y, z̃ = z and using shorthand Ls for L(Vs (t), x):
M (t)Vs (t + 1) = ξVs (t)Ωss (y, z) + (1 − ξ)Ωsh (y, wLs ) ,
(10)
M (t)Vh (t + 1) = ξVs (t)Ωhs (wLs , z) + (1 − ξ)Ωhh (w, w) .
Define diff = 2M (t)(Vh (t + 1) − Vs (t + 1)), and take a large enough w such that Ωhh (w, w) ≥ Ωsh (1, wLs ) (by
(7), this is guaranteed if σh (·, ··) is discriminative and requires w ≥ Ls if σh (·, ··) is multiplicative). Then
diff = 2(1 − ξ)(Ωhh (w, w) − Ωsh (y, wLs )) − 2ξVs (t)(Ωss (y, z) − Ωhs (wLs , z))
(11)
≥ Ωhh (w, w) − Ωsh (1, wLs ) − (Ωss (1, z) − Ωhs (wLs , z)) = RHS .
We can show that w = 1 guarantees RHS ≥ 0 regardless of x, y, and z, but w < 1 does not. Indeed, in
the case where σs (·, ··) and σh (·, ··) are both multiplicative, we have RHS = w2 Ψ(1) − wLs Ψ(1) − (zΨ(1) −
zwLs Ψ(1)) = (1 − z)(1 − wLs )Ψ(1) − (1 − w2 )Ψ(1). The other three cases can be examined analogously. Hence,
Vs (t + 1) ≤ Vh (t + 1) = 1 and the proposition follows.
Proposition 3. In a collusion scenario, CTR scheme subversion is always possible, i.e., for any x and w, and
regardless of ξ, there exist y and z such that Vho < Vso = 1; if x is close enough to 0 then Vho = 0 (denial of
service) is also observed.
Proof : First we will show that subversion is indeed possible when z = 0 and y is large enough. With z = 0,
ỹ = z̃ = 1 and Vs (0) = Vh (0) = 1, (8) implies
M (t)Vs (1) = ξΨ(1) + (1 − ξ)Ωsh (y, w),
(12)
M (t)Vh (1) = (1 − ξ)Ωhh (w, w).
Pick a y that fulfils
(1 − ξ)Ωhh (w, w) − ξΨ(1)
Ωsh (y, w) > = Ωhh (w, w) − cΨ(1), (13)
1−ξ
where c is defined in (9) (we omit the argument that such a y exists). Then (12) implies Vh (1) < Vs (1) = 1.
Suppose Vh (t) < Vs (t) = 1 for some t > 0, then using shorthand Lh = L(Vh (t), x) and Ls = L(Vs (t), x) = 1 we
have from (8):
M (t)Vs (t + 1) = ξΨ(1) + (1 − ξ)Vh (t)Ωsh (y, w),
(14)
M (t)Vh (t + 1) = (1 − ξ)Vh (t)Ωhh (wLh , wLh ).
The condition for Vh (t + 1) < Vs (t + 1) = 1 is Ωsh (y, w) > Ωhh (wLh , wLh ) − cΨ(1)/Vh (1), which (13) ensures,
hence the first part of the proposition follows by induction. To investigate x close to 0, notice from (8) that
(1 − ξ)Vh (t)Ωhh (wLh , wLh ) Vh (t)Ωhh (wLh , wLh )
Vh (t + 1) = = , (15)
M (t) cΨ(1) + Vh (t)Ωsh (y, w)
where c is defined in (9). The right-hand side of a generic equation v = vΩhh (wLh , wLh )/(cΨ(1) + vΩsh (y, w))
at v = 0 equals 0, at v = 1 equals Ωhh (wLh , wLh )/(cΨ(1) + Ωhh (y, w)) < 1 by (13), has a derivative 0 at v = 0
by the properties of L(·, ··) and Ωqq’ (·, ··), and by choosing x close enough to 0 can be made less than v for all
v < 1. Therefore the fixed-point iteration process (15) starting from Vh (t) < 1 produces Vh (t0 ) < 1 for all t0 > t
and converges to Vho = 0.
One conclusion from Proposition 3 is that the acquired trust values may contrast with agents’ intrinsic qualities,
as tenet T2 states. Another is that the qualitative difference between a collusion and a non-collusion scenario
regarding possible CTR scheme subversions occurs irrespective of ξ. This challenges the intuition tenets T2 and
T5 convey that s&s agents must be numerous enough to subvert a CTR scheme. Furthermore, if Proposition
3, second part, holds for some x0 , it also does for all x < x0 . Hence in a collusion scenario honest agents’ best
7
response to malicious s&s agents is x > xh (while small x punish selfish s&s agents, which illustrates tenet
T3). The xh that separates ”too scant” and ”enough” goodwill depends on whether σs (·, ··) and σs (·, ··) are
discriminative or multiplicative, and decreases in ξ, since so does the right-hand side of (9). For a unit-step
L(·, ··), xh can be found analytically (details are omitted): if w ≤ c then xh = 1, otherwise
(
1 − (w−c)Ψ(1)
Ψ(w) , discriminative σh (·, ··),
xh = (16)
c/w, multiplicative σh (·, ··).
We now show that “enough” goodwill protects honest agents from a denial of service caused by malicious s&s
agents that are in the minority.
Proposition 4. In a collusion scenario with ξ < 1/2, and x, w large enough, Vho > 0 regardless of y and z.
Proof : The second equation of (8) implies
(1 − ξ)Vh (t)Ωhh (wLh , wLh ) Ωhh (wLh , wLh ) Vh (t)
Vh (t + 1) ≥ min ,1 ≥ · , (17)
ξVs (t)Ψ(1) + (1 − ξ)Vh (t)Ωsh (y, wLs ) Ψ(1) c + Vh (t)
where c is defined in (9). If x and w are large enough then, by the continuity of Ωhh (·, ··), the first fraction of
the right-hand side can be made arbitrarily close to 1 for any Vh (t) > 0. Hence
Vh (t)
Vh (t + 1) ≥ (1 − ) · , (18)
c + Vh (t)
where > 0 is arbitrarily small. Let x be such that < 1 − c. The right-hand side of a generic equation
v = (1 − )v/(c + v) is an increasing concave function of v, less than 1 at v = 1, whose derivative at v = 0 is
(1 − )/c > 1. Therefore if (8) converges to some Vho then Vho is greater than or equal to the unique root of the
equation, i.e., Vho ≥ 1 − c − > 0. (Note that failure to report by honest agents is tantamount to a larger ξ,
hence results in a smaller Vho , cf. tenet T6.)
Figure 3 plots Vso and Vho against y and z in two sample settings with uniformly distributed Aij (t) i.e.,
F (a) = a for a ∈ [0, 1], implying Ψ(p) = p(1 − p/2), to illustrate tenet T2–trust values may contrast with agents’
behavior. One sees that larger y and z may, but need not mean larger trust values for s&s agents: the effect
of getting more favorable reputation data from honest agents competes with that of producing more favorable
reputation data about them. Note that Vso = 1 for large enough y (and small enough z) signifies a CTR scheme
subversion, and Vso = 0 for a range of small y, cf. Proposition 1. Qualitatively similar results were obtained for
other settings.
(a) (b)
1 1
z = 0..1 z = 0..1
0.8 0.8
trust values
trust values
ξ = 25%
0.6 ξ = 25% 0.6 collusion
collusion x = 0.25
0.4 x = 0.65 0.4 w =1
w =1
0.2 0.2 V so
V so
V ho V ho
0 0
0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1
y y
Figure 3: Trust values for various s&s service policies in a collusion scenario; Vs (0) = Vh (0) = 1, unit-step L(·, ··),
multiplicative σs (·, ··), w = 1; (a) x = 0.65, (b) x = 0.25
8
5 Bilateral Contribution
In the reputation aggregation algorithm governed by (1), agent j contributes to the new trust value of agent i
through Rij (t), service reported as received from i. Such a unilateral type of contribution is fairly common in
existing CTR schemes. Consider now a bilateral type of contribution, so that (1) becomes
X
Vj (t)δ max{∆ij (t),∆ji (t) Γ Rij (t − ∆ij (t)), Rji (t − ∆ji (t)) ,
Ri,avg (t) = (19)
j∈N \{i}
2
where Γ : [0, 1] → [0, 1] is a bivariate function. The intuition behind bilateral contribution is that an s&s agent’s
trust value should be lowered not only by skimp attacks (providing too little service), but also by slander attacks
(underreporting received service). A similar approach is taken in [Jia06], where Γ(u, v) = u + v can be inferred;
traces of it can also be found in some opinion portals where voting down someone else’s opinion causes one to
lose points, and in [Saa2010], where agents’ scores are based both on provided and received service. Since it is
reasonable to demand that Γ(u, v) ≤ min{u, v}, let Γ(u, v) = min{u, v}. Recalling (3) we replace ERij (t) by
Ri↔j (t) = Emin{Rij (t), Rji (t)} = Emin{σj (σi (Aij (t), pij ), rij ), σi (σj (Aji (t), pji ), rji } . (20)
To adopt the mean-value approximation of Sec. 3.4 let us introduce generalized functions
Z 1
a
Ψβ (p) = Emin{A0 , βA00 , p} = 1 − F ( ) (1 − F (a))da , (21)
0 β
Ωq↔q’ (p, r, π, ρ) = ERi↔j (t)|pqq’ =p,rqq’ =r,pq’q =π,rq’q =ρ . (22)
0 00
where β ∈ [0, 1], A , A ∼ F (·), and q, q’ ∈ {s, h}. Analogously to (7) and with 0/0 taken to be 0 we have:
discriminative σq(·, ··) and σq 0 (·, ··)
Ψ1 (min{p, r, π, ρ}),
discriminative σq(·, ··) , multiplicative σq 0 (·, ··)
Ψ (min{p, r}),
πρ
Ωq↔q’ (p, r, π, ρ) = (23)
Ψpr (min{π, ρ}), multiplicative σq(·, ··) , discriminative σq 0 (·, ··)
prΨπρ/pr (1), multiplicative σq(·, ··) and σq 0 (·, ··).
Using a succinct notation Ls = L(Vs (t), x) and Lh = L(Vh (t), x) we turn (8) into
ξVs (t)Ωs↔s (ỹ, z̃, ỹ, z̃) + (1 − ξ)Vh (t)Ωs↔h (y, wLs , wLs , z)
Vs (t + 1) = ,
M (t)
(24)
ξVs (t)Ωh↔s (wLs , z, y, wLs ) + (1 − ξ)Vh (t)Ωh↔h (wLh , wLh , wLh , wLh )
Vh (t + 1) = .
M (t)
Bilateral contribution proves highly beneficial, since it prevents CTR scheme subversion by a minority of s&s
agents in both a non-collusion and a collusion scenario, thus in effect neutralizes s&s agents’ collusion.
Proposition 5. With ξ < 1/2 and w = 1, CTR scheme subversion is not possible under bilateral contribution,
i.e., Vso ≤ Vho = 1 for any x, y, z ∈ [0, 1].
Proof : Define diff similarly as in the proof of Proposition 2 and assume Vs (t) ≤ Vh (t) = 1 for some t > 0.
Then Lh = 1 and, since ξ < 1/2, we have:
diff = 2(1 − ξ)(Ωh↔h (w, w, w, w) − Ωs↔h (y, wLs , wLs , z)) − 2ξVs (t)(ψ − Ωh↔s (wLs , z, y, wLs ))
(25)
≥ Ωh↔h (w, w, w, w) − Ωs↔h (y, wLs , wLs , z)) − (ψ − Ωh↔s (wLs , z, y, wLs )),
where ψ = Ψ1 (min(ỹ, z̃) or ỹz̃Ψ1 (1) if the s&s service police is discriminative or multiplicative, respectively; in
both cases ψ ≤ Ψ1 (1). From (23), Ωh↔s (wLs , z, y, wLs ) = Ωs↔h (y, wLs , wLs , z) and Ωh↔h (1, 1, 1, 1) = Ψ1 (1).
Thus if w = 1 then diff ≥ 0, i.e., Vs (t + 1) ≤ Vs (t + 1) = 1 and the proof follows by induction. (Note that if
w < 1, the proposition may not hold.)
Having two reputation aggregation algorithms to choose from (i.e., unilateral and bilateral contribution),
RAE can try to confuse s&s agents by concealing the algorithm in use. However, in agreement with [Ker09],
such ”security by obscurity” does not bring any improvement; a broader discussion is omitted for lack of space.
9
6 Related Work
Works that hint at trust value dynamics induced by one or both closed-loops in Figure 1b are many, but relatively
few explicitly construct and analyze them. The model of [Mui02] recognizes a closed loop between and an agent’s
reputation, trust, and utility resulting from reciprocity (close in meaning to a trust-aware service policy). It is
postulated that a more honest service policy foster higher reputation and more trust. We observe to the contrary
that CTR scheme subversions are possible if s&s agents collude. In [Jia06], an agent’s service policy is modeled as
a probability of positive or negative rating of an interacting agent conditioned on both agents’ intrinsic goodness
or badness. It is shown that non-colluding attackers cannot subvert the scheme regardless of their number.
Surprisingly, colluding attackers whose ratings favor fellow colluders cannot either. Our model links ratings to
current trust values rather than agents’ intrinsic qualities, which gives rise to a trust-aware service policy. We
show that colluding attackers always can subvert the scheme unless bilateral contribution is in use. Our Markovian
analysis takes advantage of a mean-value approximation; a mean field approximation similar in spirit to ours is
applied in [Hub04], albeit in a very different, economic setting. Deterministic reputation dynamics are studied
in [Cao06], but reported service, agents’ misbehavior, or trust-weighted reputation aggregation are not explicitly
accounted for. In [Chk10], each agent forms opinions cycle by cycle based on other agents’ opinions weighted by
their current reputations; the latter depend on previous-cycle reputations. In our context, an agent’s trust value
cannot influence other agents’ other than through reported service–this precludes various manipulations which
[Chk10] overcomes using control- and game-theoretic methods. Under trust-aware partner selection, reputation
dynamics arise because more frequent partners become even more selectable. Existing analyses account for
various ratings collection models [Huy06], [Has14]. With pooled service availability one expects oscillatory
trajectories of reputation scores [Yu13]. Our model prevents reputation damage owing to trust-unaware partner
selection and partitioned service availability. Game-theoretic analyses of reputation models are usually tied to a
simple interaction game, e.g., social dilemma, donation, or product choice. Evolutionary models of random pair-
wise interactions “natively” give rise to reputation dynamics under trust-unaware partner selection and trust-
aware service policy [Now98] [Oht04]. Evolutionary reputation dynamics under trust-aware partner selection
are investigated, e.g., in [Fu08], [Wan12], [Pel14]. Non-evolutionary studies of reputation dynamics in repeated
games often have one long-lived player interact sequentially with many short-lived ones [Ekm06], [Liu11]. Agents’
intrinsic qualities, collusion, service policy, or service availability are not directly reflected.
7 Conclusion And Future Work
The analyzed trust value dynamics capture some intuitions and tenets of CTR design, and run counter some
others. For example,
• a CTR scheme with trust-weighted aggregation of reputation data can be made invulnerable to subversion
in a non-collusion scenario if s&s agents are in the minority; however, subversion is possible in a collusion
scenario with an arbitrarily small proportion of s&s agents,
• defenses against selfish and malicious s&s agents can be combined by offering a moderate degree of goodwill
(and indirect reciprocity) towards low-trust agents,
• bilateral-contribution reputation aggregation at RAE in effect neutralizes s&s agents’ collusion, and finally,
• concealment of the reputation aggregation algorithm from agents does not bring honest agents better treat-
ments “security by obscurity” does not work.
Further research will focus on other reputation aggregation algorithms, multiple- rather than two-level trust
values, a multi-faceted notion of service, and extensions to quasi-static settings with adaptive service policies
adjusted based on received service. Group rather than pairwise interactions are another natural generalization.
7.0.1 Acknowledgements
Preliminary ideas of the paper were developed during the author’s participation in the Future Internet Engineer-
ing project supported by the European Regional Development Fund under Grant POIG.01.01.02-00-045/09-00.
10
References
[Cao06] J. Cao, W. Yu, and Y. Qu. A new complex network model and convergence dynamics for reputation
computation in virtual organizations. Physics Letters A, 356(6): 414–425, Aug. 2006.
[Chk10] A. G. Chkhartishvili, D. A. Gubanov, N. A. Korgin, and D. A. Novikov. Models of reputation dynamics
in expertise by social networks. Proc. UKACC Int. Conf. on Control, Coventry, UK, Sept. 2010.
[Del00] C. Dellarocas. Immunizing online reputation reporting systems against unfair ratings and discriminatory
behavior. Proc. 2nd ACM Conf. on Electronic Commerce, Minneapolis, MN, Oct. 2000.
[Ekm06] M. Ekmekci. Sustainable reputations with rating systems. Mimeo, Princeton University 2006.
[Fu08] F. Fu, C. Hauert, M. A. Nowak, and L. Wang. Reputation-based partner choice promotes cooperation
in social networks. Phys. Rev. E, 78(026117), 2008.
[Has14] M. R. Hassan, G. Karmakar, and J. Kamruzzaman. Reputation and user requirement based price
modeling for dynamic spectrum access. IEEE Trans. Mobile Comput., 13(9): 2128–2140, Sept. 2014.
[Hen15] F. Hendrikx, K. Bubendorfer, and R. Chard. Reputation systems: A survey and taxonomy. J. Parallel
and Distrib. Comput., 75(1): 184–197, Jan. 2015.
[Hub04] B. A Huberman and Fang Wu. The dynamics of reputations. J. Stat. Mechanics, P04006, April 2004.
[Huy06] Trung Dong Huynh, N. R. Jennings, and N. R. Shadbolt. Certified reputation: how an agent can trust
a stranger. Proc. AAMAS’06, Hakodate, Japan, May 2006.
[Jia06] T. Jiang and J. S. Baras. Trust evaluation in anarchy: A case study on autonomous networks. Proc.
25th IEEE INFOCOM, Barcelona, Spain, April 2006.
[Ker09] R. Kerr and R. Cohen. Smart cheaters do prosper: Defeating trust and reputation systems. Proc.
AAMS’09, Budapest, Hungary, May 2009.
[Liu11] Q. Liu. Information acquisition and reputation dynamics. Rev. Econ. Studies, 78(4): 1400–1425, 2011.
[Mui02] L. Mui, M. Mohtashemi, and A. Halberstadt. A computational model of trust and reputation. Proc.
35th Annual Hawaii International Conf. on System Sciences, 2002.
[Now98] M. A. Nowak and K. Sigmund. Evolution of indirect reciprocity by image scoring. Nature, 393: 573–577,
June 1998.
[Oht04] H. Ohtsuki and Y. Iwasa. How should we define goodness?–reputation dynamics in indirect reciprocity.
J. Theor. Biol., 231(1): 107–120, Nov. 2004.
[Pel14] A. Peleteiro, J. C. Burguillo, and Siang Yew Chong. Exploring indirect reciprocity in complex networks
using coalitions and rewiring. Proc. AAMAS’14, Paris, France, May 2014.
[Ram04] S. D. Ramchurn, Dong Huynh, and N. R. Jennings. Trust in multi-agent systems. The Knowledge
Engineering Review, 19(1): 1–25, March 2004.
[Saa2010] S. Saavedra, D. Smith, and F. Reed-Tsochas. Cooperation under indirect reciprocity and imitative
trust,” PLoS ONE, vol. 5, 2010.
[Sei04] J.-M. Seigneur, S. Farrell, C. Damsgaard Jensen, E. Gray, and Y. Chen. End-to-end trust starts with
recognition. LNCS vol. 2802, Berlin, Heidelberg: Springer, 2004.
[Wan12] Z. Wang, L.Wang, Z.-Y.Yin, and C.-Y. Xia. Inferring reputation promotes the evolution of cooperation
in spatial social dilemma games. PLoS ONE, 7(7): e40218, 2012.
[Yu13] Han Yu, Zhiqi Shen, C. Leung, C. Miao, and V. R. Lesser. A survey of multi-agent trust management
systems. IEEE Access, 1: 35–50, 2013.
[Zha12] L. Zhang, S. Jiang, Jie Zhang, and Wee Keong Ng. Robustness of trust models and combinations
for handling unfair ratings. IFIP Advances in Information and Communication Technology, vol. 374, Berlin,
Heidelberg: Springer, 2012.
11