Lemma 4.2, p. 13 — the bound in equation (6) and its equality case
ProvedLiquidPoA.Kelly.lemma_4_2Let be an -player resource allocation mechanism, , with allocation and payment functions and , and let
Then the liquid price of anarchy of satisfies
If, in addition, every is an equilibrium of the game , then (6) holds with equality.
The lemma turns upper and lower bounds on the liquid price of anarchy into the analysis of a single explicit expression in the signal vector, with no reference to valuations or budgets.
Formalization Note is the supremum over all admissible games and all their equilibria, as on p. 6. The paper's proof restricts to equilibria in by the claim of pp. 5–6 that no other signal vector is an equilibrium (up to games whose liquid welfare does not depend on the allocation); that claim uses the continuity of the payment at the zero vector, which is property 8 of the mechanism axioms. User 1 is index ; makes it exist.
import Mathlib import Definitions.Def_LiquidPoA_Kelly_Setting
namespace LiquidPoA.Kelly
/-- Lemma 4.2, p. 13: the liquid price of anarchy is bounded by the supremum (6), with equality under the equilibrium condition. -/
theorem lemma_4_2 {n : ℕ} (hn : 2 ≤ n) (M : Mechanism n)
(hM : IsRAMechanism M) :
(lpoa M ≤ ⨆ (s : Fin n → ℝ) (_ : InX s),
ratio M s (⟨0, by omega⟩ : Fin n)) ∧
((∀ s, InX s →
IsEquilibrium M (worstGame M s (⟨0, by omega⟩ : Fin n)) s) →
lpoa M = ⨆ (s : Fin n → ℝ) (_ : InX s),
ratio M s (⟨0, by omega⟩ : Fin n)) := by sorry
end LiquidPoA.Kelly
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.