Proof of Theorem 5.3, p. 560 — optimal welfare is monotone under valuation dominance
ProvedBalancedPrices.ClosureMax.optVal_monobalanced-pricesoptimal-welfarep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-inequality
Let every valuation in the base spaces take values in . Let and with for every agent and outcome . Then for every set of outcome profiles
In the proof of Theorem 5.3 this is the comparison , used in both chains.
Formalization Note The optimal value is the real supremum of welfare over , so the paper's two steps (evaluate at 's maximiser, then compare with 's optimum) merge into one supremum comparison and no attainment is assumed. The bound of §2 keeps both suprema bounded; both sides are when is empty. Agents are indexed from zero.
Preamble
import Mathlib import Definitions.Def_BalancedPrices_ClosureMax_Composition
Formal statement
namespace BalancedPrices.ClosureMax
/-- The supremum comparison used in the proof of Theorem 5.3, including the empty set. -/
theorem optVal_mono {n : ℕ} {X : Fin n → Type*}
(Vsp : ∀ i, Set (X i → ℝ))
(hV : ∀ i (f : X i → ℝ), f ∈ Vsp i → ∀ xi, 0 ≤ f xi ∧ f xi ≤ 1)
(vt vf : BalancedPrices.Extension.Valuation X) (hvt : ∀ i, vt i ∈ Vsp i)
(hvf : ∀ i, vf i ∈ VmaxSet Vsp i)
(hle : ∀ i xi, vt i xi ≤ vf i xi)
(S : Set (BalancedPrices.Extension.Outcome X)) : BalancedPrices.Extension.optVal vt S ≤ BalancedPrices.Extension.optVal vf S := by sorry
end BalancedPrices.ClosureMax
Source
Dütting, Feldman, Kesselheim, Lucier, Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs, SIAM J. Comput. 49 (2020), p. 560, proof of Theorem 5.3, property (b), last two inequalities
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.