Proof of Theorem 5.1, p. 15 — the supremum is 2
ProvedLiquidPoA.Kelly.kelly_sup_ratiobudgetskelly-mechanismliquid-welfarep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchyresource-allocation
For at least two Kelly players, the supremum of the ratio in equation (6) over signal vectors with at least two positive coordinates is
The value is a supremum: for two players it is approached as the first signal tends to zero while remaining positive. It supplies the numerical bound for Theorem 5.1.
Preamble
import Mathlib import Definitions.Def_LiquidPoA_Kelly_Setting
Formal statement
namespace LiquidPoA.Kelly
/-- The final supremum in the display on p. 15 is exactly two. -/
theorem kelly_sup_ratio (n : ℕ) (hn : 2 ≤ n) :
(⨆ (s : Fin n → ℝ) (_ : InX s),
ratio (kelly n) s (⟨0, by omega⟩ : Fin n)) = 2 := by sorry
end LiquidPoA.Kelly
Source
Caragiannis, Voudouris, The efficiency of resource allocation mechanisms for budget-constrained users, arXiv:1707.03551v3, p. 15, proof of Theorem 5.1, last line of displayed calculation
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.