Price of stability, restricted play, behavior SPE, and the Theorem 6.3 family
DefinitionDraftPoA_Supplement_ModelThis module extends the published draft-auction model with exactly the objects required by Theorems 5.1, 6.2, and 6.3.
For additive item values it defines the induced valuation. For nonnegative item values it defines the unit-demand valuation
Per-item no-overbidding at current holdings requires a named action to satisfy
The restricted pure-Nash and behavior-SPE predicates require this condition for every equilibrium action at every public node and allow only deviations satisfying the same restriction. A behavior strategy is a node-indexed probability mass function on legal actions. Expected continuation utility and welfare are obtained recursively over the finite public game tree, with bidders' current action draws independent. Being pure along the path means that each action distribution at a nonterminal prefix of the realized path is a point mass; damaged off-path subgames may mix.
The price of stability first takes the infimum of the welfare ratio over equilibria of one fixed instance and only then the supremum over instances. Ratios use , with for and .
Finally, the module defines the explicit Appendix D.2 family: sink items, two rent blocks of items, one private item, optional dummy items, bidders and two sink bidders per sink item, and the priority order . The parameters are the immutable harmonic-instance definitions from the published mission.
import Mathlib
import Definitions.Def_DraftPoA_Auction
import Definitions.Def_DraftPoA_Equilibria
import Definitions.Def_DraftPoA_BadInstance
namespace DraftPoA.Supplement
/-!
# Price of stability, restricted play, and behavior equilibria for the draft auction
H. T. Truong, N. Thach, H. Chan, M. Guo, *The Price of Anarchy of Draft Auctions*, STOC 2027
submission (manuscript sha256 270ffdaa…), §2, p.5 (PDF 6), Definition 6.1, p.11 (PDF 12),
and Appendix D.2, pp.28–32 (PDF 29–33).
This file extends the published `DraftPoA` model without changing it. It adds the instance-wise
infimum needed for price of stability, per-item no-overbidding and the corresponding restricted
game, unit-demand valuations, behavior strategies, and the explicit additive/unit-demand family
used in Theorem 6.3.
**Formalization Note.**
* `pureSPEBestRatio` first takes the infimum over pure SPE profiles of one fixed instance.
`additiveGridPoS` then takes the supremum over instances, so the two quantifiers are not pooled.
Ratios use the published mission's `ℝ≥0∞` convention: positive welfare divided by zero is
`⊤`, while `0/0 = 0`.
* Per-item no-overbidding uses the bidder's marginal value at her current public holdings, for
every item in the named set. `IsRestrictedPureNash` and `IsRestrictedBehaviorSPE` restrict both
the equilibrium profile and every allowed deviation.
* A behavior strategy assigns a discrete probability mass function to actions at every public
node. The games in Theorem 6.3 have `δ > 0`, finitely many grid bids, finite item sets, and a
finite horizon, so this represents every behavior strategy of the source. The expectation is
the finite-horizon independent product of the bidders' action distributions, written recursively.
* `PureAlongPath` means that some legal pure profile generates the equilibrium path and every
behavior distribution at a nonterminal prefix of that path is the corresponding point mass.
Off-path damaged subgames may mix.
* In the explicit family, items are the `N` sink items, two rent blocks of `rOf N` items, one
private item, and then `d` dummy items. Bidders are `A`, `P`, `W`, and two sink bidders per
sink item, in that priority order. The parameters `Kof`, `deltaOf`, `alpha`, `sigma`, `phi`,
`wOf`, `hOf`, and `rOf` are the immutable published definitions from the base mission.
-/
open scoped BigOperators ENNReal
variable {n m : ℕ}
/-! ## Additive and unit-demand valuations -/
/-- The additive valuation generated by nonnegative item values `c`. -/
def additiveValue (c : Fin n → Fin m → ℝ) (i : Fin n) (S : Finset (Fin m)) : ℝ :=
∑ j ∈ S, c i j
/-- The unit-demand valuation `max_{j ∈ S} c(j)`, with value `0` on the empty set (p.5). -/
noncomputable def unitDemandValue (c : Fin m → ℝ) (S : Finset (Fin m)) : ℝ :=
if hS : S.Nonempty then S.sup' hS c else 0
/-- A unit-demand valuation with nonnegative item values (p.5). -/
def IsUnitDemand (v : Finset (Fin m) → ℝ) : Prop :=
∃ c : Fin m → ℝ, (∀ j, 0 ≤ c j) ∧ ∀ S, v S = unitDemandValue c S
/-- Item data for Theorem 5.1: nonnegative values, capped by `Mbar`, and integer multiples of
the positive bid increment `δ`. -/
def IsAdditiveGridData (c : Fin n → Fin m → ℝ) (δ Mbar : ℝ) : Prop :=
∀ i j, 0 ≤ c i j ∧ c i j ≤ Mbar ∧ ∃ k : ℕ, c i j = k * δ
/-! ## Per-item no-overbidding and the restricted game -/
/-- Definition 6.1: at holdings `H`, `(beta, X)` does not overbid per item when
`beta ≤ v(H ∪ {j}) - v(H)` for every named item `j`. -/
def IsNoOverbidAction (v : Finset (Fin m) → ℝ) (i : Fin n) (nu : DraftPoA.Node n m)
(a : ℝ × Finset (Fin m)) : Prop :=
∀ j ∈ a.2, a.1 ≤ v (DraftPoA.holdings nu i ∪ {j}) - v (DraftPoA.holdings nu i)
/-- A pure strategy never overbids per item at any legal nonterminal public node. -/
def StrategyNoOverbid {δ Mbar : ℝ} (v : Finset (Fin m) → ℝ) (i : Fin n)
(s : DraftPoA.Strategy n m δ Mbar) : Prop :=
∀ nu, DraftPoA.IsNode δ Mbar nu → (DraftPoA.remaining nu).Nonempty →
IsNoOverbidAction v i nu (s.act nu)
/-- Every strategy in a pure profile never overbids per item. -/
def ProfileNoOverbid {δ Mbar : ℝ} (v : Fin n → Finset (Fin m) → ℝ)
(b : Fin n → DraftPoA.Strategy n m δ Mbar) : Prop :=
∀ i, StrategyNoOverbid (v i) i (b i)
/-- Pure Nash equilibrium of the per-item restricted game: the played strategies and all
admissible deviations obey per-item no-overbidding at every node. -/
def IsRestrictedPureNash [NeZero n] {δ Mbar : ℝ} (prio : Equiv.Perm (Fin n))
(v : Fin n → Finset (Fin m) → ℝ) (b : Fin n → DraftPoA.Strategy n m δ Mbar) : Prop :=
ProfileNoOverbid v b ∧
∀ (i : Fin n) (s : DraftPoA.Strategy n m δ Mbar), StrategyNoOverbid (v i) i s →
DraftPoA.u prio v (Function.update b i s) i ≤ DraftPoA.u prio v b i
/-! ## Behavior strategies and behavior subgame perfection -/
/-- A behavior strategy: a probability distribution over actions at every public node, supported
on legal actions at every legal nonterminal node. -/
structure BehaviorStrategy (n m : ℕ) (δ Mbar : ℝ) where
act : DraftPoA.Node n m → PMF (ℝ × Finset (Fin m))
legal : ∀ nu, DraftPoA.IsNode δ Mbar nu → (DraftPoA.remaining nu).Nonempty →
∀ a, act nu a ≠ 0 → DraftPoA.IsLegalAction δ Mbar nu a
/-- The probability of an action profile at one node, under independent behavior randomization. -/
noncomputable def actionProfileWeight {δ Mbar : ℝ}
(b : Fin n → BehaviorStrategy n m δ Mbar) (nu : DraftPoA.Node n m)
(a : Fin n → ℝ × Finset (Fin m)) : ℝ :=
(∏ i, (b i).act nu (a i)).toReal
/-- One public round after the sampled action profile `a`. -/
noncomputable def behaviorStep [NeZero n] (prio : Equiv.Perm (Fin n))
(a : Fin n → ℝ × Finset (Fin m)) (nu : DraftPoA.Node n m) : DraftPoA.Node n m :=
let w := DraftPoA.winner prio a
nu ++ [(w, (a w).1, (a w).2)]
/-- Expected value of a terminal-node statistic after at most `k` further rounds. At each round
the bidders' behavior actions are sampled independently. -/
noncomputable def behaviorExpect [NeZero n] {δ Mbar : ℝ} (prio : Equiv.Perm (Fin n))
(b : Fin n → BehaviorStrategy n m δ Mbar) (terminal : DraftPoA.Node n m → ℝ) :
ℕ → DraftPoA.Node n m → ℝ
| 0, nu => terminal nu
| k + 1, nu =>
if DraftPoA.remaining nu = ∅ then terminal nu
else ∑' a : Fin n → ℝ × Finset (Fin m),
actionProfileWeight b nu a * behaviorExpect prio b terminal k (behaviorStep prio a nu)
/-- A bidder's expected continuation utility under a behavior profile, from a public node. -/
noncomputable def behaviorUFrom [NeZero n] {δ Mbar : ℝ} (prio : Equiv.Perm (Fin n))
(v : Fin n → Finset (Fin m) → ℝ) (b : Fin n → BehaviorStrategy n m δ Mbar)
(nu : DraftPoA.Node n m) (i : Fin n) : ℝ :=
behaviorExpect prio b (fun z => DraftPoA.uAt (v i) z i) m nu
/-- Expected welfare under a behavior profile from a public node. -/
noncomputable def behaviorSWFrom [NeZero n] {δ Mbar : ℝ} (prio : Equiv.Perm (Fin n))
(v : Fin n → Finset (Fin m) → ℝ) (b : Fin n → BehaviorStrategy n m δ Mbar)
(nu : DraftPoA.Node n m) : ℝ :=
behaviorExpect prio b (DraftPoA.SWAt v) m nu
/-- Expected welfare from the root under a behavior profile. -/
noncomputable def behaviorSW [NeZero n] {δ Mbar : ℝ} (prio : Equiv.Perm (Fin n))
(v : Fin n → Finset (Fin m) → ℝ) (b : Fin n → BehaviorStrategy n m δ Mbar) : ℝ :=
behaviorSWFrom prio v b []
/-- A behavior strategy never overbids per item: every action in its support at every legal
nonterminal node satisfies Definition 6.1. -/
def BehaviorStrategyNoOverbid {δ Mbar : ℝ} (v : Finset (Fin m) → ℝ) (i : Fin n)
(s : BehaviorStrategy n m δ Mbar) : Prop :=
∀ nu, DraftPoA.IsNode δ Mbar nu → (DraftPoA.remaining nu).Nonempty →
∀ a, s.act nu a ≠ 0 → IsNoOverbidAction v i nu a
/-- Every strategy of a behavior profile never overbids per item. -/
def BehaviorProfileNoOverbid {δ Mbar : ℝ} (v : Fin n → Finset (Fin m) → ℝ)
(b : Fin n → BehaviorStrategy n m δ Mbar) : Prop :=
∀ i, BehaviorStrategyNoOverbid (v i) i (b i)
/-- A behavior-strategy SPE of the per-item restricted game: at every public subgame no bidder
gains by any restricted behavior-strategy deviation. -/
def IsRestrictedBehaviorSPE [NeZero n] {δ Mbar : ℝ} (prio : Equiv.Perm (Fin n))
(v : Fin n → Finset (Fin m) → ℝ) (b : Fin n → BehaviorStrategy n m δ Mbar) : Prop :=
BehaviorProfileNoOverbid v b ∧
∀ nu, DraftPoA.IsNode δ Mbar nu → (DraftPoA.remaining nu).Nonempty →
∀ (i : Fin n) (s : BehaviorStrategy n m δ Mbar), BehaviorStrategyNoOverbid (v i) i s →
behaviorUFrom prio v (Function.update b i s) nu i ≤ behaviorUFrom prio v b nu i
/-- Embed a legal pure strategy as a point-mass behavior strategy. -/
noncomputable def behaviorOfPure {δ Mbar : ℝ} (s : DraftPoA.Strategy n m δ Mbar) :
BehaviorStrategy n m δ Mbar where
act nu := PMF.pure (s.act nu)
legal := by
intro nu hnu hrem a ha
have hEq : a = s.act nu := by
simpa [PMF.pure_apply] using ha
subst a
exact s.legal nu hnu hrem
/-- The behavior profile is point-mass at every node reached on the path generated by a pure
profile; behavior in other subgames is unrestricted. -/
def PureAlongPath [NeZero n] {δ Mbar : ℝ} (prio : Equiv.Perm (Fin n))
(b : Fin n → BehaviorStrategy n m δ Mbar) : Prop :=
∃ p : Fin n → DraftPoA.Strategy n m δ Mbar,
∀ i nu, DraftPoA.IsNode δ Mbar nu → (DraftPoA.remaining nu).Nonempty →
nu.IsPrefix (DraftPoA.play prio p) → (b i).act nu = PMF.pure ((p i).act nu)
/-! ## Price of stability and restricted-game price of anarchy -/
/-- For one fixed instance, the infimum of `OPT/SW` over its pure SPE profiles. -/
noncomputable def pureSPEBestRatio [NeZero n] {δ Mbar : ℝ} (prio : Equiv.Perm (Fin n))
(v : Fin n → Finset (Fin m) → ℝ) : ENNReal :=
⨅ (b : Fin n → DraftPoA.Strategy n m δ Mbar) (_h : DraftPoA.IsPureSPE prio v b),
ENNReal.ofReal (DraftPoA.OPT v) / ENNReal.ofReal (DraftPoA.SW prio v b)
/-- Price of stability for additive, grid-valued instances with `m` items and at least two
bidders: the supremum over instances of their instance-wise equilibrium infimum. -/
noncomputable def additiveGridPoS (m : ℕ) (δ : ℝ) : ENNReal :=
⨆ q : ℕ, ⨆ prio : Equiv.Perm (Fin (q + 2)), ⨆ Mbar : ℝ,
⨆ c : Fin (q + 2) → Fin m → ℝ, ⨆ (_h : IsAdditiveGridData c δ Mbar),
pureSPEBestRatio (δ := δ) (Mbar := Mbar) prio (additiveValue c)
/-- A valuation admitted by Theorem 6.3: additive or unit-demand. -/
def IsAdditiveOrUnitDemand (v : Finset (Fin m) → ℝ) : Prop :=
DraftPoA.IsAdditive v ∨ IsUnitDemand v
/-- Price of anarchy of the per-item restricted game at behavior-strategy SPE, for instances in
which each bidder is additive or unit-demand. -/
noncomputable def restrictedBehaviorPoA (m : ℕ) (δ : ℝ) : ENNReal :=
⨆ q : ℕ, ⨆ prio : Equiv.Perm (Fin (q + 1)), ⨆ Mbar : ℝ,
⨆ v : Fin (q + 1) → Finset (Fin m) → ℝ,
⨆ (_hv : ∀ i, IsAdditiveOrUnitDemand (v i)), ⨆ (_hcap : DraftPoA.IsCapped v Mbar),
⨆ b : Fin (q + 1) → BehaviorStrategy (q + 1) m δ Mbar,
⨆ (_heq : IsRestrictedBehaviorSPE prio v b),
ENNReal.ofReal (DraftPoA.OPT v) / ENNReal.ofReal (behaviorSW prio v b)
/-! ## The explicit family of Appendix D.2 -/
/-- The number of items in the unpadded Theorem 6.3 instance: `N + 2r + 1`. -/
noncomputable def supplementItemCount (N : ℕ) : ℕ := N + 2 * DraftPoA.rOf N + 1
/-- The number of bidders: `A`, `P`, `W`, and two sink bidders for every sink item. -/
def supplementBidderCount (N : ℕ) : ℕ := 2 * N + 3
instance (N : ℕ) : NeZero (supplementBidderCount N) := ⟨by simp [supplementBidderCount]⟩
/-- The priority order `A ≻ P ≻ W ≻ C₁ ≻ C₁' ≻ ⋯`. -/
def supplementPriority (N : ℕ) : Equiv.Perm (Fin (supplementBidderCount N)) := Equiv.refl _
/-- Item values of the unit-demand punisher `W`: `w` on either rent block, `h` on the private
item, and zero on sink and dummy items. -/
noncomputable def punisherItemValue (N d : ℕ) (x : Fin (supplementItemCount N + d)) : ℝ :=
if N ≤ x.val ∧ x.val < N + 2 * DraftPoA.rOf N then DraftPoA.wOf N
else if x.val = N + 2 * DraftPoA.rOf N then DraftPoA.hOf N
else 0
/-- Per-item values of the additive bidders `A`, `P`, and the two sink bidders per sink item. -/
noncomputable def supplementAdditiveItemValue (N d : ℕ) (i : Fin (supplementBidderCount N))
(x : Fin (supplementItemCount N + d)) : ℝ :=
if i.val = 0 then
if x.val < N then DraftPoA.alpha N (x.val + 1)
else if N ≤ x.val ∧ x.val < N + DraftPoA.rOf N then DraftPoA.hOf N else 0
else if i.val = 1 then
if x.val < N then DraftPoA.phi N (x.val + 1)
else if N + DraftPoA.rOf N ≤ x.val ∧ x.val < N + 2 * DraftPoA.rOf N
then DraftPoA.hOf N else 0
else if i.val = 3 + 2 * x.val ∨ i.val = 4 + 2 * x.val then
if x.val < N then DraftPoA.sigma N (x.val + 1) else 0
else 0
/-- The explicit valuations of Appendix D.2, extended by `d` dummy items. Bidder `W` (index 2)
is unit-demand; every other bidder is additive. -/
noncomputable def supplementValuation (N d : ℕ) (i : Fin (supplementBidderCount N))
(S : Finset (Fin (supplementItemCount N + d))) : ℝ :=
if i.val = 2 then unitDemandValue (punisherItemValue N d) S
else ∑ x ∈ S, supplementAdditiveItemValue N d i x
end DraftPoA.Supplement