Lemma 11, p. 51 — for any δ ∈ (0,1), one level ℓ ≥ log₂F sees at most log(2L/δ) + 3 fake users with probability at least 1 − δ/(2L)
ProvedFakeUserRanking.FORC.lemma_11Throughout, products with click probabilities in (condition (1)) and exit probabilities are shown to users, at most of whom are fake, controlled by an adaptive randomized policy that sees only the past history and puts no mass on fake users once rounds were fake. FORC (Algorithm 3) runs levels with ; it does not know , or . Its unspecified choices (tie-breaking in GraphRankSelect, the "arbitrary ranking", and Step 6 when no level qualifies) are arbitrary functions of its past, and the statement holds for all of them.
Lemma 11. For any policy with fakeness budget , any and any fixed level , with probability at least level is exposed to at most fake users:
Here is an arbitrary number in , not FORC's parameter.
Because level is sampled with probability independently of the fake entity's decision in the same round, a level expects at most one fake user; the lemma is the corresponding high-probability bound. Its union bound over levels is Lemma 5.
Formalization Note. Products, positions, levels and rounds are 0-based in Lean (Fin n, Fin L, Fin T): Lean product is paper product , and Lean level is paper level , so the paper's condition is written . The exposure counts rounds whose sampled level is and whose user is fake, even when another level's graph ranks (p. 52). "With probability " is read as "at least".
Differences from the source:
- encoding: products, positions, levels and rounds indexed from 1; paper level ℓ; ℓ ≥ ℓ⋆ = ⌈log₂F⌉ → Fin n, Fin L, Fin T, all 0-based; Lean level k is paper level ℓ = k + 1; ℓ ≥ ⌈log₂F⌉ is written F ≤ 2^(k+1); reason: Lean convention; same instances (F ≤ 2^ℓ is exactly ℓ ≥ ⌈log₂F⌉, and holds for every level when F = 0)
- encoding: expectations and probabilities over the random history H_T → finite sums over trajectories Fin T → Step, weighted by the product of the level weights, the policy's PMF and the real customer's cascade law; reason: every space of the model is finite, so this is the law of the history exactly
- reading: L = log₂(T) levels → L = ⌈log₂T⌉ (Nat.clog 2 T); reason: the number of levels must be an integer; the ceiling keeps 2^L ≥ T (paper.md Slip 1)
- reading: Step 8, no click at the last examined position: r ← r(η − 1)/(η + 1) → r^(ℓ)_i = (clicks of i at level ℓ)/η^(ℓ)_i, the average reward; reason: Step 3 calls r the average reward; FAR's Step 6 has r(η − 1)/η and the proofs use r·η = sum of samples (paper.md Slip 2)
- encoding: Step 9 updates η̂, r̂ incrementally, only for levels ℓ ≥ ℓ_t and examined products → η̂, r̂ in closed form (17)–(18) from the current counts, for every level; reason: η^(g) with g ≤ ℓ changes only in rounds with ℓ_t ≤ ℓ, which trigger the update, so the stored values always equal the closed form
- reading: ties among the smallest η in GraphRankSelect, its 'arbitrary ranking' on a cyclic graph, and Step 6 when no non-eliminated level above ℓ_t exists are left unspecified → universally quantified functions tb (a member of the tied set) and fb of FORC's past and the sampled level; reason: the claim is made for the algorithm as printed, so it must hold for every resolution of its unspecified choices (paper.md Slip 8)
- encoding: n ≥ 1 products and T rounds, unrestricted → 1 ≤ n and 2 ≤ T; reason: δ = 1/(n³T) is undefined at n = 0, and T ≤ 1 gives L = ⌈log₂T⌉ = 0 levels, where FORC draws no level and the statement is vacuous
- reading: with probability 1 − δ/(2L) → probability at least 1 − δ/(2L); reason: a probability bound; the proof (p. 52) gives a lower bound
- reading: any level ℓ ≥ log₂(F) is exposed to at most log(2L/δ) + 3 fake users → for each fixed level k with F ≤ 2^(k+1), the bound holds with that probability; reason: the proof fixes one level ('for a fixed level', p. 51) and Lemma 5 is its union bound (paper.md Slip 12)
import Mathlib import Definitions.Def_FakeUserRanking_FORC_Model import Definitions.Def_FakeUserRanking_FORC_Algorithm import Definitions.Def_FakeUserRanking_FORC_GoodEvent
namespace FakeUserRanking.FORC
/-- Lemma 11, p. 51: one level `ℓ ≥ log₂ F` (Lean: `F ≤ 2^(k+1)`) is exposed to at most
`log(2L/δ) + 3` fake users with probability at least `1 − δ/(2L)`, for any `δ ∈ (0,1)`. -/
theorem lemma_11 (n T F : ℕ) (hn : 1 ≤ n) (hT : 2 ≤ T)
(inst : Instance n) (hμ : StrictAnti inst.μ)
(P : Adversary n) (hP : WithinBudget F P)
(tb : List (Fin (numLevels T) × Obs n) → Fin (numLevels T) → Finset (Fin n) → Fin n)
(htb : ∀ h k S, S.Nonempty → tb h k S ∈ S)
(fb : List (Fin (numLevels T) × Obs n) → Fin (numLevels T) → Equiv.Perm (Fin n))
(δ : ℝ) (hδ0 : 0 < δ) (hδ1 : δ < 1)
(k : Fin (numLevels T)) (hk : F ≤ 2 ^ ((k : ℕ) + 1)) :
1 - δ / (2 * (numLevels T : ℝ)) ≤
prob inst P (forc n T tb fb) T
(fun τ => (exposure k τ : ℝ) ≤ Real.log (2 * (numLevels T : ℝ) / δ) + 3) := by sorry
end FakeUserRanking.FORC
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.