Lemma 4.1, p. 10 — an affine worst-case game bounds LPoA
ProvedLiquidPoA.Kelly.lemma_4_1budgetskelly-mechanismliquid-welfarep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchyresource-allocation
Let be a resource allocation mechanism and an admissible -player game with . Suppose is a pure Nash equilibrium with minimum liquid welfare among the equilibria of . There is a player such that
where gives all of the resource to . The lemma reduces a game's inefficiency to that of an affine game determined by an equilibrium.
Formalization Note The minimum-welfare condition and are explicit. Ratios use extended nonnegative reals.
Preamble
import Mathlib import Definitions.Def_LiquidPoA_Kelly_Setting
Formal statement
namespace LiquidPoA.Kelly
/-- Lemma 4.1, p. 10: a minimum-welfare equilibrium is bounded by an affine worst-case game. -/
theorem lemma_4_1 {n : ℕ} (M : Mechanism n) (hM : IsRAMechanism M)
(G : RAGame n) (hG : G.IsAdmissible)
(hbad : 1 < gameLPoA M G) (s : Fin n → ℝ)
(heq : IsEquilibrium M G s) (hs : InX s)
(hmin : ∀ t, IsEquilibrium M G t → LW G (M.alloc s) ≤ LW G (M.alloc t)) :
∃ i : Fin n,
gameLPoA M G ≤
LW (worstGame M s i) (unitAlloc i) / LW (worstGame M s i) (M.alloc s) ∧
LW (worstGame M s i) (unitAlloc i) / LW (worstGame M s i) (M.alloc s) =
ratio M s i := by sorry
end LiquidPoA.Kelly
Source
Caragiannis, Voudouris, The efficiency of resource allocation mechanisms for budget-constrained users, arXiv:1707.03551v3, p. 10, Lemma 4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.