Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 15 proof, p. 27 — Mechanism 5 never exhausts the budget

Proved
BudgetClock.PostedSym.payment_bound

by mikedeng1 · Oct 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

budget-feasibleharmonic-sump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1posted-price

Let n≥2n \ge 2n≥2 bidders have costs 0≤ci≤B0 \le c_i \le B0≤ci​≤B, where B>0B > 0B>0 is the budget, and let jjj be any bidder. Run Mechanism 5 with set-aside bidder jjj. Write W′W'W′ for the set of bidders that accept during the scan of [n]∖{j}[n]\setminus\{j\}[n]∖{j} and pip_ipi​ for the price offered to bidder iii; write WWW for the final winning set. Then

∑i∈W′pi<Band∑i∈Wpi≤B.\sum_{i \in W'} p_i < B \qquad\text{and}\qquad \sum_{i \in W} p_i \le B .i∈W′∑​pi​<Bandi∈W∑​pi​≤B.

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 BBB to jjj when nobody else accepted.

Formalization Note. The proof on p. 27 bounds the payment by (1+1+12+⋯+1n−1)B2ln⁡n≤ln⁡(n−1)+22ln⁡nB<B(1 + 1 + \tfrac12 + \cdots + \tfrac1{n-1})\tfrac{B}{2\ln n} \le \tfrac{\ln(n-1)+2}{2\ln n}B < B(1+1+21​+⋯+n−11​)2lnnB​≤2lnnln(n−1)+2​B<B; the last inequality fails for 2≤n≤62 \le n \le 62≤n≤6 (at n=2n=2n=2 the middle term is ≈1.44 B\approx 1.44\,B≈1.44B). Only n−1n-1n−1 bidders are scanned, so at most n−1n-1n−1 prices are paid and the total is at most (1+Hn−2)B2ln⁡n(1 + H_{n-2})\tfrac{B}{2\ln n}(1+Hn−2​)2lnnB​, which is below BBB for every n≥2n \ge 2n≥2. The theorem states the claim, not the printed chain. The hypothesis n≥2n \ge 2n≥2 makes ln⁡n>0\ln n > 0lnn>0; ci≤Bc_i \le Bci​≤B is the paper's standing assumption for Mechanism 5 (p. 27).

Preamble
import Mathlib
import Definitions.Def_BudgetClock_PostedSym_Setting
Formal statement
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
Source
Balkanski et al., Deterministic Budget-Feasible Clock Auctions, arXiv:2107.09239v2, p. 27, proof of Theorem 15, first paragraph
Human review
  • Endorsed by Shuze Chen · Oct 14, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 14, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me