Theorem C.1 — is a pure equilibrium of the scaled marginal-contribution rule
ProvedCompDesignBFM.Supplement.theorem_C_1budget-feasiblecompensation-designmechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , and normalized and -self-bounding. Let be the global maximizer of
ties broken by a fixed total order on in which comes first. For every cost vector , is a pure Nash equilibrium of the game induced by the scaled marginal-contribution rule (Algorithm C.1).
This is the equilibrium-existence step of the extension of the framework from self-bounding to -self-bounding valuations.
Differences from the source:
- reading: β-self-bounding with β unrestricted → 0 < β; reason: Algorithm C.1 and Φ^{(β)} divide by β; the appendix treats β ≥ 1 classes and never β ≤ 0
- encoding: S^{(β)}(c), the maximizer of Φ^{(β)}_c with ties broken by a fixed total order with ∅ first → Amc v (B/β) r c with IsPriority r; reason: pot v (B/β) c = Φ^{(β)}_c because c_i/(B/β) = βc_i/B
- encoding: every cost vector c → every nonnegative cost vector; reason: the section defines Φ^{(β)}_c for any nonnegative vector c (p.45)
Preamble
import Mathlib import Definitions.Def_CompDesignBFM_IsPriority import Definitions.Def_CompDesignBFM_Amc import Definitions.Def_CompDesignBFM_Supplement_IsBetaSelfBounding import Definitions.Def_CompDesignBFM_Supplement_IsPNEOf import Definitions.Def_CompDesignBFM_Supplement_scaledPay
Formal statement
namespace CompDesignBFM
namespace Supplement
/-- Theorem C.1 (pure equilibrium), Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, p.45, PDF 47. Let `v` be normalized and `β`-self-bounding.
For every cost vector `c`, `S^(β)(c)` is a pure Nash equilibrium of the game induced by the scaled
marginal-contribution rule of Algorithm C.1.
**Formalization Note.** `S^(β)(c)`, the global maximizer of `Φ^(β)_c(S) = v(S) ∏_(i ∈ S) (1 − β cᵢ/B)₊`
with ties broken by a fixed total order with `∅` first, is `Amc v (B / β) r c` for a priority `r`
(`IsPriority r`): `cᵢ/(B/β) = β cᵢ/B`. Cost vectors are nonnegative ("for any nonnegative vector c",
p.45). `B > 0` and `β > 0` are the model's. -/
theorem theorem_C_1 {n : ℕ} (v : Finset (Fin n) → ℝ) (B β : ℝ) (hB : 0 < B) (hβ : 0 < β)
(hv0 : v ∅ = 0) (hv : IsBetaSelfBounding β v) (r : Finset (Fin n) → ℕ) (hr : IsPriority r)
(c : Fin n → ℝ) (hc : ∀ i, 0 ≤ c i) :
IsPNEOf (scaledPay v B β) c (Amc v (B / β) r c) := by sorry
end Supplement
end CompDesignBFM
Source
Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, Theorem C.1, p.45 (PDF 47)