Theorem 3.2 — potential maximizers are pure Nash equilibria
ProvedCompDesignBFM.theorem_3_2budget-feasiblemechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be normalized and monotone, and . If is a global maximizer of the potential , with or , then is a pure Nash equilibrium of the marginal-contribution rule.
This is what makes the potential maximizer an equilibrium allocation, and the mechanism's budget feasibility rests on it.
Differences from the source:
- reading: the global maximizer S of Φ^F_c → a global maximizer with S = ∅ or Φ^F_c(S) > 0; reason: uniqueness needs the Remark 2.1 tie-breaking with ∅ first, whose maximizer has this property, and the printed proof says 'Now suppose S ≠ ∅. Then Φ(S) > 0'. Without it F ≡ 0, n = 1, B = 1, c₁ = 1/2, S = {1} fails
Preamble
import Mathlib import Definitions.Def_CompDesignBFM_IsMonotoneSF import Definitions.Def_CompDesignBFM_IsPNE import Definitions.Def_CompDesignBFM_pot
Formal statement
namespace CompDesignBFM
/-- Theorem 3.2, Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, p.15, PDF 17. For a normalized monotone `F`, the global maximizer of `Φ^F_c` is a
pure Nash equilibrium of the marginal-contribution rule.
**Formalization Note.** "The global maximizer" is the one of Remark 2.1, with `∅` first, whose potential
is positive unless it is `∅`; the printed proof says "Now suppose `S ≠ ∅`. Then `Φ^F_c(S) > 0`". That
property is the hypothesis `hS₀`. Without it `F ≡ 0`, `n = 1`, `B = 1`, `c₁ = 1/2`, `S = {1}` fails. -/
theorem theorem_3_2 {n : ℕ} (F : Finset (Fin n) → ℝ) (B : ℝ) (c : Fin n → ℝ) (hB : 0 < B)
(hF0 : F ∅ = 0) (hF : IsMonotoneSF F) (hc : ∀ i, 0 ≤ c i) (S : Finset (Fin n))
(hS : ∀ T, pot F B c T ≤ pot F B c S) (hS₀ : S = ∅ ∨ 0 < pot F B c S) :
IsPNE F B c S := by sorry
end CompDesignBFM
Source
Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, Theorem 3.2, p.15 (PDF 17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.