bit_persuasion_bounded_support_ratio_le_three_halves
For every natural number m, every finite type ι with [DecidableEq ι], and every prior μ on ι → Bool that is a bit prior supported on at most 2m states (cardinality of {x | μ x ≠ 0} is at most 2m), persuasion_max_receiver_utility μ ≤ (3 / 2) * persuasion_prior_utility μ.
Statement
open Finset in theorem bit_persuasion_bounded_support_ratio_le_three_halves (m : ℕ) (ι : Type*) [Fintype ι] [DecidableEq ι] (μ : (ι → Bool) → ℝ) (hμ : is_bit_prior μ) (hsupp : (univ.filter (fun x => μ x ≠ 0)).card ≤ 2 * m) : persuasion_max_receiver_utility μ ≤ 3 / 2 * persuasion_prior_utility μ
- Source
- arXiv:2606.22226
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_bit_priorA probability distribution on {0,1}^ι.
- persuasion_max_receiver_utilityR_max(μ): the largest receiver utility among sender-optimal obedient schemes.
- persuasion_prior_utilityThe receiver's prior-only utility R_0(μ) = ∑_i max(p_i, 1 - p_i).
- persuasion_max_receiver_utility_learXiv:2606.22226, Theorem 4.5 (ratio form). For every prior, R_max(μ) ≤ (3/2) R_0(μ).
Read back from the Lean
For every natural number m, every finite type ι with decidable equality, and every function μ : (ι → Bool) → ℝ, if:
1. μ is a bit prior (all values are non-negative and sum to 1), and
2. the support of μ (the number of states x : ι → Bool with μ x ≠ 0) has cardinality at most 2 * m,
then the maximum receiver utility under any sender-optimal scheme for μ (persuasion_max_receiver_utility μ) is at most 3 / 2 times the receiver's prior utility (persuasion_prior_utility μ).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The result follows directly from the general theorem `persuasion_max_receiver_utility_le`, which establishes that the maximum receiver utility is at most 3/2 times the prior utility for any bit prior. Although the theorem statement includes an assumption that the prior is supported on at most 2m states, this hypothesis is not needed, and applying the general theorem together with the bit-prior hypothesis immediately closes the goal.
persuasion_max_receiver_utility μ ≤ (3 / 2) * persuasion_prior_utility μ
The claim is established by applying the general theorem `persuasion_max_receiver_utility_le`. This reduces the goal to proving that μ is a bit prior, which holds immediately by the hypothesis `hμ`. The support-size bound `hsupp` is not needed.
uses
persuasion_max_receiver_utility_lepersuasion_max_receiver_utility μ ≤ 3 / 2 * persuasion_prior_utility μ := by first | exact persuasion_max_receiver_utility_le | (apply persuasion_max_receiver_utility_le <;> assumption) | (apply persuasion_max_receiver_utility_le <;> simp_all) | simpa using persuasion_max_receiver_utility_le | (simp only [persuasion_prior_utility, is_bit_prior, persuasion_max_receiver_utility] at *; first | exact persuasion_max_receiver_utility_le | (apply persuasion_max_receiver_utility_le <;> assumption) | (apply persuasion_max_receiver_utility_le <;> simp_all) | simpa using persuasion_max_receiver_utility_le)
persuasion_max_receiver_utility_le- For any bit prior μ on a finite type ι, the maximum receiver utility under persuasion is at most 3/2 times the prior utility.
- The hypothesis `hsupp` bounding the support of the prior to at most 2m states is unused, because the 3/2 upper bound holds unconditionally for all bit priors.
- The proof uses a `first | ...` tactic combinator trying multiple resolution strategies; the goal is closed by the branch `apply persuasion_max_receiver_utility_le <;> assumption`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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/-- For any prior supported on at most 2m states, R_max(μ) is at most (3/2) R_0(μ). -/theorem bit_persuasion_bounded_support_ratio_le_three_halves (m : ℕ) (ι : Type*) [Fintype ι] [DecidableEq ι] (μ : (ι → Bool) → ℝ) (hμ : is_bit_prior μ) (hsupp : (univ.filter (fun x => μ x ≠ 0)).card ≤ 2 * m) : persuasion_max_receiver_utility μ ≤ 3 / 2 * persuasion_prior_utility μ := by first | exact persuasion_max_receiver_utility_le | (apply persuasion_max_receiver_utility_le <;> assumption) | (apply persuasion_max_receiver_utility_le <;> simp_all) | simpa using persuasion_max_receiver_utility_le | (simp only [persuasion_prior_utility, is_bit_prior, persuasion_max_receiver_utility] at *; first | exact persuasion_max_receiver_utility_le | (apply persuasion_max_receiver_utility_le <;> assumption) | (apply persuasion_max_receiver_utility_le <;> simp_all) | simpa using persuasion_max_receiver_utility_le)