The influence limiter: Provably manipulation-resistant recommender systems
This appendix should be read in conjunction with the article by Resnick and Sami [1]. Here, we include the proofs that were omitted from the main article due to shortage of space. A.1 Lemma 5 Lemma 5: For the quadratic scoring rule (MSE) loss, for all q,u ∈ [0,1], GF(q||u) ≥ D(q||u) 2. Proof of Lemm...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Text |
| Language: | English |
| Published: |
2007
|
| Subjects: | |
| Online Access: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.166 http://deepblue.lib.umich.edu/bitstream/2027.42/55415/1/recsys-appendix.pdf |
| Summary: | This appendix should be read in conjunction with the article by Resnick and Sami [1]. Here, we include the proofs that were omitted from the main article due to shortage of space. A.1 Lemma 5 Lemma 5: For the quadratic scoring rule (MSE) loss, for all q,u ∈ [0,1], GF(q||u) ≥ D(q||u) 2. Proof of Lemma 5: Because both D(q||u) = D(1 − q||1 − u) and GF(q||u) = GF(1 − q||1 − u), we can assume u ≥ q without loss of generality. Keeping q fixed, we want to show that the result holds for all u. Note that D(q||q) = GF(q||q) = 0. Thus, differentiating with respect to u, it is sufficient to prove that GF ′ (q||u) ≥ D ′ (q||u)/2 for all u ≥ q,u ≤ 1. We change variables by setting y = u − q. We use the notation D ′ (y) to denote D ′ (q||u)|u=q+y, treating q as fixed and implicit. Likewise, we use the notation GF ′ (y). For brevity, we use q to denote (1 − q). D(q||u) = q[(q − y) 2 − q 2]+q[(q+y) 2 − q 2] = q[y 2 − 2yq]+q[y 2 + 2qy] = y 2 ⇒ D ′ (y) = 2y 1 GF(q||u) = qlog(1+y 2 − 2qy)+qlog(1+y 2 + 2qy) |
|---|