Theorem 15 proof, p. 27 — Mechanism 5 never exhausts the budget
ProvedBudgetClock.PostedSym.payment_boundLet bidders have costs , where is the budget, and let be any bidder. Run Mechanism 5 with set-aside bidder . Write for the set of bidders that accept during the scan of and for the price offered to bidder ; write for the final winning set. Then
The first inequality is the paper's statement that "at any time of the execution of the mechanism, we would not exhaust the budget"; the second is budget feasibility of the mechanism's output, which includes the payment to when nobody else accepted.
Formalization Note. The proof on p. 27 bounds the payment by ; the last inequality fails for (at the middle term is ). Only bidders are scanned, so at most prices are paid and the total is at most , which is below for every . The theorem states the claim, not the printed chain. The hypothesis makes ; is the paper's standing assumption for Mechanism 5 (p. 27).
import Mathlib import Definitions.Def_BudgetClock_PostedSym_Setting
namespace BudgetClock.PostedSym
theorem payment_bound (n : ℕ) (hn : 2 ≤ n) (B : ℝ) (hB : 0 < B)
(c : Fin n → ℝ) (hc0 : ∀ i, 0 ≤ c i) (hcB : ∀ i, c i ≤ B) (j : Fin n) :
(∑ i ∈ (scan n B c j).winners, (scan n B c j).price i < B) ∧
(∑ i ∈ (mech5 n B c j).1, (mech5 n B c j).2 i ≤ B) := by sorry
end BudgetClock.PostedSym
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.