Figure 6: Screenshot of review screen from shoutve- locity.com.
If a mechanism does not rate an item till it loses at least once, then this item cannote be distinguished from better items. Therefore, it is impossible to estimate the ranks r
within r(1 ± ). Let gc(x) denote 1
gc(x), and let f(x) = 1
normally distributed qualities gc(x) = erfc(x). Let us es- timate the score of the item with rank r; at that point
the cdf must have value 1 centrated around gc 1(r/n).
r n . So the quality vr is con- For large n we may simply
1(r/n). Let s = r/n; then we can think of w r i t e v r = g c v s = g 1 c ( s ) a s a f u n c t i o n o f s . Let x = vs. Number of thumb ratings required for an item
with score x till it loses at least once is
1 f (x)
, as in each rating
it loses with probability f(x). Now gc(x) = s. For large x, g(x) = erfc(x) can be approximated as g0(x)/x. Now
1 (log n)
So total number of thumbs required is at least: Pr∈1..n 1 (log n) 1 (r/n) 2 2 . So the average number of thumbs per item is: /2
1 (log n)
X r r∈1..n n
1 (log n)
Z 1 s =
1, clearly this quantity diverges to ∞. More gener-
ally we get
Z 1 0
Z 1 0
Z 1 0
1 f (gc
Proof of Theorem 5.2:
Let p = f(x) denote the prob-
ability of winning in one comparison; the variance
indicator variable for one comparison is p(1
By central limit theorem (or by similar concentration in- equalities such as Hoeffding bounds), for a large number of comparisons k, the fraction of wins is expected to be around
p with variance p(1k p) . The probability that the estimate
for p has additive error more than is e confidence δ this gives:
k = Θ(
However, we need to estimate x within error x ± x, which means we need to estimate p = f(x) within error |f(x ±
f(x)| ≈ |f0(x)|.
Replacing by f0(x) gives us the
20 2 f (x)
Observe that for f(x) equal to the erf or the logistic func-
tion the quantity
02 f (x)
is decreasing in x. This means
that the number of comparisons required is fewer when com- pared to an item with similar quality.
Proof of Theorem 5.3: We show that successively com- paring the given item with geometrically decreasing per- centile ranks 1/2, ρ/2, ρ2/2..., 1/n achieves the result. We compare the item to these items successively till we find two consecutive ranks between which the item lies. Choos- ing ρ = 1/(1 + ) ensures that the algorithm approximates the rank within a factor of 1 + . Next we bound the total
number of comparisons required. An item with percentile rank s =
gets compared with
items with percentile ranks s(1 + ), s(1 + )2, s(1 + )3..1/2. Thus it gets compared with log(1/s)/ log(1 + ) items.
To get a good estimate the number of comparisons re- quired is minimized when it is compared to an item with closest quality which is s(1 + ).
To estimate the rank within error r, we need to es-
timate its quality vr
| v s ± s 1 / g 0 c ( g c
vs| ≈ v0(s)s. Let x = vs. Then v0(s) = (gc
1 ( s ) ) = 1 / g 0 c ( x ) .
Thus error in quality estimate is
is also the difference in the qual-
ities of the two items, number of comparisons required is
s / g 0 c ( x ) Since = s/(xgc(x)) is small f( ), 1 /x = f( ) and Now = Θ ( / p l o g ( 1 / s ) ) . = f 0 ( ) a r e c o n s t a n t , s o n u m b e r o f c o m p a r i s o n s i s O ( 1 / 2 ) = O(log(1/s)). This is multiplied by at most log(1/s)/ log(1 +
log2(n/x)/ log(1 + ) = O(n/ log(1 + )).
Thus, the average number of comparisons required is O(1/ log(1 + )) which is a constant.
EXPERIMENT L RESULTS
Simulations over Synthetic Data
We perform experiments to compare the ranking schemes of the thumbs algorithm and the comparison based shoutve- locity algorithm. Experiments are done by considering n players (set to 1000) and choosing their true scores based on g(x) being the normal distribution with variance 1. We