Proposition 3.1 — the marginal-contribution rule is budget feasible
ProvedCompDesign.proposition_3_1compensation-designp2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchypure-nash-equilibriumsubmodular-functions
Let and let satisfy Assumption 3.1 (, monotone, submodular). Let if and , and otherwise (8).
Proposition 3.1 (Budget feasibility). The marginal-contribution rule is budget feasible:
Budget feasibility is a requirement of the model on every payment rule (§3.1); this proposition certifies that is a game of the model. It follows from Lemma 3.2, .
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_CompDesignBFM_IsMonotoneSF import Definitions.Def_CompDesignBFM_IsSubmodularSF import Definitions.Def_CompDesignBFM_mcPay open CompDesignBFM
Formal statement
namespace CompDesign
/-- Proposition 3.1 (Budget feasibility), §3.2.2, p.16 (PDF 19) of Anagnostides et al., *Compensation Design*, arXiv:2607.14438 (version of November 3, 2026, sha256 3d305d4d…):
the marginal-contribution rule (8) is budget feasible, `∑_{i∈S} p^mc_i(S) ≤ B` for all `S ⊆ N`.
**Formalization Note.** Assumption 3.1 and `B > 0` are the standing assumptions of §3.1. -/
theorem proposition_3_1 {n : ℕ} (v : Finset (Fin n) → ℝ) (B : ℝ) (hB : 0 < B) (hv0 : v ∅ = 0)
(hm : IsMonotoneSF v) (hs : IsSubmodularSF v) (S : Finset (Fin n)) :
∑ i ∈ S, mcPay v B S i ≤ B := by sorry
end CompDesign
Source
Anagnostides, Bhawalkar, Liaw, Mehta, Paes Leme, Teng, Velegkas, Zheng, Compensation Design, arXiv:2607.14438 (version of November 3, 2026, sha256 3d305d4d…), §3.2.2, Proposition 3.1, p.16 (PDF 19)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.