persuasion_pair_or_scheme_obedient
lemmaverified
The pair-OR scheme of a nonnegative symmetric coupling with first marginal μ is obedient.
Statement
open Finset in lemma persuasion_pair_or_scheme_obedient {ι : Type*} [Fintype ι] [DecidableEq ι] (μ : (ι → Bool) → ℝ) (ν : (ι → Bool) → (ι → Bool) → ℝ) (hν0 : ∀ x y, 0 ≤ ν x y) (hνs : ∀ x y, ν x y = ν y x) (hνμ : ∀ x, ∑ y, ν x y = μ x) : is_obedient_direct_scheme μ (persuasion_pair_or_scheme ν)
- Source
- step towards persuasion_receiver_ratio_optimal_constant (optimal receiver-utility constant 3/2, open in arXiv:2606.22226 v1, Sec. 5)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_obedient_direct_schemeAn obedient direct scheme for the prior μ on {0,1}^ι.
- persuasion_pair_or_schemeThe pair-OR scheme of a symmetric coupling ν: draw (X, Y) ∼ ν and recommend X ∨ Y.
- persuasion_obedience_costObedience cost C_i(x, a): 1/2 - x_i if a_i = 1, x_i - 1/2 if a_i = 0.
- Used by 4
- persuasion_uniform_two_states_ratio_leFor every finite type ι and every prior μ on ι → Bool that is uniform on 2 distinct states, the maximum receiver utility R_max(μ) is at…
- persuasion_max_receiver_utility_learXiv:2606.22226, Theorem 4.5 (ratio form). For every prior, R_max(μ) ≤ (3/2) R_0(μ).
- persuasion_slice_scheme_obedientThe slice scheme (pair the realised state with a uniformly random other state and recommend the coordinatewise OR) is an obedient direct…
- bit_persuasion_even_scheme_obedientFor every natural number m ≥ 1, bit_persuasion_even_scheme m is an obedient direct scheme for bit_persuasion_even_prior m…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finset in/-- The pair-OR scheme of a nonnegative symmetric coupling with first marginal `μ` is obedient. -/lemma persuasion_pair_or_scheme_obedient {ι : Type*} [Fintype ι] [DecidableEq ι] (μ : (ι → Bool) → ℝ) (ν : (ι → Bool) → (ι → Bool) → ℝ) (hν0 : ∀ x y, 0 ≤ ν x y) (hνs : ∀ x y, ν x y = ν y x) (hνμ : ∀ x, ∑ y, ν x y = μ x) : is_obedient_direct_scheme μ (persuasion_pair_or_scheme ν) := by classical refine ⟨fun x a => sum_nonneg fun y _ => ?_, fun x => ?_, fun a i => ?_⟩ · split_ifs · exact hν0 x y · exact le_refl 0 · unfold persuasion_pair_or_scheme rw [sum_comm, ← hνμ x] apply sum_congr rfl; intro y _ rw [sum_ite_eq] simp · unfold persuasion_pair_or_scheme set L := ∑ x, (∑ y, if (fun i => x i || y i) = a then ν x y else 0) * persuasion_obedience_cost i x a have e1 : L = ∑ x, ∑ y, (if (fun i => x i || y i) = a then ν x y else 0) * persuasion_obedience_cost i x a := by simp only [L, sum_mul] have e2 : L = ∑ x, ∑ y, (if (fun i => x i || y i) = a then ν x y else 0) * persuasion_obedience_cost i y a := by rw [e1, sum_comm] apply sum_congr rfl; intro y _ apply sum_congr rfl; intro x _ have hor : (fun i => y i || x i) = (fun i => x i || y i) := by funext j; exact Bool.or_comm _ _ rw [hor, hνs y x] have e3 : 2 * L ≤ 0 := by have : 2 * L = ∑ x, ∑ y, (if (fun i => x i || y i) = a then ν x y else 0) * (persuasion_obedience_cost i x a + persuasion_obedience_cost i y a) := by rw [two_mul] nth_rewrite 1 [e1] rw [e2, ← sum_add_distrib] apply sum_congr rfl; intro x _ rw [← sum_add_distrib] apply sum_congr rfl; intro y _ ring rw [this] apply sum_nonpos; intro x _ apply sum_nonpos; intro y _ split_ifs with h · apply mul_nonpos_of_nonneg_of_nonpos (hν0 x y) have hai : a i = (x i || y i) := by rw [← h] unfold persuasion_obedience_cost cases hx : x i <;> cases hy : y i <;> rw [hx, hy] at hai <;> simp [hai] <;> norm_num · simp linarith