Information Technology Reference
In-Depth Information
for B's report is
(
p
(
g
g
)) = (
0
.
8
.
0
.
2
)
, and just like in the weather prediction
example it's expected reward for the scoring rule:
pay
(
o
t
,
q
)=
1
+
2
q
t
−
|
g
)
,
p
(
b
|
j
=
1
q
j
k
is 1
.
68, provided that A's probability distribution for B's experience is indeed
(
0
.
8
.
0
.
2
)
.
If A did not experience good service, it would expect B's observation to follow a
different probability distribution, in this case
(
0
.
4
,
0
.
6
)
. If it nevertheless reports good
service, the expected reward is only 0
.
4
0
.
72
=
1
.
2. On the other hand,
when A truthfully reports bad service, the mechanism treats this as a prediction of
the probability distribution
(
0
.
4
,
0
.
6
)
for B's experience. The payments for truthfully
reporting bad service are calculated using the probabilities
(
0
.
4
,
0
.
6
)
and would lead to
a higher expected reward for truthful reporting of 0
.
4
·
1
.
92
+
0
.
6
·
·
(
1
+
2
·
0
.
4
−
0
.
52
)+
0
.
6
·
(
1
+
2
·
0
.
6
0
.
52
)=
1
.
52.
Note that, contrary to the weather prediction, we are not asking A to report this
probability distribution, but only whether it received good or bad service. Thus, the
designer of the reward scheme needs to know how an observation influences A's beliefs
about the observations of another agent B with reasonable precision in order to compute
the payments. It can in part be deduced from the general expectations of the quality of
service, but also involves an assumption of how the individual agents would update their
beliefs in response to a positive or negative experience.
Furthermore, the original peer prediction method suffers from the weakness that
truthful reporting is not the only equilibrium strategy: any strategy where agents all
report the same is also a Nash equilibrium. In fact, since actual observations or predic-
tions are likely to be noisy, the highest-paying equilibrium is always one where agents
always report the same, independently of their true knowledge!
This problem can be overcome by constructing scoring rules that refer not to one,
but several reference reports. [6,7] show that when at least 3 reference reports are used,
truthful reporting can be made the highest-paying Nash equilibrium. Furthermore, they
show that truthful reporting can be made the
only
Nash equilibrium and thus completely
eliminate the problem of collusive reporting strategies.
It has recently been shown that peer prediction methods can be generalized to sce-
narios where agents report not on identical events, but events that are merely corre-
lated ([8]). This makes it applicable for example to measurements in sensor networks,
where different sensors measure quantities that are correlated by not equal.
−
4
Opinion Polls
A major weakness of the peer prediction method is that it requires all participating
agents to share the same probability distribution of the reported events. If this is not the
case, proper scoring rules can still be designed, but the rewards that must be paid to
agents quickly become very large ([9]).
To counter this effect, it is possible to design peer prediction schemes as opinion
polls that publish the current results of the poll. Agents whose probability distribution
