Lemma 1, p. 20 — regret is at most F plus the gap-weighted expected number of real examinations of misplaced products
ProvedFakeUserRanking.FORC.lemma_1Lemma 1 (Decomposing Regret). Consider the cascade model with click probabilities in (condition (1)) and exit probabilities , a fake-user policy with fakeness budget , and any randomized ranking algorithm that sees only its own past (observations and internal randomness). Then the regret against the optimal ranking satisfies
where is the event that product is at position in round , the customer of round is real, and she does not exit before position ; both runs face the same policy .
The lemma reduces regret to pairwise misplacements: each examination by a real customer of a worse product placed at the position costs at most the gap , and fake users cost at most in total. It is the first step of the proofs of Theorems 2 and 3.
Formalization Note. An algorithm is an Alg n L: in each round it draws an internal label with weights w h · (nonnegative, summing to 1) that may depend on its past h (labels and observations), and displays the ranking rank h ℓ. Every randomized algorithm induces the same law of the history as one of these (take the ranking itself as the label). Products and positions are 0-based; Finset.Ioi j is . Expectations are finite sums over trajectories; is prob.
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
- encoding: an arbitrary randomized algorithm (π_t : H^o_{t−1} → Π) → Alg n L: per round a label drawn with weights depending on the algorithm's own past (nonnegative, summing to 1), and a ranking that is a function of that past and the label; reason: every randomized algorithm has a behavioural representation with the same history law (label = ranking, L = n!), and every Alg is such an algorithm
- encoding: E_{H_t(π_t)}[I(A_{r,t}(π_t(j) = i))] over the t-round history → the probability of the event under the T-round run; reason: the event depends only on the first t rounds and the later rounds' weights sum to 1
import Mathlib import Definitions.Def_FakeUserRanking_FORC_Model
namespace FakeUserRanking.FORC
/-- Lemma 1 (Decomposing Regret), p. 20. -/
theorem lemma_1 {n L : ℕ} (T F : ℕ) (A : Alg n L)
(hw_nonneg : ∀ h k, 0 ≤ A.w h k) (hw_sum : ∀ h, ∑ k, A.w h k = 1)
(inst : Instance n) (hμ : StrictAnti inst.μ)
(P : Adversary n) (hP : WithinBudget F P) :
regret inst P A T ≤ (F : ℝ) + ∑ t : Fin T, ∑ j : Fin n, ∑ i ∈ Finset.Ioi j,
gap inst j i * prob inst P A T (fun τ => feedbackEvent A τ t j i) := by sorry
end FakeUserRanking.FORC
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.