Lemma 4.3, p. 14 — class C makes each signal an equilibrium
ProvedLiquidPoA.Kelly.lemma_4_3budgetskelly-mechanismliquid-welfarep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchyresource-allocation
For any -player resource allocation mechanism in the class and any , the same signal vector is a pure Nash equilibrium of its affine game:
This is the equality condition used in Lemma 4.2. The class asks for concavity of each player's own-signal allocation and convexity of her own-signal payment.
Formalization Note The valuations and budgets of are constructed from and ; affordability is part of equilibrium.
Preamble
import Mathlib import Definitions.Def_LiquidPoA_Kelly_Setting
Formal statement
namespace LiquidPoA.Kelly
/-- Lemma 4.3, p. 14: every vector in `𝕏ₙ` is an equilibrium of its affine game for a class-`𝒞` mechanism. -/
theorem lemma_4_3 {n : ℕ} (hn : 2 ≤ n) (M : Mechanism n)
(hM : IsRAMechanism M) (hC : InClassC M)
(s : Fin n → ℝ) (hs : InX s) :
IsEquilibrium M (worstGame M s (⟨0, by omega⟩ : Fin n)) s := by sorry
end LiquidPoA.Kelly
Source
Caragiannis, Voudouris, The efficiency of resource allocation mechanisms for budget-constrained users, arXiv:1707.03551v3, p. 14, Lemma 4.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.