Abstract

It is well known that as information grows about a random variable, the conditional expectation of the random variable given the information evolves as a martingale. Therefore, martingales naturally arise in trust and reputation systems, which involve the evolution of trust or reputation with growing information. This work focuses on a particular decision problem—namely, which links to probe in a network, to assess the overall capability of the network. In essence, the decision maker is trying to establish the trustworthiness of a system by probing links within it. Each link is assumed to have a random binary state, fixed for all time, and when a link is probed the decision maker obtains a noisy observation of the link state. A particular example is probing links within a graph to determine whether the links with state one span the graph. The conditional state of each link is a martingale, and the conditional probability that the overall network state is good is also a martingale. Examples and preliminary analysis are described in this talk.