Theorem 5.1, p. 14 — the liquid price of anarchy of Kelly is exactly 2
ProvedLiquidPoA.Kelly.theorem_5_1budgetskelly-mechanismliquid-welfarep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchyresource-allocation
For every number of players, the liquid price of anarchy of the Kelly proportional allocation mechanism is exactly two:
The supremum ranges over every admissible budgeted resource allocation game and every pure Nash equilibrium, including signal vectors outside . It is the paper's tight efficiency statement for Kelly.
Formalization Note Kelly charges each player's submitted signal at every profile, as specified on p. 9. Liquid welfare, budgets, and suprema are extended nonnegative reals. The paper's one-player case has a different value, so is explicit.
Preamble
import Mathlib import Definitions.Def_LiquidPoA_Kelly_Setting
Formal statement
namespace LiquidPoA.Kelly
/-- Theorem 5.1, p. 14: the full liquid price of anarchy of Kelly is exactly two. -/
theorem theorem_5_1 (n : ℕ) (hn : 2 ≤ n) :
lpoa (kelly n) = 2 := by sorry
end LiquidPoA.Kelly
Source
Caragiannis, Voudouris, The efficiency of resource allocation mechanisms for budget-constrained users, arXiv:1707.03551v3, p. 14, Theorem 5.1; proof p. 15
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.