Proof of Theorem 2, "Quasiconcavity of utility in the buyer's own strategy", p. 12 — spend increasing; utility increasing below budget, decreasing above when H > M/ϵ
ProvedMultPacing.Existence.theorem_2_quasiconcavityFix a pacing game, , , a buyer and the multipliers of the other buyers. For write for buyer 's total spend and for her utility in the -smoothed pacing game when she plays . Then:
- is continuous and strictly increasing on ;
- is strictly increasing on ;
- if satisfies for every buyer and , then is strictly decreasing on .
Since is increasing, the two sets are and for the point where the spend reaches (or if it never does), so increases up to and decreases after it:
In particular is quasiconcave in the buyer's own strategy, which is the second hypothesis of the existence theorem behind Theorem 2; part 2 is also used in the proof of Theorem 1.
Formalization Note The other buyers' multipliers enter through a profile with all entries in , and buyer 's entry is replaced by (Function.update α i a).
Differences from the source:
- generalization: the bullet is argued under Theorem 2's hypotheses (, and Definition 3's ) → parts 1 and 2 for every real , part 3 under and ; reason: below the budget the utility does not involve , and the spend never does, so the bound on is needed only for part 3; with the hypotheses in place the statement is the source's.
- reading: " is increasing", "total spend … is increasing", "utility is decreasing" → strictly increasing / strictly decreasing; reason: the paper itself recalls the claim as "strictly increasing … (the strictness is due to the artificial good)" in the proof of Theorem 1, and the strict reading is the stronger one.
- encoding: "there exists a number such that for , is nondecreasing … for nonincreasing", with the solution of or → monotonicity on the sets and ; reason: since is continuous and strictly increasing (part 1) these sets are exactly and (the second empty when is not attained).
import Mathlib import Definitions.Def_MultPacing_Existence_Smoothed
namespace MultPacing.Existence
theorem theorem_2_quasiconcavity {N G : Type*} [Fintype N] [DecidableEq N] [Fintype G]
(P : PacingGame N G) (ε H M : ℝ) (hε : 0 < ε) (α : N → ℝ)
(hα : ∀ k, α k ∈ Set.Icc (0 : ℝ) 1) (i : N) :
(ContinuousOn (fun a => smSpend P ε (Function.update α i a) i) (Set.Icc 0 1) ∧
StrictMonoOn (fun a => smSpend P ε (Function.update α i a) i) (Set.Icc 0 1)) ∧
StrictMonoOn (fun a => smUtility P ε H (Function.update α i a) i)
{a | a ∈ Set.Icc (0 : ℝ) 1 ∧ smSpend P ε (Function.update α i a) i ≤ P.B i} ∧
((∀ k, ∑ j, P.v k j + 2 * ε ≤ M) → M / ε < H →
StrictAntiOn (fun a => smUtility P ε H (Function.update α i a) i)
{a | a ∈ Set.Icc (0 : ℝ) 1 ∧ P.B i ≤ smSpend P ε (Function.update α i a) i}) := by sorry
end MultPacing.Existence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.