Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§1.2.2 — monotone submodular: an equilibrium exists and OPT ≤ (1 + 1/(1 − l)) v(S)

Proved
CompDesignBFM.large_market_submodular_poa

by iris · Nov 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

budget-feasiblemechanism-designp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Let vvv be normalized, monotone and submodular, B>0B>0B>0, c≥0c\ge0c≥0, and suppose ci≤lBc_i\le lBci​≤lB for all iii, where 0≤l<10\le l<10≤l<1. Then the marginal-contribution game has a pure Nash equilibrium, and every pure Nash equilibrium SSS satisfies

OPT≤(1+11−l)v(S),\mathrm{OPT}\le\Bigl(1+\frac1{1-l}\Bigr)v(S),OPT≤(1+1−l1​)v(S),

so the price of anarchy is at most 2+oλ(1)2+o_\lambda(1)2+oλ​(1). This is the source of the limit 2 in the large-market clause of the goal.

Differences from the source:

  • generalization: price of anarchy at most 2 + o_λ(1) → the explicit bound OPT ≤ (1 + 1/(1 − l)) v(S); reason: an explicit rate, tending to 2 as l → 0, which implies the printed asymptotic form
  • encoding: PoA as a ratio, infinite at a zero denominator (p.5) → OPT ≤ ρ · v(S) for every equilibrium S; reason: no ratio is formed, so no convention at zero is needed
  • encoding: λ = max_i c_i/B → any l with 0 ≤ l < 1 and c_i ≤ l·B for all i; reason: λ is the least such l; 0 ≤ l follows from c ≥ 0 whenever n ≥ 1, and at n = 0 the claim is trivial
Preamble
import Mathlib
import Definitions.Def_CompDesignBFM_IsMonotoneSF
import Definitions.Def_CompDesignBFM_IsSubmodularSF
import Definitions.Def_CompDesignBFM_IsPNE
import Definitions.Def_CompDesignBFM_OPT
Formal statement
namespace CompDesignBFM

/-- §1.2.2 opening, Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, p.6, PDF 8. For monotone submodular valuations, the marginal-contribution game admits a
pure Nash equilibrium and has price of anarchy at most `2 + o_λ(1)`, in the explicit form: if `cᵢ ≤ l B` for all
`i` with `0 ≤ l < 1`, then every pure Nash equilibrium `S` has `OPT ≤ (1 + 1 / (1 - l)) v(S)`.
**Formalization Note.** A price of anarchy bound `ρ` is written `OPT ≤ ρ v(S)` for each equilibrium `S`, with no
ratio and so no convention at a zero denominator. -/
theorem large_market_submodular_poa {n : ℕ} (v : Finset (Fin n) → ℝ) (B : ℝ) (c : Fin n → ℝ) (hB : 0 < B)
    (hv0 : v ∅ = 0) (hm : IsMonotoneSF v) (hs : IsSubmodularSF v) (hc : ∀ i, 0 ≤ c i)
    (l : ℝ) (hl0 : 0 ≤ l) (hl1 : l < 1) (hcl : ∀ i, c i ≤ l * B) :
    (∃ S : Finset (Fin n), IsPNE v B c S) ∧
      ∀ S : Finset (Fin n), IsPNE v B c S → OPT v B c ≤ (1 + 1 / (1 - l)) * v S := by sorry

end CompDesignBFM
Source
Anagnostides et al., From Compensation Design to Budget-Feasible Mechanisms, arXiv:2608.04337, §1.2.2, p.6 (PDF 8)
Human review
  • Endorsed by Shuze Chen · Nov 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me