# Towards Trust and Reputation as a Service in a Blockchain-based
Decentralized Marketplace

Stephen Olariu  Department of Computer Science, Old Dominion University
Norfolk, Virginia, 23529, USA  Ravi Mukkamalai  Department of Computer
Science, Old Dominion University
Norfolk, Virginia, 23529, USA  Meshari Aljohani  Department of Computer
Science, Old Dominion University
Norfolk, Virginia, 23529, USA

###### Abstract

Motivated by the challenges inherent in implementing trusted services in the
Society 5.0 initiative, we propose a novel trust and reputation service for a
decentralized marketplace. We assume that a Smart Contract is associated with
each transaction and that the Smart Contract is responsible for providing
automatic feedback, replacing notoriously unreliable buyer feedback by a more
objective assessment of how well the parties have fulfilled their obligations.
Our trust and reputation service was inspired by Laplace’s Law of Succession,
where trust in a seller is defined as the probability that she will fulfill
her obligations on the next transaction. We offer three applications. First,
we discuss an application to a multi-segment marketplace, where a malicious
seller may establish a stellar reputation by selling cheap items, only to use
their excellent reputation to defraud buyers in a different market segment.
Next, we demonstrate how our trust and reputation service works in the context
of sellers with time-varying performance by providing two discounting schemes
wherein older reputation scores are given less weight than more recent ones.
Finally, we show how to predict trust and reputation far in the future, based
on incomplete information. Extensive simulations have confirmed our analytical
results.

###### Index Terms:

Society 5.0, service-centric society, decentralized marketplace, smart
contract, trust measure, reputation.

##  I Introduction and motivation

In 2016, the Japanese Government publicized a bold initiative and a call to
action for the implementation of a “Super Smart Society” announced as Society
5.0. The novelty of Society 5.0 is that it embodies a sustainable service-
centric society enabled by the latest digital technologies. Society 5.0 meets
the needs of its members by providing goods and services to the people who
require them when they are required, and in the amount required, thus enabling
its citizens to live an active and comfortable life through the provisioning
of high-quality services [1, 2, 3, 4]. Society 5.0 provides a common societal
infrastructure for prosperity based on an advanced service platform which
turns out to be its main workhorse.

The insight behind Society 5.0 is that continued progress of ICT and digital
technologies of all sorts will provide individuals and society tremendous
opportunities for innovation, growth, and unprecedented prosperity and well-
being through various forms of human-to-human, human-to-machine, and machine-
to-machine cooperations and collaboration. Most of these forms of cooperation
and collaboration between humans and machines or between autonomous machine
systems have yet to be defined and understood.

Services and their effects have been studied intensely in the past two decades
and most of their dynamics are now well understood [5, 6, 7, 8, 9, 10].
Recently, the emergence of Decentralized Autonomous Organizations (DAO) has
motivated the study of service provisioning in decentralized blockchain-based
environments fed by open networks of contributors [11, 12, 13].

Our paper was inspired and motivated by some of the challenges that will have
to be overcome in order to implement Society 5.0. Key among these challenges,
as pointed out by several workers, is providing trusted and secure services
[14, 15, 16]. With this in mind, we set out to explore providing a trust and
reputation service in recently proposed blockchain-based decentralized
marketplaces. To the best of our knowledge, this is the first time such an
effort has been undertaken.

Today, decentralized markets are growing at a rapid pace with all types of
goods and services being transacted online. In such global markets, buyers and
sellers engage in transactions with counterparts with whom they had little or
no previous interaction. This introduces significant risks for both buyers and
sellers. In order to assist buyers (sellers) with the process of choosing a
trustworthy trading partner, marketplaces maintain individual reputation
scores for each seller (buyer) [17, 18, 19, 20]. These reputation scores
capture, in various forms, statistical information about the past behavior of
sellers (buyers) registered with the platform.

The goal of a trust and reputation service is to provide buyers with a robust
framework that allows them to select future transaction partners based on a
combination of objective and subjective trust measures distilled from
accumulated evidence of sellers’ past behavior in the marketplace. The quality
of a trust and reputation service depends, in a fundamental way, on the
quality of the feedback it receives from buyers. This is even more crucial
when we consider decentralized marketplaces, where there is no centralized
control, unlike marketplaces such as Amazon and eBay.

Being a subjective measure, the quality of buyer feedback is notoriously hard
to assess [21, 22, 23]. The fundamental problem is that different buyers may
rate a similar experience with the same seller vastly differently. When
feedback is provided by buyers from around the world, who may value different
aspects of the same transaction differently, it is very hard to know when a
buyer provides truthful feedback.

###  I-A Our contributions

The first main contribution of this paper is to propose a novel blockchain-
based trust and reputation service with the goal of reducing the uncertainty
associated with buyer feedback in decentralized marketplaces.

The second main contribution of the paper is to illustrate three applications
of the proposed blockchain-based trust and reputation service. Specifically,
in Subsections VI-A and VI-B we discuss two applications of our service to a
multi-segment marketplace, where a malicious seller may establish an enviable
reputation by selling cheap items or providing some specific service, only to
use their superb reputation score to defraud buyers in a different market
segment. Next, in Subsection VI-C, we apply the results of Section IV in the
context of sellers with time-varying performance due, for example, to overcome
initial difficulties. We provide two discounting schemes where older
reputation scores are given less weight than more recent ones, thus focusing
attention on current performance. Finally, in Subsection VI-D we show how to
predict trust and reputation scores far in the future, based on incomplete
information.

In our work we assume that a Smart Contract (SC) is associated with each
transaction. We assume that the SC in charge of the transaction is also
responsible for providing feedback at the end of the transaction, replacing
buyer feedback with a more objective assessment of how well the buyer and the
seller have fulfilled their contractual obligations towards each other.

At the heart of any trust and reputation service must lie a trust engine, an
algorithm that takes as input a seller’s reputation score and distills from it
a subjective trust measure, namely the perceived probability that on the next
transaction, the seller will fulfill her contractual obligations. The proposed
trust and reputation engine was inspired by a classic result in probability
theory, namely Laplace’s Law of Succession [24, 25]. We extend Laplace’s
classic result in a way that provides a trust measure in a seller’s future
performance in terms of her past reputation scores.

The remainder of this paper is organized as follows. Section II offers a
succinct review of recently proposed blockchain-based trust and reputation
systems. Section IV introduces the proposed Laplace trust and reputation
service. This is followed by Section V which discusses how the trust measure
is updated over time. Section VI offers three applications of the proposed
Laplace trust and reputation service. Section VII introduces our simulation
model and offers simulation results. Finally, Section VIII offers concluding
remarks and directions for future work.

We wish to alert the reader that an appendix was added for some tedious
mathematical derivations whose inclusion in the main paper would be
distracting.

##  II Blockchain-based reputation systems

Trust and reputation models have long been of interest to economists [26, 27,
28, 29, 30, 31, 32, 33]. The advent of e-commerce has renewed interest in
online transactions where, naturally, trust or lack thereof is a major
concern.

In recent years, a steadily increasing number of workers have investigated
blockchain-based reputation systems wherein SCs may or may not play a
significant role. We refer the reader to the surveys of Hendrix et al. [34],
Bellini et al. [11], and Hasan et al. [12] for a comprehensive discussion.
With this in mind, the main goal of this section is to review some of the
recently proposed blockchain-based reputation systems.

Buechler et al. [35] developed a reputation system where SCs contribute to the
task of reputation scoring by analyzing the underlying network structure.
Their system allows buyers and sellers to query and record the outcomes of
transactions.

Lu et al. [36] proposed a blockchain-based trust model specifically designed
to improve the trustworthiness of messages in Vehicular Ad-hoc Networks
(VANET). However, their system does not use SCs in any capacity. Later, Javaid
et al. [37] proposed a blockchain-based and a trusted Certificate-Authority-
based trust and reputation model for VANET. While SCs are mentioned by the
authors of [37], no specific role for SCs is mentioned in the paper, other
than supporting the functionality of the blockchain. More recently, Singh et
al. [38] have proposed a blockchain-based trust management system in the
context of the Internet of Vehicles [39, 40], an extension of VANET. In their
work, the blockchain provides trust among vehicles that have no reason to
trust each other. The blockchain also manages in a reliable manner trust and
reputation across the Internet of Vehicles. However, although mentioned, there
is no specific role played by SCs in their scheme.

Arshad et al. [41] presented a blockchain-based reputation system that they
call REPUTABLE which computes the reputation of sellers within a blockchain
ecosystem through decentralized on-chain and off-chain implementations.
REPUTABLE ensures privacy, reliability, integrity, and accuracy of reputation
scores, all this with minimal overhead. In order to facilitate gathering buyer
feedback, REPUTABLE employs SCs. However, the SCs are not entrusted with
providing feedback on their own.

##  III The assumed blockchain-based decentralized marketplace

If a reputation system is to be successful, several conditions must be
satisfied: first, the decentralized marketplace must collect, aggregate, and
disseminate seller reputation scores accurately and in a timely manner;
second, buyers provide truthful feedback on their buying experience; and,
third, buyers base the choice of their future transaction partners (i.e.
sellers) solely on reputation scores.

The first and third conditions are relatively easy to enforce or to
incentivize. The second condition is far more problematic. It has been argued
that if buyers consistently provide truthful feedback, isolated interactions
between buyers and sellers take on attributes of long-term relationships and,
as a result, the reputation scores tallied by the marketplace become a high-
quality substitute for community-based reputation [42].

It is not surprisingly, therefore, that numerous authors have proposed
strategies intended to incentivize truthful feedback [43, 44, 45, 46].

In this work we assume a blockchain-based marketplace similar to [47, 17, 19,
18, 20, 48], where the transactions between buyers and sellers are maintained
as individual blocks that, once added to the blockchain, keep immutable
information about the transaction. We maintain statistical information about
the buyers’ and sellers’ performance as part of the blockchain.

##  IV The Laplace trust and reputation service

The main goal of this section is to introduce our trust and reputation
service.

###  IV-A Terminology and definitions

Consider a decentralized marketplace and a new seller $S$ who just joined the
marketplace at time $0$. We associate with the seller an urn containing an
unknown number, $N$, of balls and an unknown composition, in terms of the
number of black balls it contains. The intention is for the urn of unknown
composition to represent the total number of transactions in which seller $S$
will be involved during her career in the marketplace. Here, each black ball
represents a transaction in which seller $S$ has fulfilled her contractual
obligations.

We define the reputation score of the seller at time $t$ as an ordered triple
whose first and second components are, respectively, the total number of
transactions in which the seller was involved up to time $t$ and the number of
transactions in which the seller has fulfilled her contractual obligations up
to time $t$. The third component is $(0,t)$ or, simply, $t$ if no confusion
can arise.

Each transaction in which seller $S$ is involved is associated with a ball
extracted from the urn without replacement. If the extracted ball is black, we
say that the seller has fulfilled her obligations in the corresponding
transaction. The motivation for this is that every time a ball is extracted
from the urn without replacement, the probability of obtaining a black ball on
the next extraction changes. This is intended to capture, to some extent, the
uncertainties and vagaries of seller behavior.

Let $I$ be the random variable denoting the initial number of black balls in
the urn. Let $H_{i}=\\{I=i\\},\ (0\leq i\leq N)$, be the hypothesis that the
initial composition of the urn is $(i,N-i)$, in other words the urn contains
$i$ black balls, while the remaining $N-i$ balls have other colors.

Since nothing is known à priori about the past history, skill level, and
integrity profile of the seller, it makes sense to assume, as an initial
prior, that all compositions of the urn are equiprobable (see [24] for a good
discussion) and so

$\Pr[H_{i}]=\frac{1}{N+1}.$ (1)

We define $\rho_{S}(0,t)$, the trust measure in seller $S$ at time $t$, to be
the probability that the seller will fulfill her contractual obligations on
the next transaction following $t$. In terms of the underlying urn, this means
that the next ball extracted from the urn is black. For example, let $B_{0}$
be the event that on the very first transaction the seller will fulfill her
contractual obligations. Equivalently, $B_{0}$ is the event that, on the first
extraction a black ball will appear. For reasons that will become clear later
we write $\rho_{S}(0,0)$ for $\Pr[B_{0}]$. It is clear that

$\displaystyle\rho_{S}(0,0)=\sum_{i=0}^{N}\Pr[B_{0}|H_{i}]\Pr[H_{i}]=\frac{1}{N+1}\sum_{i=0}^{N}\frac{i}{N}\
\ \ \mbox{[by (\ref{Ci})]}$ (2) $\displaystyle=$
$\displaystyle\frac{1}{N(N+1)}\sum_{i=0}^{N}i$ $\displaystyle=$
$\displaystyle\frac{1}{N(N+1)}\frac{N(N+1)}{2}=\frac{1}{2},$

which makes intuitive sense, since we have no à prior knowledge of the
seller’s past behavior in the marketplace and therefore the trust we place in
her is $\frac{1}{2}$.

###  IV-B Updating the prior

Now, suppose that our seller has accumulated, in the time interval $r([0,t]$,
a reputation score of $(n,k,t)$. Recall that this means that out of a total of
$n$ transactions in which the seller was involved up to time $t$, she has
fulfilled her obligations in $k$ of them. Equivalently, this says that from
the urn mentioned above, a sample of $n$ balls was extracted without
replacement and that $k$ of them were observed to be black.

In order to update the trust measure in our seller, we need to update our
belief in the original composition of the associated urn. For this purpose,
let $A$ be the event that in a sample of $n$ balls extracted without
replacement from the urn, $k$ black balls were observed. Once the event $A$ is
known, we update the prior in a Bayesian fashion by setting

$\displaystyle\Pr[H_{i}|n,k]=\Pr[H_{i}|A]=\frac{\Pr[H_{i}\cap A]}{\Pr[A]}$ (3)
$\displaystyle=$
$\displaystyle\frac{\Pr[A|H_{i}]\Pr[H_{i}]}{\sum_{j=0}^{N}\Pr[A|H_{j}]\Pr[H_{j}]}=\frac{\Pr[A|H_{i}]}{\sum_{j=0}^{N}\Pr[A|H_{j}]}\
\ \mbox{[by (\ref{Ci}).]}$ $\displaystyle=$
$\displaystyle\frac{\frac{{i\choose k}{{N-i}\choose{n-k}}}{{N\choose
n}}}{\sum_{j=0}^{N}\frac{{{j\choose
k}}{{N-j}\choose{n-k}}}{{{N}\choose{n}}}}=\frac{{{i\choose
k}{{N-i}\choose{n-k}}}}{\sum_{j=0}^{N}{{j\choose k}}{{N-j}\choose{n-k}}}$
$\displaystyle=$ $\displaystyle\frac{\frac{{i\choose
k}{{N-i}\choose{n-k}}}{{N\choose
n}}}{\frac{{{N+1}\choose{n+1}}}{{{N}\choose{n}}}}\ \ \ \mbox{[by
(\ref{eq:lovasz-1}) in the Appendix]}$ $\displaystyle=$
$\displaystyle\frac{{{i\choose k}{{N-i}\choose{n-k}}}}{{{N+1}\choose{n+1}}.}$

To summarize, the expression of the updated prior $\Pr[H_{i}|n,k]$ reflects
our updated belief in the initial composition of the urn, as a result of
seeing $k$ black balls out of $n$ balls extracted. In terms of our seller,
upon seeing that the seller has fulfilled her obligations in $k$ out of the
first $n$ transactions, we update the perceived intrinsic performance profile
of our seller. At the risk of mild confusion, we continue to write
$\Pr[H_{i}]$ for the updated prior, instead of more cumbersome
$\Pr[H_{i}|n,k]$.

###  IV-C Modeling the trust measure

Recall that we define a seller’s (subjective) trust measure, $\rho_{S}(0,t)$,
at time $t$ as the probability of the event that on the next transaction the
seller will fulfill her contractual obligations.

###### Theorem IV.1

Assuming that seller $S$ has accumulated, in the interval $(0,t)$, a
reputation score of $(n,k,t)$, the trust measure in $S$ at time $t$ is

$\rho_{S}(0,t)=\frac{k+1}{n+2}.$

###### Proof:

Consider the urn associated with seller $S$ and assume that out of the urn, a
sample of $n$ balls was extracted and $k$ of them were observed to be black.
Let $B$ be the event that the next ball extracted from the urn is black. In
terms of our marketplace, $\Pr[B]$ is precisely $\rho_{S}(0,t)$. By the Law of
Total Probability,

$\Pr[B]=\sum_{i=0}^{N}\Pr[B|H_{i}]\Pr[H_{i}].$ (4)

Observe that $\Pr[B|H_{i}]=\frac{i-k}{N-n}$ and recall that, by (3),
$\Pr[H_{i}]=\frac{{i\choose k}{{N-i}\choose{n-k}}}{{{N+1}\choose{n+1}}}.$ With
this, (4) can be written as

$\displaystyle\rho_{S}(0,t)=\Pr[B]$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{N}\frac{i-k}{N-n}\frac{{i\choose
k}{{N-i}\choose{n-k}}}{{{N+1}\choose{n+1}}}$ $\displaystyle=$
$\displaystyle\frac{\sum_{i=0}^{N}(i-k)\cdot\frac{i!}{k!(i-k)!}{{N-i}\choose{n-k}}}{(N-n)\frac{(N+1)!}{(n+1)!(N-n)!}}$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{N}\frac{(k+1){i\choose{k+1}}{{N-i}\choose{n-k}}}{(N+1){{N}\choose{n+1}}}$
$\displaystyle=$
$\displaystyle\frac{k+1}{N+1}\sum_{i=0}^{N}\frac{{i\choose{k+1}}{{N-i}\choose{n-k}}}{{{N}\choose{n+1}}}$
$\displaystyle=$
$\displaystyle\frac{k+1}{N+1}~{}\frac{{{N+1}\choose{n+2}}}{{{N\choose{n+1}}}}\
\ \ \mbox{[by (\ref{eq:lovasz-1})]}$ $\displaystyle=$
$\displaystyle\frac{k+1}{n+2},$

and the proof of Theorem IV.1 is complete. ∎

###  IV-D Illustrating Theorem IV.1

Somewhat surprisingly, the expression of the trust measure is independent of
$N$ and depends only on $n$ and $k$. It is very important to note that the
expression of the trust measure specified in Theorem IV.1 is very easy to
remember and to compute. Specifically, if a certain seller has accumulated a
reputation score $(n,k,t)$, evaluating the corresponding trust measure in the
seller at time $t$ is very simple. This is one of the significant advantages
of our trust and reputation service.

It is of interest to plot the trust measure of Theorem IV.1 for the cases
where $n$, and $k$ are fixed. First, for fixed $n$, Figure 1 reveals that
$\rho_{S}(0,t)$ features a linear increase in $k$. Indeed, the trust measure
of a seller with a reputation score of $(n,k+1,t)$ and that of a seller with a
reputation score of $(n,k,t)$, differ by
$\frac{k+2}{n+2}-\frac{k+1}{n+2}=\frac{1}{n+2}$.

Figure 1: Illustrating the trust measure for fixed $n$.

On the other hand, Figure 2 shows that for a fixed value of $k$,
$\rho_{S}(0,t)$, perceived as a function of $n$, experiences a hyperbolic
decline. To see this, observe that the trust measure of a seller with a
reputation score of $(n,k,t)$ and that of a seller with a reputation score of
$(n+1,k,t)$, differ by
$\frac{k+1}{n+2}-\frac{k+1}{n+3}=(k+1)\left[\frac{1}{n+2}-\frac{1}{n+3}\right]$.

Figure 2: Illustrating the trust measure for fixed $k$.

To summarize this discussion, we refer the reader to Figure 3 the trust
measure $\rho_{S}(0,t)$ for small values of $n$ and $k$. For a better
illustration, the values of $\rho_{S}(0,t)$ for different values of $k$ are
depicted in different colors. Figure 3 also reveals that
$\rho_{S}(0,0)=\frac{1}{2}$, as we found in (2).

Figure 3: Illustrating $\rho_{S}(0,t)$ for small values of $n$ and $k$

##  V Updating the trust measure

The main goal of this section is to show how the trust measure introduced in
Section IV is updated over time.

###### Theorem V.1

Assume that in the time interval $(0,t]$, seller $S$ was involved in $n$
transactions and that she has fulfilled her contractual obligations in $k$ of
them. If in the time interval $(t,t^{\prime}]$ seller $S$ is involved in
$n^{\prime}$ additional transactions and that she fulfills her contractual
obligations in $k^{\prime}$ of them, then the seller’s trust measure,
$\rho_{S}(0,t^{\prime})$, at time $t^{\prime}$ is

$\rho_{S}(0,t^{\prime})=\frac{k+k^{\prime}+1}{n+n^{\prime}+2}.$ (5)

###### Proof:

Let $A^{\prime}$ be the event that in a subsequent sample of size
$n^{\prime}$, $k^{\prime}$ balls were observed to be black. Once the event
$A^{\prime}$ is known to have occurred, it is necessary to update our prior.
Proceeding, in a Bayesian fashion, we write

$\displaystyle\Pr[H_{i}|n,k,n^{\prime},k^{\prime}]$ $\displaystyle\leftarrow$
$\displaystyle\Pr[H_{i}|A^{\prime}]=\frac{\Pr[H_{i}\cap
A^{\prime}]}{\Pr[A^{\prime}]}$ (6) $\displaystyle=$
$\displaystyle\frac{\Pr[A^{\prime}|H_{i}]\Pr[H_{i}]}{\sum_{j=0}^{N}\Pr[A^{\prime}|H_{j}]\Pr[H_{j}]}.$

Noticing that

  * •

$\Pr[A^{\prime}|H_{i}]=\frac{{i\choose k}{{N-i}\choose{n-k}}}{{N\choose n}}$;

  * •

by (3), $\Pr[H_{i}]=\frac{{{i\choose
k}{{N-i}\choose{n-k}}}}{{{N+1}\choose{n+1}}}$; and,

  * •

by (22) in the Appendix A-B,
$\Pr[A^{\prime}]=\sum_{j=0}^{N}\Pr[A^{\prime}|H_{j}]\Pr[H_{j}]=\frac{{{k+k^{\prime}}\choose
k}{{n-k+n^{\prime}-k^{\prime}}\choose{n-k}}}{{{n+n^{\prime}+1}\choose{n+1}}}$,

equation (6) becomes

$\Pr[H_{i}]=\Pr[H_{i}|n,k,n^{\prime},k^{\prime}]=\frac{{i\choose{k+k^{\prime}}}{{N-i}\choose{n-k+n^{\prime}-k^{\prime}}}}{{{N+1}\choose{n+n^{\prime}+1}}}.$
(7)

As before, in order to simplify notation, we continue to refer to
$\Pr[H_{i}|n,k,n^{\prime},k^{\prime}]$ as $\Pr[H_{i}]$. The expression of the
prior $\Pr[H_{i}]$ in (7) reflects our updated belief in the composition of
the urn, as a result of seeing $k^{\prime}$ black balls out of $n^{\prime}$
balls in the second sample extracted.

Let $B^{\prime}$ be the event that the next ball extracted from the urn is
black. In terms of our marketplace, $\Pr[B^{\prime}]$ is
$\rho_{S}(0,t^{\prime})$.

$\displaystyle\Pr[B^{\prime}]$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{N}\Pr[B^{\prime}|H_{i}]\Pr[H_{i}]$ (8)
$\displaystyle=$
$\displaystyle\sum_{i=0}^{N}\frac{i-k-k^{\prime}}{N-n-n^{\prime}}\frac{{i\choose{k+k^{\prime}}}{{N-i}\choose{n-k+n^{\prime}-k^{\prime}}}}{{{N+1}\choose{n+n^{\prime}+1}}}$
$\displaystyle=$
$\displaystyle\scriptstyle\frac{1}{(N-n-n^{\prime}){{N+1}\choose{n+n^{\prime}+1}}}\sum_{i=0}^{N}(i-k-k^{\prime})\cdot\frac{i!}{(k+k^{\prime})!(i-k-k^{\prime})!}{{N-i}\choose{n-k+n^{\prime}-k^{\prime}}}$
$\displaystyle=$
$\displaystyle\scriptstyle\frac{k+k^{\prime}+1}{(N-n-n^{\prime}){{N+1}\choose{n+n^{\prime}+1}}}\sum_{i=0}^{N}{i\choose{k+k^{\prime}+1}}{{N-i}\choose{n-k+n^{\prime}-k^{\prime}}}$
$\displaystyle=$
$\displaystyle\frac{k+k^{\prime}+1}{(N-n-n^{\prime}){{N+1}\choose{n+n^{\prime}+1}}}{{N+1}\choose{n+n^{\prime}+2}}$
$\displaystyle=$ $\displaystyle\frac{k+k^{\prime}+1}{n+n^{\prime}+2}.$

∎

Notice that, in spite of the laborious derivation, the final result is
extremely simple and easy to compute. This is a definite advantage of our
scheme.

An interesting question is to determine under what conditions the trust
measure $\rho_{S}(0,t^{\prime})$ is at least as large as $\rho_{S}(0,t)$. The
answer to this question is provided by the following result.

###### Lemma V.2

$\rho_{S}(0,t^{\prime})\geq\rho_{S}(0,t)\iff\frac{k^{\prime}}{n^{\prime}}\geq\frac{k+1}{n+2}.$

###### Proof:

Follows by Lemma A.4 in the appendix $a=k+1$, $b=n+2$, $a^{\prime}=k^{\prime}$
and $b^{\prime}=n^{\prime}$. ∎

Figure 4: A geometric interpretation of Lemma V.2.

Refer to Figure 4 for a geometric illustration of Lemma V.2. Consider a two-
dimensional coordinate system where the horizontal and vertical axes capture,
respectively, the total number of transactions and the number of transactions
in which the seller has fulfilled her contractual obligations. Consider,
further, the points $A,\ B,\ C$ of coordinates $(n+2,k+1),\
(n+n^{\prime}+2,k+1),\ (n+n^{\prime}+2,k+k^{\prime}+1)$. It is easy to confirm
that $\rho_{S}(0,t)=\tan\theta=\frac{k+1}{n+2}$, and
$\rho_{S}(0,t^{\prime})=\tan\theta^{\prime}=\frac{k+k^{\prime}+1}{n+n^{\prime}+2}$.
Finally, is is easy to confirm that $\rho_{S}(0,t^{\prime})\geq\rho_{S}(0,t)$
if and only if the angle $\phi$ determined by the sides $AB$ and $AB$ of the
triangle determined by the points $A,\ B,\ C$ satisfies
$\frac{k^{\prime}}{n^{\prime}}=\tan\phi\geq\tan\theta=\frac{k+1}{n+2}$,
exactly as claimed in Lemma V.2.

Theorem V.1 can be readily generalized.

###### Theorem V.3

For an arbitrary positive integer $r$, consider $r$ successive epochs
$(t_{0},t_{1}],\ (t_{1},t_{2}],\ \cdots,\ (t_{i-1},t_{i}],\ \cdots,\
(t_{r-1},t_{r}]$, such that in epoch $(t_{i-1},t_{i}],\ (1\leq i\leq r)$, our
seller was involved in $n_{i}$ transactions and has fulfilled her contractual
obligations in $k_{i}$ of them. Then the seller’s reputation score at time
$t_{r}$ is $(\sum_{i=1}^{r}n_{i},\sum_{i=1}^{r}k_{i},(t_{0},t_{r}))$ and her
associated trust measure is

$\rho_{S}(0,t_{r})=\frac{\sum_{i=1}^{r}k_{i}+1}{\sum_{i=1}^{r}n_{i}+2}.$ (9)

###### Proof:

Assume, without loss of generality, that $t_{0}=0$ and let $t$ and
$t^{\prime}$ denote, respectively, $t_{r-1}$ and $t_{r}$. In the time interval
$(0,t]$ the seller was involved in $\sum_{i=1}^{r-1}n_{i}$ transactions and
has fulfilled her obligations in $\sum_{i=1}^{r-1}k_{i}$ of them. In the time
interval, $(t,t^{\prime}]$ our seller was involved in $n_{r}$ transactions and
has fulfilled her contractual obligations in $k_{r}$ of them.

By definition, in the interval $(0,t^{\prime}]$, the seller’s reputation score
is $(\sum_{i=1}^{r}n_{i},\sum_{i=1}^{r}k_{i},(t_{0},t_{r}))$. Similarly, by
Theorem V.1 her trust measure is

$\displaystyle\rho_{S}(0,t_{r})$ $\displaystyle=$
$\displaystyle\frac{k+k^{\prime}+1}{n+n^{\prime}+2}$ $\displaystyle=$
$\displaystyle\frac{(\sum_{i=1}^{r-1}k_{i})+k_{r}+1}{(\sum_{i=1}^{r-1}n_{i})+n_{r}+2}$
$\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{r}k_{i}+1}{\sum_{i=1}^{r}n_{i}+2},$

and the proof of Theorem V.3 is complete. ∎

Theorem V.3 has a number of consequences:

  * •

the updated trust measure is related to the updated reputation scores, exactly
as specified in Theorem IV.1;

  * •

the updated trust measure does not change if

    * –

Associativity: the seller has fulfilled her obligations in $0$ of the first
$\sum_{i=1}^{r-1}n_{i}$ transactions and in $\sum_{i=1}^{r}k_{i}$ out of the
next $n_{r}$ transactions, provided $\sum_{i=1}^{r}k_{i}\leq n_{r}$.

    * –

Commutativity: for any choice of subscripts $i,j$, with $(1\leq i\neq j\leq
r)$, the $n_{j}$ transactions in epoch $j$ have occurred before or after the
$n_{i}$ transactions in epoch $i$;

    * –

Interchangeability: the seller has fulfilled her obligation in $k_{j}$ of the
$n_{i}$ transactions in epoch $i$ and in $k_{i}$ of the transactions in epoch
$j$, provided that $k_{j}\leq n_{i}$ and $k_{i}\leq n_{j}$.

##  VI Applications of the Laplace Trust Engine

The main goal of this section is to illustrate three applications of the trust
and reputation service introduced in Section IV. Specifically, in Subsections
VI-A and VI-B we discuss two applications to a multi-segment marketplace,
where a malicious seller may establish a very high reputation by selling cheap
items or providing some specific type of service, only to use their reputation
score to defraud buyers in a different market segment.

Next, in Subsection VI-C, we apply the results of Section IV in the context of
sellers with time-varying performance due to an initial learning curve. We
provide two discounting schemes, wherein older reputation scores are given
less weight than more recent ones. Finally, in Subsection VI-D we show how to
predict trust and reputation scores far in the future, based on currently
available information.

###  VI-A Price-range specific trust and reputation

We assume that the transactions in the marketplace are partitioned, by the
monetary value of the goods transacted, into non-overlapping price ranges
$0<R_{1}<R_{2}<\cdots<R_{s}$ for some positive integer $s$. These ranges
determine $s$ market segments $M_{1},M_{2},\cdots,M_{s}$ where market segment
$M_{j}$ involves all the transactions within the price range $R_{j}$.

In all marketplaces of which we are aware [11, 12, 15, 16, 17, 18, 19, 20, 22,
23], seller reputation is global, being established irrespective of their
performance in different market segments.

However, this may lead to insecurities. For example, imagine a seller that has
established an enviable reputation score by selling cheap items, all in the
market segment corresponding to the range $R_{1}$. Suppose that our seller
decides to get involved in a different market segment, say corresponding to
price range $R_{10}$. Should her reputation score established in $R_{1}$ carry
over to $R_{10}$? We believe that the answer should be in the negative. One
reason is that, as pointed out by [49] and other workers, dishonest sellers
establish stellar reputation scores by selling cheap items and use the
resulting reputation score to hit-and-run in a different market segment.

To prevent this kind of attack from being mounted, we associate with each
market segment a distinct reputation score and, consequently, a distinct trust
measure. Also, with each market segment, we associate a different urn as
discussed in the previous sections of this work. For example, if our seller
has never transacted in the market segment corresponding to the price range
$R_{10}$, her reputation score in that market segment is $(0,0,t)$ and, not
surprisingly, her corresponding trust measure will be
$\frac{0+1}{0+2}=\frac{1}{2}=50\%$, capturing the idea that nothing is known
about the performance of the seller in that market segment.

Consider a generic market segment $M_{i},\ (1\leq i\leq s)$, and assume that
up to time $t$, our seller has accumulated a reputation score of
$(n_{i},k_{i},t)$ in $R_{i}$. Consistent with our definition, the trust
measure that our seller enjoys in $M_{i}$ is $\frac{k_{i}+1}{n_{i}+2}$. This
trust measure is local to $M_{i}$ and is independent of the seller’s trust
measure in other market segments.

It is worth noting that, as an additional benefit, our approach provides
resistance to Sybil attacks. It is well known that malicious users involve
their Sybils in augmenting their reputation scores [50, 51, 13, 52]. However,
the fact that by assumption Smart Contracts are responsible for providing
transaction feedback (including the market segment in which the transaction
took place), this feedback will be, perforce, local to one market segment,
minimizing the effect of the attack. Indeed, as a result of the Sybil attack,
the malicious user’s reputation may well increase in one market segment, but
her reputation in other market segments will not be affected. This provides
for very desirable resistance to Sybil attacks.

###  VI-B Service-specific trust and reputation

In Subsection VI-A we argued that reputation scores and, therefore, the trust
measure of a seller should not be global but should, instead, be specific to
individual price ranges. Specifically, we made the point that reputation
scores acquired by doing business in one market segment (by dollar amount)
should not carry over to a different market segment.

In this subsection, we extend the same idea to the types of services provided.
The intuition is that a service provider (i.e. seller) may behave differently
when providing different services. Thus, the best indicator of how the service
provider will perform in the future depends on their past performance in the
context of the type of services contemplated. This motivates assessing the
trustworthiness of a service provider by the type of individual service of
interest.

As an illustrative example, consider a plumbing contractor who may act in the
marketplace as a seller of plumbing hardware, but also as a provider of
plumbing services such as repairs, installation of various equipment such a
gas furnaces, electric furnaces, hot water heaters, or extended maintenance
contracts, etc.

Our plumber may be inclined to provide higher quality services in areas that
benefit him most (e.g. installing electric water heaters) and of lesser
quality in some other areas that are less lucrative, e.g. maintenance
contracts or installing gas water heaters), even though an electric water
heater may cost roughly the same as a gas water heater.

The point is that the plumber’s reputation score acquired by providing one
type of service should not be relevant when evaluating his/her trustworthiness
in different service categories where he/she is either less competent or
simply not interested in providing high-quality services.

###  VI-C Discounting old trust measures

Up to this point, we have assumed that seller behavior is constant over time.
For various reasons, sellers may well change their attitude and behave
differently from the way they acted in the past. To accommodate this
imponderable, in this subsection we introduce two simple mechanisms that allow
us to discount older trust measures, giving more credence to recent reputation
scores.

For an arbitrary integer $r$, consider $r$ successive time epochs
$(t_{0},t_{1}],\ (t_{1},t_{2}],\ \cdots,\ (t_{i-1},t_{i}],\ \cdots,\
(t_{r-1},t_{r}]$ with $t_{0}=0$ and such that in epoch $(t_{i-1},t_{i}],\
(1\leq i\leq r)$, our seller was involved in $n_{i}$ transactions and has
fulfilled her contractual obligations in $k_{i}$ of them. Recall that, given
this information, the seller’s reputation score at time $t_{r}$ is
$(\sum_{i=1}^{r}n_{i},\sum_{i=1}^{r}k_{i},(t_{0},t_{r}))$ and, by Theorem V.3,
her associated trust measure is

$\rho_{S}(0,t_{r})=\frac{\sum_{i=1}^{r}k_{i}+1}{\sum_{i=1}^{r}n_{i}+2}.$ (10)

####  VI-C1 First discounting scheme

In order to produce a weighted version of (10), consider non-negative rational
numbers $\lambda_{1},\ \lambda_{2},\ \cdots,\lambda_{r}$ Assuming $\sum_{1\leq
j\leq r}\lambda_{j}\neq 0$, define weights $0\leq w_{1},\ w_{2},\ \cdots,\
w_{r}\leq 1$, where, for all $i,\ (1\leq i\leq r)$,

$w_{i}=\frac{\lambda_{i}}{\sum_{j=1}^{r}\lambda_{j}}.$

Assuming $\sum_{1\leq j\leq r}\lambda_{i}\neq 0$, define the following
weighted version of (10):

$\displaystyle D_{S}(0,t_{r})$ $\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{r}w_{i}k_{i}+1}{\sum_{i=1}^{r}w_{i}n_{i}+2}$
(11) $\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{r}\frac{\lambda_{i}k_{i}}{\sum_{j=1}^{r}\lambda_{j}}+1}{\sum_{i=1}^{r}\frac{\lambda_{i}n_{i}}{\sum_{j=1}^{r}\lambda_{j}}+2}$
$\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{r}\lambda_{i}k_{i}+\sum_{i=1}^{r}\lambda_{i}}{\sum_{i=1}^{r}\lambda_{i}k_{i}+2\sum_{i=1}^{r}\lambda_{i}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{r}\lambda_{i}(k_{i}+1)}{\sum_{i=1}^{r}\lambda_{i}(n_{i}+2)}.$

It is clear that by varying the $\lambda_{i}$s we can give different weights
to the past versus more recent trust measures of the seller. For example, by
taking $\lambda_{i}=0$ for $1\leq i\leq r-1$ and $\lambda_{r}=1$, the past
performance of the seller is ignored and the discounted trust measure
$D_{S}(0,t_{r})$ reduces to the most recent trust measure. Conversely, by
taking $\lambda_{i}=1$, for $(1\leq i\leq r-1)$, and $\lambda_{r}=0$, the past
is given more weight to the detriment of the more recent performance. We claim
that

###### Lemma VI.1

$\min_{1\leq i\leq r}\frac{k_{i}+1}{n_{i}+2}\leq D_{S}(0,t_{r})\leq\max_{1\leq
i\leq r}\frac{k_{i}+1}{n_{i}+2},$ (12)

###### Proof:

Assume, without loss of generality, that $\frac{a_{j}+1}{b_{j}+2}=\max_{1\leq
i\leq r}\frac{k_{i}+1}{n_{i}+2}$. The proof of the rightmost inequality in the
chain above follows directly from Lemma A.3 in the appendix file by setting
$a_{0}=k_{j}+1$, $b_{0}=n_{j}+2$, and for all $i,\ (1\leq i\leq r)$,
$a_{i}=k_{i}+1$ and $b_{i}=n_{i}+2$. The leftmost inequality is followed by a
mirror argument. ∎

Lemma VI.1 shows that the discounted trust measure cannot improve the overall
trust measure. It can, however, focus attention to more recent performance
that, in many contexts, may be more relevant.

####  VI-C2 Second discounting scheme

We find it useful to inherit the notation and terminology developed in the
previous subsection. In order to produce a simple discounting scheme, we
compute a weighted average of the seller trust measure in each of the $r$ time
epochs. Indeed, consider the time interval $(0,t_{r}]$ during which a seller
has been active in the marketplace. Let
$0=t_{0}<t_{1}<t_{2}<\cdots<t_{r-1}<t_{r}$ be an arbitrary partition of
$(0,t_{r}]$. Assume, further, that for all $i,\ (1\leq i\leq t)$, in the time
interval $(t_{i-1},t_{i}]$ the seller has accumulated a reputation score
$(n_{i},n_{i},t_{i}-t_{i-1})$. Define non-negative weights $w_{1},\ w_{2},\
\cdots,\ w_{r}$, with $\sum_{i=1}^{r}w_{i}=1$, and define the weighted trust
measure of the seller in the time interval $(t_{0},t_{r}]$ as

$D^{\prime}_{S}(0,t_{r})=\sum_{i=1}^{r}w_{i}\times\frac{k_{i}+1}{n_{i}+2}.$
(13)

It is clear that by varying the $w_{i}$s we can give different weights to the
past versus more recent trust measure of the seller. It is also easy to see
that the following result holds, mirroring (12).

###### Lemma VI.2

$\min_{1\leq i\leq r}\frac{k_{i}+1}{n_{i}+2}\leq
D^{\prime}_{S}(0,t_{r})\leq\max_{1\leq i\leq r}\frac{k_{i}+1}{n_{i}+2},$ (14)

###### Proof:

We prove that $D^{\prime}_{S}(0,t_{r})\leq\max_{1\leq i\leq
r}\frac{k_{i}+1}{n_{i}+2}$. The proof that $\min_{1\leq i\leq
r}\frac{k_{i}+1}{n_{i}+2}\leq D^{\prime}_{S}(0,t_{r})$ is similar and,
therefore, omitted. As before, assume without loss of generality that
$\frac{a_{j}+1}{b_{j}+2}=\max_{1\leq i\leq r}\frac{k_{i}+1}{n_{i}+2}$. With
this assumption, we write

$\displaystyle D^{\prime}_{S}(0,t_{r})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{r}w_{i}\times\frac{k_{i}+1}{n_{i}+2}$ (15)
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{r}w_{i}\times\frac{k_{j}+1}{n_{j}+2}$
$\displaystyle=$ $\displaystyle\frac{k_{j}+1}{n_{j}+2}\sum_{i=1}^{r}w_{i}$
$\displaystyle=$ $\displaystyle\frac{k_{j}+1}{n_{j}+2}.$

This completes the proof of Lemma VI.2. ∎

Just like Lemma VI.1, Lemma VI.2 tells us that the discounted trust measure
will not improve the overall trust measure. It can, and does, focus attention
on more recent performance that, in many contexts, may be of more relevance.

###  VI-D Predicting trust measure and reputation scores over the long term

It is of great theoretical interest and practical relevance to be able to
extrapolate the correct performance of a seller and predict her performance,
far in the future. With this in mind, consider a seller that has completed $n$
transactions and has fulfilled her obligations in $k$ of them. Let $A$ be the
corresponding event. We are interested in predicting the expected reputation
score of the seller by the time her total number of transactions has reached
$n+m$ for some $m\geq 0$.

Let $R$ be the random variable that keeps track of the number of black balls
among the additional $m$ balls extracted, and assume that the event
$\\{R=r\\}$ has occurred.

Using the expression of $H_{i}$ from (3), the conditional probability of the
event $\\{R=r\\}$ given $A$ is

$\displaystyle\Pr[R=r|A]$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{N}\Pr[R=r|H_{i}]\Pr[H_{i}]$ (16) $\displaystyle=$
$\displaystyle\frac{{{k+r}\choose
k}{{n-k+m-r}\choose{n-k}}}{{{n+m+1}\choose{n+1}}}.$

Actually, this follows directly from (25) in Subsection A-B of the Appendix by
taking $r=k^{\prime}$ and $m=n^{\prime}$.

We are interested in evaluating the conditional expectation, $E[R|A]$, of $R$
given $A$. For this purpose, using the Law of Total Expectation, we write

$\displaystyle E[R|A]$ $\displaystyle=$
$\displaystyle\sum_{r=0}^{m}r\Pr[R=r|A]$ $\displaystyle=$
$\displaystyle\sum_{r=0}^{m}r\cdot\frac{{{k+r}\choose
k}{{n-k+m-r}\choose{n-k}}}{{{n+m+1}\choose{n+1}}}\ \ \ \mbox{[By
(\ref{K=k'})]}$ $\displaystyle=$
$\displaystyle\sum_{r=0}^{m}\left[(k+r+1)-(k+1)\right]\cdot\frac{{{k+r}\choose
k}{{n-k+m-r}\choose{n-k}}}{{{n+m+1}\choose{n+1}}}$ $\displaystyle=$
$\displaystyle\sum_{r=0}^{m}(k+r+1)\frac{{{k+r}\choose
k}{{n-k+m-r}\choose{n-k}}}{{{n+m+1}\choose{n+1}}}$ $\displaystyle-$
$\displaystyle\sum_{r=0}^{m}(k+1)\frac{{{k+r}\choose
k}{{n-k+m-r}\choose{n-k}}}{{{n+m+1}\choose{n+1}}}$ $\displaystyle=$
$\displaystyle\sum_{r=0}^{m}(k+r+1)\frac{{{k+r}\choose
k}{{n-k+m-r}\choose{n-k}}}{{{n+m+1}\choose{n+1}}}$ $\displaystyle-$
$\displaystyle(k+1)\sum_{r=0}^{m}\frac{{{k+r}\choose
k}{{n-k+m-r}\choose{n-k}}}{{{n+m+1}\choose{n+1}}}.$

The two sums will be evaluated separately. We begin by evaluating the
following sum:

$\displaystyle\sum_{r=0}^{m}\frac{{{k+r}\choose
k}{{n-k+m-r}\choose{n-k}}}{{{n+m+1}\choose{n+1}}}$ $\displaystyle=$
$\displaystyle\sum_{r=0}^{m}\frac{{{k+r}\choose
k}{{n-k+m-r}\choose{n-k}}}{{{n+m+1}\choose{n+1}}}$ $\displaystyle=$
$\displaystyle\frac{\sum_{r=0}^{m}{{k+r}\choose
k}{{n-k+m-r}\choose{n-k}}}{{{n+m+1}\choose{n+1}}}$ $\displaystyle=$
$\displaystyle\frac{{{n+m+1}\choose{n+1}}}{{{{n+m+1}\choose{n+1}}}}=1.$

This implies that the second sum is $k+1$. Next, to evaluate the first sum, we
notice that

$\displaystyle(k+k^{\prime}+1){{k+k^{\prime}}\choose k}$ $\displaystyle=$
$\displaystyle\frac{k+1}{u+1}(k+k^{\prime}+1)\frac{(k+k^{\prime})!}{k!k^{\prime}!}$
(17) $\displaystyle=$
$\displaystyle(k+1)\frac{(k+k^{\prime}+1)!}{(k+1)!k^{\prime}!}$
$\displaystyle=$ $\displaystyle{{k+k^{\prime}+1}\choose{k+1}}.$

Using (17), the first sum can be written as

$\displaystyle\sum_{r=0}^{m}(k+r+1)\frac{{{k+r}\choose
k}{{n-k+m-r}\choose{n-k}}}{{{n+m+1}\choose{n+1}}}$ (18) $\displaystyle=$
$\displaystyle\frac{k+1}{{{{n+m+1}\choose{n+1}}}}\sum_{r=0}^{m}{{k+r+1}\choose{k+1}}{{n-k+m-r}\choose{n-k}}$
$\displaystyle=$
$\displaystyle\frac{k+1}{{{{n+m+1}\choose{n+1}}}}{{n+m+2}\choose{n+2}}$
$\displaystyle=$ $\displaystyle(k+1)\frac{n+m+2}{n+2}.$

By combining the intermediate results developed above, the expression of
$E[R|A]$ becomes

$\displaystyle E[R|A]$ $\displaystyle=$
$\displaystyle\sum_{r=0}^{m}(k+r+1)\frac{{{k+r}\choose
k}{{n-k+m-r}\choose{n-k}}}{{{n+m+1}\choose{n+1}}}$ (19) $\displaystyle-$
$\displaystyle(k+1)\sum_{r=0}^{m}\frac{{{k+r}\choose
k}{{n-k+m-r}\choose{n-k}}}{{{n+m+1}\choose{n+1}}}$ $\displaystyle=$
$\displaystyle(k+1)\frac{n+m+2}{n+2}-(k+1)$ $\displaystyle=$
$\displaystyle(k+1)\left[\frac{n+m+2}{n+2}-1\right]$ $\displaystyle=$
$\displaystyle m\cdot\frac{k+1}{n+2}.$

The intuition behind this simple result is as follows: since nothing is known
about the future, in each of the $m$ hypothetical extractions from the urn,
the success probability, is the same, namely, $\frac{k+1}{n+2}$. Thus, by a
well-known result, the expectation of the number of successes must be
$m\cdot\frac{k+1}{n+2}$.

Let us translate (19) into the language of trust and reputation. Consider a
seller with a current reputation score of $(n,k,t)$. We are interested in
predicting the reputation score of the seller by time $T$ when her total
number of transactions has reached $n+m$. By (19), it follows that out of a
total of $n+m$ transactions, the predicted number of transactions in which our
seller has fulfilled her obligations is $k+m\frac{k+1}{n+2}$.

To put it differently, the expected reputation score of the seller by time
$T$, when she was involved in $n+m$ transactions, is
$(n+m,k+m\frac{k+1}{n+2},T)$. Interestingly, as the following derivation
shows, the seller’s predicted trust measure at time $T$ is still
$\frac{k+1}{n+2}$.

$\displaystyle\rho_{S}(0,T)$ $\displaystyle=$
$\displaystyle\frac{k+m\frac{k+1}{n+2}+1}{n+m+2}$ (20) $\displaystyle=$
$\displaystyle\frac{k(n+2)+m(k+1)+n+2}{(n+2)(n+m+2)}$ $\displaystyle=$
$\displaystyle\frac{k(n+m+2)+n+m+2}{(n+2)(n+m+2)}$ $\displaystyle=$
$\displaystyle\frac{(k+1)(n+m+2)}{(n+2)(n+m+2)}$ $\displaystyle=$
$\displaystyle\frac{k+1}{n+2}.$

##  VII Simulation results

The goal of this section is to present the results of our empirical evaluation
of the trust and reputation service discussed, analytically, in Sections IV –
VI.

###  VII-A Simulation model

For the purpose of empirical evaluation, we have simulated a blockchain-based
decentralized marketplace with SC support. The actors in the marketplace are
the buyers and the sellers. We assume that a SC is associated with each
transaction and, for simplicity, that each transaction involves one buyer and
one seller. The SC in charge of the transaction is responsible for providing
feedback at the end of the transaction, replacing notoriously unreliable buyer
feedback with a more objective assessment of how well the buyer and the seller
have fulfilled their contractual obligations towards each other.

The marketplace simulation model consists of a seller who was involved in
transactions with multiple buyers. Each transaction can be either successful
(indicating that the seller has fulfilled her contractual obligations) or
failed otherwise. In the simulation, we tracked the number of successful
transactions and the total number of transactions. The probability of a
successful transaction is determined based on the goals of the experiment as
we explain in the following subsections. For each goal, we repeated the
experiment a large number of times, as needed.

The remainder of this section is structured as follows. In Subsection VII-B we
turn our attention to a multi-segment marketplace (by dollar value of the
goods transacted) and illustrate, by simulation, the reputation scores and
trust measure of a generic seller in these market segments. Next, in
Subsection VII-C we present simulation results of seller performance in a
marketplace segmented by service type, not price range. This is followed, in
Subsection VII-D, by a simulation of the effect of two discounting strategies
on the trust measure of a generic seller. Finally, in Subsection VII-E we
predict, by simulation, the future reputation scores and trust measure of a
generic seller, using currently available, incomplete information.

###  VII-B Trust measure in a price-range based multi-segment marketplace

The purpose of this subsection is to illustrate, by simulation, the trust
measure of a seller in different market segments defined by the dollar value
of the goods transacted. For the simulation, we assume that the transactions
in the marketplace are divided into four non-overlapping price ranges
$R_{1},R_{2},R_{3}$, and $R_{4}$, based on the monetary value of the items
transacted. These four price ranges determine four disjoint market
segments—$M_{1},M_{2},M_{3},M_{4}$, where market segment $M_{i}$ includes all
transactions falling within the price range $R_{i}$.

We have simulated a seller that has accumulated, over a time window of 250
units, the following performance in each of the four market segments:

  * •

In market segment $M_{1}$ the seller had 85 successful transactions out of 100
total transactions;

  * •

In market segment $M_{2}$ the seller had 3 successful transactions out of 3
total transactions;

  * •

In market segment $M_{3}$ the seller had 1 successful transaction out of 1
total transaction; and,

  * •

In market segment $M_{4}$ the seller had zero transactions;

Figure 5 illustrates the seller’s trust measure in each of the four market
segments using (IV.1) from Theorem IV.1.

Figure 5: Illustrating the trust measure in a price-based multi-segment
market.

Not surprisingly, even though the trust measure of the seller in market
segment $M_{1}$ is fairly high, 86/102, her trust measure in market segment
$M_{3}$ is a meager 2/3, while in market segment $M_{4}$ the seller’s
performance is only 1/2, reflecting the fact that the seller has had no
experience in the market segment. As a result, the seller cannot misrepresent
her performance.

###  VII-C Trust measure in a service-type based multi-segment marketplace

In Subsection VI-A we argued that the reputation scores and trust measure of a
seller should not be global but should, instead, be specific to individual
price ranges. In Subsection VI-B we extended the same idea to various types of
services and made the point that the best indicator of how the service
provider will perform in the future depends on their past performance in the
context of the type of services contemplated.

This motivated us to assess the trustworthiness of a service provider by the
type of individual service of interest. With this in mind, we have simulated
the evolution of reputation scores and trust measures of a plumbing contractor
who is offering the following services: electric heater installation, gas
heater installation, general plumbing repairs, long-term maintenance
contracts, sewer repairs, and gas boiler service.

Some of these services are more lucrative than others and our plumber is more
competent in dealing with electricity than with gas equipment installation and
repairs. Thus, our plumber may be inclined to provide higher quality services
in areas that benefit him most (e.g. installing electric water heaters and
general plumbing repairs) and of lesser quality in some other areas that are
less lucrative, e.g. installing gas water heaters or providing sewer repairs.
We note that in this case, the quality of a service is not necessarily price
range dependent, because an electric water heater may cost roughly the same as
a gas water heater.

The point is that the plumber’s reputation score acquired by providing one
type of service should not be relevant when evaluating his/her trustworthiness
in different service categories where he/she is either less competent or
simply not interested in providing high-quality services. In our simulations,
our plumber has accumulated the following performance in each of the six
service categories:

  * •

In the electric heater installation category, the plumber had 92 successful
transactions out of 93 transactions;

  * •

In the gas heater installation category, the plumber had 11 successful
transactions out of 29 transactions;

  * •

In the general plumbing repairs category, the plumber had 39 successful
transactions out of 48 transactions;

  * •

In the maintenance contract category, the plumber had 58 successful
transactions out of 98 transactions;

  * •

In the gas boiler service category, the plumber had 3 successful transactions
out of 18 transactions;

  * •

In the sewer repairs category, the plumber had 0 successful transactions out
of 0 transactions.

Figure 6 illustrates our plumber’s trust measure in each of the service
categories above.

Thus, if a consumer wishes to hire a trustworthy plumbing contractor for gas
boiler service, our plumber has nothing to recommend him in that service
category, even though they have a stellar performance in electric water heater
installation.

Figure 6: Illustrating a plumber’s trust measure in a service-based multi-
segment market.

###  VII-D Illustrating the effect of discounting strategies

We have simulated the reputation scores and associated trust measure, of a
generic seller in six time epochs, each one week long. Each epoch has its own
success rate, as detailed below.

  * •

Epoch 1: time range from 0 to 250 with a success rate of 0.55;

  * •

Epoch 2: time range from 250 to 500 with a success rate of 0.65;

  * •

Epoch 3: time range from 500 to 750 with a success rate of 0.70;

  * •

Epoch 4: time range from 750 to 1000 with a success rate of 0.75;

  * •

Epoch 5: time range from 1000 to 1250 with a success rate of 0.80;

  * •

Epoch 6: time range from 1250 to 1500 with a success rate of 0.90.

Initially, the seller’s reputation scores were low, perhaps because of her
lack of experience. We have simulated the effect of the two discounting
strategies presented in Section VI. Table I displays the different weights
utilized as discounting parameters:

| $\lambda_{1}$ | $\lambda_{2}$ | $\lambda_{3}$ | $\lambda_{4}$ | $\lambda_{5}$ | $\lambda_{6}$
---|---|---|---|---|---|---
Experiment 1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.5
Experiment 2 | 0.0 | 0.0 | 0.1 | 0.2 | 0.2 | 0.5
Experiment 3 | 0.0 | 0.0 | 0.0 | 0.0 | 0.5 | 0.5
Experiment 4 | 0.0 | 0.0 | 0.0 | 0.0 | 0.4 | 0.6
Experiment 5 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 1.0
Experiment 6 | 0.17 | 0.17 | 0.17 | 0.17 | 0.17 | 0.17
TABLE I: Various Weights as Discounting Parameters

The results of the simulation with each experiment color-coded are summarized
in Figure 7. In the figure we have plotted, side by side, the seller’s
aggregate trust measure without discounting as well as her trust measure
weighted as described. In the figure, it becomes obvious the effect of
favoring recent performance over more remote performance. As it turns out,
selecting the weights that focus attention on the performance of the seller in
the last week presents her trust measure in the best light, as it is,
conceivably, the most accurate reflection of her improvement.

Figure 7: A first Illustration the two discounting strategies in Subsection
VI-C.

###  VII-E Predicting trust measure and reputation scores over the long term

In this subsection, we are presenting the results of simulating the
convergence of the predicted and simulated long-term trust measure of a
seller. For this purpose, we have simulated the performance of a seller in her
first 100 transactions. Our goal was to see how close is the prediction of the
expected number of her successful transactions among the next 100
transactions. The results of the simulation are plotted in Figure 8. The
simulation was repeated between 50 and 150 times. From the figure, it is clear
that the seller’s simulated long-term performance, in terms of her reputation
scores (and associated trust measure) converges to the theoretically predicted
performance.

Figure 8: Illustrating the convergence of the simulated prediction of long-
term trust measure to the theoretical prediction of Subsection VI-C.

##  VIII Concluding remarks

This paper was motivated by the multi-fold challenges inherent in implementing
the vision of trusted and secure services in Society 5.0.

The first main contribution of this paper was a novel trust and reputation
service with a view to reducing the uncertainty associated with buyer feedback
in decentralized marketplaces. Our trust and reputation service was inspired
by a classic result in probability theory that can be traced back to Laplace.

The second main contribution of the paper was to offer three applications of
the proposed trust and reputation service.

Specifically, in Subsections VI-A and VI-B we discussed two applications to a
multi-segment marketplace, where a malicious seller may establish a stellar
reputation by selling cheap items or providing some specific service, only to
use their excellent reputation score to defraud buyers in a different market
segment. As we noted, our service can provide Sybil resistance is a much-
desired attribute.

Next, in Subsection VI-C, we applied the results of Section IV in the context
of sellers with time-varying performance due, for example, to fighting an
initial learning curve or other similar impediments. We provided two
discounting schemes wherein less recent reputation scores are given less
weight than more recent ones. In Subsection VI-D we showed how to use or trust
and reputation services to predict reputation scores far in the future, based
on fragmentary information.

Last, but certainly not least, the reputation and trust service developed in
this paper seems to have applications for several domains, including banking,
inventory management, vehicular networks [37], peer-to-peer networking [36],
and vehicular clouds [39]. Exploring these new application domains promises to
be an exciting area for future work.

## References

  * [1] A. Deguchi, C. Hirai, H. Matsuoka, T. Nakano, K. Oshima, M. Tai, and S. Tani, _What Is Society 5.0?_ Tokyo, Japan, 05 2020, pp. 1–23.
  * [2] M. E. Gladden, “Who will be the members of society 5.0? towards an anthropology of technologically posthumanized future societies,” _Social Sciences_ , vol. 8, no. 5, p. 148, May 2019. [Online]. Available: http://dx.doi.org/10.3390/socsci8050148
  * [3] Hitachi-UTokyo Laboratory (H-UTokyo Lab), _Society 5.0 – A People-centric Super-smart Society_. Berlin: Springer Open, 2020.
  * [4] Y. Shiroishi, K. Uchiyama, and N. Suzuki, “Society 5.0: For human security and well-being,” _IEEE Computer_ , vol. 51, no. 7, pp. 91–95, July 2018.
  * [5] H. Chesbrough and J. Spohrer, “A research manifesto for service science,” _Communications of the ACM_ , vol. 7, no. 49, pp. 35–40, July 2006.
  * [6] R. Larson, “Smart service systems: Bridging the silos,” _Service Science_ , vol. 8, no. 4, pp. 359–367, 2016.
  * [7] P. Maglio and J. Spohrer, “Fundamentals of service science,” _Journal of the Academy of Marketing Science_ , vol. 36, no. 1, pp. 18–20, 2008.
  * [8] P. Maglio, S. Vargo, N. Caswell, and J. Spohrer, “The service system is the basic abstraction of service science,” _Information Systems and e-business Management_ , vol. 7, no. 4, pp. 395–406, 2009.
  * [9] A. Medina-Borja, “Smart things as service providers: A call for convergence of disciplines to build a research agenda for the service systems of the future,” _Service Science_ , vol. 7, no. 1, pp. ii–v, 2015.
  * [10] J. Spohrer, P. Maglio, J. Bailey, and D. Gruhl, “Toward a science of service systems,” _IEEE Computer_ , vol. 40, no. 1, pp. 71–77, January 2007.
  * [11] E. Bellini, Y. Iraqi, and E. Damiani, “Blockchain-based distributed trust and reputation management systems: A survey,” _IEEE Access_ , vol. 8, pp. 21 127–21 151, 2020.
  * [12] O. Hasan, L. Brunie, and E. Bertino, “Privacy-preserving reputation systems based on blockchain and other cryptographic building blocks: A survey,” _ACM Computing Surveys (CSUR)_ , vol. 55, no. 2, pp. 1–37, 2022.
  * [13] C. Santana and L. Albareda, “Blockchain and the emergence of decentralized autonomous organizations (DAO): An integrative model and research agenda,” _Technological Forecasting & Social Change_, vol. 182, 2022.
  * [14] T. Kaji, Y. Takahashi, A. Shimura, and M. Yoshino, “Trusted and secure service system for society 5.0,” _Hitachi Review_ , pp. 81–85, November 2021.
  * [15] A. Gandini, I. Pais, and D. Beraldo, “Reputation and trust on online labor markets: the reputation economy of elance,” _Work Organisation, Labour and Globalisation_ , vol. 16, pp. 27–43, 2016.
  * [16] F. Adebesin and R. Mwalugha, “The mediating role of organizational reputation and trust in the intention to use wearable health devices: Cross-country study,” _JMIR Mhealth Uhealth_ , vol. 20, 2020.
  * [17] V. Koutsos, D. Papadopoulos, D. Chatzoloulos, S. Tarkoma, and P. Hui, “Agora: A privacy-aware data marketplace,” _IEEE Transactions on Dependable and Secure Computing_ , 2021.
  * [18] Y. Peng, M. Du, F. Li, R. Cheng, and D. Song, “FalconDB: Blockchain-based collaborative database,” in _Proceedings of ACM SIGMOD’2020_ , Portland, Oregon, June 14-19, 2020.
  * [19] K. Soska, A. Kwon, N. Christin, and S. Devadas, “Beaver: a decentralized anonymous marketplace with secure reputation,” Cryptology ePrint Archive: Report 2016/464, 2016.
  * [20] M. Travizano, C. Sarraute, G. Ajzenman, and M. Minnoni, “Wibson: A decentralized data marketplace,” in _Proc. ACM Workshop on Blockchain and Smart Contracts_ , San Francisco, CA, 2018.
  * [21] D. de Siqueira Braga, M. Niemann, B. Hellingrath, and F. B. de Lima-Neto, “Survey on computational trust and reputation models,” _ACM Computing Surveys_ , vol. 51, pp. 1 – 40, November 2018.
  * [22] A. Jøsang and R. Ismail, “The beta reputation system,” in _Proceedings of 15-th Bled Electronic Commerce Conference, e-Reality: Constructing the e-Economy_ , Bled, Slovenia, June, 17–19, 2002.
  * [23] W. T. Teacy, J. Patel, N. R. Jennings, and M. Luck, “TRAVOS: Trust and reputation in the context of inaccurate information sources,” _Autonomous Agents and Multi-Agent Systems_ , no. 2, pp. 183–198, 2006.
  * [24] S. Geisser, “On prior distributions for binary trials,” _The American Statistician_ , no. 4, pp. 244–247, November 1984.
  * [25] S. L. Zabell, “The rule of succession,” _Erkenntnis_ , pp. 283–321, 1989.
  * [26] F. Bass, “A new product growth for model consumer durables,” _Management Science_ , vol. 15, no. 5, pp. 215–227, 1969.
  * [27] D. Bergemann, A. Bonatti, and A. Smolin, “The design and price of information,” _American Economic Review_ , no. 1, pp. 1–48, 2018.
  * [28] S. Frederick, G. Loewenstein, and T. O’Donoghue, “Time discounting and time preference: A critical review,” _Journal of Economic Literature_ , vol. XL, pp. 351–401, 2002.
  * [29] R. Howard, “Information value theory,” _IEEE Transactions on Systems Science and Cybernetics_ , vol. 2, no. 1, pp. 22–26, August 1966.
  * [30] D. Lucking-Reiley, “Auctions on the Internet: What’s beig auctioned and how,” _Journal of Inducstrial Economics_ , vol. 48, pp. 227–252, 2000.
  * [31] P. Resnick, R. Zeckhauser, J. Swanson, and K. Lockwood, “The value of reputation on eBay,” _Experimental Economics_ , no. 2, pp. 79–101, 2006.
  * [32] C. Shapiro, “Premiums for high quality products as returns to reputation,” _Quarterly Journal of Economics_ , vol. 98, pp. 659–680, 1983.
  * [33] K. Waehrer, “A mode of auction contracts for liquidated damages,” _Journal of Economic Theory_ , pp. 531–555, 1995.
  * [34] F. Hendrix, K. Bubendorfer, and R. Chard, “Reputation systems: A survey and taxonomy,” _Journal of Parallel and Distributed Computing_ , vol. 75, 2014.
  * [35] M. Buechler, M. Eerabathini, C. Hockenbrocht, and D. Wan, “Decentralized reputation system for transaction networks,” _Technical report, University of Pennsylvania, Tech. Rep._ , 2015.
  * [36] Z. Lu, Q. Wang, G. Qu, and Z. Liu, “Bars: A blockchain-based anonymous reputation system for trust management in vanets,” in _Proc. 17th IEEE Int. Conference On Trust, Security and Privacy in Computing and Communications_ , 2018, pp. 98–103.
  * [37] U. Javaid, M. N. Aman, and B. Sikdar, “Drivman: Driving trust management and data sharing in vanets with blockchain and smart contracts,” in _2019 IEEE 89th Vehicular Technology Conference (VTC2019-Spring)_ , 2019, pp. 1–5.
  * [38] P. K. Singh, R. Singh, S. K. Nandi, K. Z. Ghafoor, D. B. Rawat, and S. Nandi, “Blockchain-based adaptive trust management in internet of vehicles using smart contract,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 22, no. 6, pp. 3616–3630, 2020.
  * [39] S. Olariu, “A survey of vehicular cloud computing: Trends, applications, and challenges,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 6, pp. 2648–2663, June 2020.
  * [40] ——, “Vehicular crowdsourcing for congestion support in smart cities,” _Smart Cities_ , vol. 4, pp. 662–685, 2021.
  * [41] J. Arshad, M. A. Azad, A. Prince, J. Ali, and T. G. Papaioannou, “REPUTABLE–a decentralized reputation system for blockchain-based ecosystems,” _IEEE Access_ , vol. 10, pp. 79 948–79 961, 2022.
  * [42] P. Resnick, R. Zeckhauser, E. Friedman, and K. Kuwabara, “Reputation systems,” _Communications of the ACM_ , no. 12, pp. 45–48, 2000.
  * [43] R. Jurca and B. Faltings, “An incentive-compatible reputatiion mechanism for the online hotel booking industry,” in _Proc. IEEE Conference on e-commerce_ , Newport Beach, CA, 2003, pp. 285–292.
  * [44] ——, “Confess, an incentive-compatible reputatiion mechanism for the online hotel booking industry,” in _Proc. IEEE Conference on e-commerce_ , San Diego, CA, 2004.
  * [45] ——, “Enforcing truthful strategies in incentive-compatible reputation mechanisms,” _Internet and Network Economics_ , pp. 268–277, 2005.
  * [46] H. Zhao, X. Yang, and X. Li, “WIM: A wage-based incentive mechanism for reinforcing truthful feedbacks in reputation systems,” in _Proc. IEEE Globecom_ , San Diego, CA, 2010.
  * [47] R. Dennis and G. Owen, “Rep on the block: A next generation reputation system based on the blockchain,” in _2015 10th International Conference for Internet Technology and Secured Transactions (ICITST)_ , 2015, pp. 131–138.
  * [48] Z. Zhou, M. Wang, C.-N. Yang, Z. Fu, X. Sun, and Q. J. Wu, “Blockchain-based decentralized reputation system in e-commerce environment,” _Future Generation Computer Systems_ , vol. 124, pp. 155–167, 2021.
  * [49] R. Kerr and R. Cohen, “Smart cheaters do prosper: defeating trust and repuation systems,” in _Proceedings of 8-th International Conference on Autonomous Agents and Multiagent Systems_ , Budapest, Hungary, May 10-15, 2009.
  * [50] A. Cheng and E. Friedman, “Sybilproof reputation mechanisms,” in _SIGGCOM Workshops_ , 2005, pp. 128–132.
  * [51] B. Nasrulin, G. Ishmaev, and J. Pouwelse, “MeritRank: Sybil tolerant reputation for merit-based tokenomics,” in _Proc. 4-th IEEE Conference on Blockchain Research and Applications for Innovative Networks and Services (BRAINS’22)_ , 2022, pp. 95–102.
  * [52] A. Stannat, C. U. Ileri, D. Gijswijt, and J. Pouwelse, “Achieving sybil-proofness in distributed work systems,” in _Proc. 20-th International Conference on Autonomous Agents and Multiagent Systems, (AAMAS’21)_ , 2021, pp. 1261–1271.
  * [53] R. L. Graham, D. E. Knuth, and O. Patashnik, _Concrete Mathematics_ , 2nd ed. Addison-Wesley, 1994.

Professor Olariu received his M.Sc and PhD from McGill University, Montreal,
Canada. Much of his experience has been with the design and implementation of
robust protocols for wireless networks and their applications. Professor
Olariu is applying mathematical modeling and analytical frameworks to the
resolution of problems ranging from securing communications to predicting the
behavior of complex systems to evaluating the performance of wireless
networks. His most recent research interests are in the area of services
computing.

Dr. Ravi Mukkamala received his Ph.D. from the University of Iowa, Iowa City,
Iowa, in 1987. He also received his M.B.A. from Old Dominion University in
1993. He joined ODU as an Assistant professor in 1987 where he is currently a
Professor of Computer Science and Associate Dean for the College of Sciences.
Dr. Mukkamala’s current areas of research include computer security, privacy,
data mining, and modeling. He has published more than 175 research papers in
refereed journals and conference proceedings. He has received more than $3
million in research grants as PI or co-PI from agencies including NASA, as
well as Jefferson Lab and private industries. He received a Most Inspirational
Faculty Award from ODU in 1994. He has won several best paper awards at
national and international conferences over the years.

Meshari Aljohani received the M.S. degree in computer science from California
Lutheran University in 2013. He is currently pursuing the Ph.D. degree in
computer science at Old Dominion University. His research interests are
related to blockchain, marketplace, and reputation systems.

##  Appendix A Appendices

###  A-A Combinatorial preliminaries

###### Lemma A.1

For non-negative integers, $r,\ s,\ t$, the following holds

${r\choose s}{{r-s}\choose t}={{s+t}\choose s}{r\choose{s+t}}.$

###### Proof:

See [53], pp. 167–8. ∎

###### Lemma A.2

For all non-negative integers $k,\ r,\ s,\ m,\ n$, with $0\leq r\leq n$, the
following equality holds

$\sum_{k=0}^{s}{{r+k}\choose n}{{s-k}\choose m}={{r+s+1}\choose{n+m+1}}.$ (21)

###### Proof:

See [53], p. 169. ∎

###  A-B Evaluating $\sum_{j=0}^{N}\Pr[A^{\prime}|H_{j}]\Pr[H_{j}]$

To simplify notation, we write $\Pr[H_{i}]$ instead of $\Pr[H_{i}|n,k]$.
Obviously, Recall that by (3),
$\Pr[H_{i}]=\frac{{i\choose{k}}{{N-i}\choose{n-k}}}{{{N+1}\choose{n+1}}}$ and
that
$\Pr[A^{\prime}|H_{i}]=\frac{{{i-k}\choose{k^{\prime}}}{{N-i-(n-k)}\choose{n^{\prime}-k^{\prime}}}}{{{N-n}\choose
n^{\prime}}}$. With this, the expression of
$\sum_{j=0}^{N}\Pr[A^{\prime}|H_{j}]\Pr[H_{j}]$ becomes:

$\displaystyle\sum_{j=0}^{N}\Pr[A^{\prime}|H_{j}]\Pr[H_{j}]$ $\displaystyle=$
$\displaystyle\frac{\sum_{i=0}^{N}{{i\choose
k}}{{N-i}\choose{n-k}}{{i-k}\choose{k^{\prime}}}{{{N-i-(n-k}}\choose{n^{\prime}-k^{\prime}}}}{{{N-n}\choose{n^{\prime}}}{{N+1}\choose{n+1}}}$
(22)

By Lemma A.1 in the Appendix A-A we can write

${i\choose k}{{i-k}\choose{k^{\prime}}}={{k+k^{\prime}}\choose
k}{i\choose{k+k^{\prime}}}$ (23)

and

$\scriptstyle{{N-i}\choose{n-k}}{{N-i-(n-k)}\choose{n^{\prime}-k^{\prime}}}={{n-k+n^{\prime}-k^{\prime}}\choose{n-k}}{{N-i}\choose{n-k+n^{\prime}-k^{\prime}}}.$
(24)

On replacing (23) and (24) back into (22) we obtain

$\displaystyle\sum_{j=0}^{N}\Pr[A^{\prime}|H_{j}]\Pr[H_{j}]$ $\displaystyle=$
$\displaystyle\frac{{{k+k^{\prime}}\choose
k}{{n-k+n^{\prime}-k^{\prime}}\choose{n-k}}}{{{N-n}\choose{n^{\prime}}}{{N+1}\choose{n+1}}}\scriptstyle\sum_{i=0}^{N}{i\choose{k+k^{\prime}}}{{N-i}\choose{n-k+n^{\prime}-k^{\prime}}}$
(25) $\displaystyle=$ $\displaystyle\frac{{{k+k^{\prime}}\choose
k}{{n-k+n^{\prime}-k^{\prime}}\choose{n-k}}{{N+1}\choose{n+n^{\prime}+1}}}{{{N-n}\choose{n^{\prime}}}{{N+1}\choose{n+1}}}$
$\displaystyle=$ $\displaystyle\frac{{{k+k^{\prime}}\choose
k}{{n-k+n^{\prime}-k^{\prime}}\choose{n-k}}}{{{n+n^{\prime}+1}\choose{n+1}}}.$

###  A-C Two simple algebraic inequalities

###### Lemma A.3

Let $r$ be an arbitrary positive integer and consider non-negative real
numbers $a_{0},a_{1},\cdots,a_{r}$ and
$\alpha_{1},\alpha_{2},\cdots,\alpha_{r}$ as well as positive reals
$b_{0},b_{1},\cdots,b_{r}$ such that

$\frac{a_{i}}{b_{i}}\leq\frac{a_{0}}{b_{0}},\ {\rm for\ all}\ i=1,\ 2,\
\cdots,\ r.$ (26)

Then,

$\frac{\sum_{i=1}^{r}\alpha_{i}~{}a_{i}}{\sum_{i=1}^{r}\alpha_{i}~{}b_{i}}\leq\frac{a_{0}}{b_{0}}.$
(27)

###### Proof:

Let us evaluate the difference

$\displaystyle\frac{a_{0}}{b_{0}}-\frac{\sum_{i=1}^{r}\alpha_{i}~{}a_{i}}{\sum_{i=1}^{r}\alpha_{i}~{}b_{i}}$
$\displaystyle=$
$\displaystyle\frac{a_{0}\sum_{i=1}^{r}\alpha_{i}~{}b_{i}-b_{0}\sum_{i=1}^{r}\alpha_{i}~{}a_{i}}{b_{0}\sum_{i=1}^{r}\alpha_{i}~{}b_{i}}$
(28) $\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{r}\alpha_{i}~{}\left[a_{0}~{}b_{i}-b_{0}~{}a_{i}\right]}{b_{0}\sum_{i=1}^{r}\alpha_{i}~{}b_{i}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{r}\alpha_{i}~{}b_{0}~{}b_{i}\left[\frac{a_{0}}{b_{0}}-\frac{a_{i}}{b_{i}}\right]}{b_{0}\sum_{i=1}^{r}\alpha_{i}~{}b_{i}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{i=1}^{r}\alpha_{i}~{}b_{i}\left[\frac{a_{0}}{b_{0}}-\frac{a_{i}}{b_{i}}\right]}{\sum_{i=1}^{r}\alpha_{i}~{}b_{i}}$
$\displaystyle\geq$ $\displaystyle 0\ \ \ \ \ \mbox{[by (\ref{eq:a0b0}).]}$

∎

###### Lemma A.4

Let $a,\ a^{\prime}$ be non-negative reals and let $b,\ b^{\prime}$ be
positive reals. Then

$\frac{a+a^{\prime}}{b+b^{\prime}}\geq\frac{a}{b}\iff\frac{a^{\prime}}{b^{\prime}}\geq\frac{a}{b}.$
(29)

###### Proof:

We write in stages

$\displaystyle\frac{a+a^{\prime}}{b+b^{\prime}}\geq\frac{a}{b}$
$\displaystyle\iff$
$\displaystyle\frac{a+a^{\prime}}{a}\geq\frac{b+b^{\prime}}{b}$
$\displaystyle\iff$
$\displaystyle\frac{a^{\prime}}{a}\geq\frac{b^{\prime}}{b}$
$\displaystyle\iff$
$\displaystyle\frac{a^{\prime}}{b^{\prime}}\geq\frac{a}{b},$

and the proof of the lemma is complete. ∎