Appendix A.1, pp. 20–21 — the three constraints on v(W₁ ∪ W₂)/OP̃T_t̂ are incompatible for ρ ≥ 4.75
ProvedBudgetClock.Monotone.incompatibility_A1approximationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1real-inequality
Let be an integer and real numbers with
Then there is no real number with
In the proof of Theorem 1, , , , , and the three inequalities are what follows from assuming that both and are below a fraction of the benchmark. Their incompatibility yields the factor .
Formalization Note The bound on uses Lemma 2's constant ; the appendix quotes once but substitutes in the computation that follows. All three inequalities are strict, as printed; at , , and the extreme the lower and upper bounds coincide.
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_BudgetClock_Monotone_Mechanism
Formal statement
namespace BudgetClock.Monotone
/-- Appendix A.1, pp. 20–21: for `t ≥ 3`, `ρ ≥ 4.75`, `α ≥ 2^{t−2}/(2^{t−1}+2)`,
`β ≤ 3/2 − 1/2^{t−2}` and `0 ≤ u ≤ 1`, no real `x` (the ratio `v(W_1 ∪ W_2)/OP̃T_t̂`) satisfies the three
constraints `x > ρα − β`, `x > ρ(1 − u) − β`, `x < (2ρα + 2β − ρu + ρ/2^{t−2})/(2ρ − 2)`. -/
theorem incompatibility_A1 (t : ℕ) (ht : 3 ≤ t) (ρ α β u x : ℝ) (hρ : 19 / 4 ≤ ρ)
(hα : (2 : ℝ) ^ (t - 2) / ((2 : ℝ) ^ (t - 1) + 2) ≤ α)
(hβ : β ≤ 3 / 2 - 1 / (2 : ℝ) ^ (t - 2)) (hu0 : 0 ≤ u) (hu1 : u ≤ 1) :
¬ (ρ * α - β < x ∧ ρ * (1 - u) - β < x ∧
x < (2 * ρ * α + 2 * β - ρ * u + ρ / (2 : ℝ) ^ (t - 2)) / (2 * ρ - 2)) := by sorry
end BudgetClock.Monotone
Source
Balkanski et al., Deterministic Budget-Feasible Clock Auctions, arXiv:2107.09239v2, pp. 20–21, Appendix A.1, proof of Theorem 1 (the three constraints and their incompatibility)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.