Proof of Theorem 4.1 — every strict better response strictly increases
ProvedCompDesign.thm_4_1_potential_increasesThroughout, is the set of agents, the budget, the private costs, and a value function satisfying Assumption 3.1: , monotone () and submodular ( whenever and ). The marginal-contribution payment is if and , and otherwise (8); agent 's utility is if and otherwise.
Assume moreover for every agent . Let and , ordered lexicographically. If is a strict better response from in (one agent switches its participation and its utility strictly rises), then
Opt-ins and opt-outs from positive-value states raise the first coordinate; an opt-out from a zero-value state keeps and raises the second coordinate. Since there are finitely many states, this is what makes every better-response sequence terminate.
Differences from the source: none.
import Mathlib import Definitions.Def_CompDesignBFM_IsMonotoneSF import Definitions.Def_CompDesignBFM_IsSubmodularSF import Definitions.Def_CompDesign_IsStrictImprovement import Definitions.Def_CompDesign_PhiLex open CompDesignBFM
namespace CompDesign
/-- The lexicographic potential increases, proof of Theorem 4.1, §4.1, p.17 (PDF 20) of Anagnostides et al., *Compensation Design*, arXiv:2607.14438 (version of November 3, 2026, sha256 3d305d4d…):
every strict unilateral improvement `S → S'` of `Γ^mc` strictly increases
`Φ′(S) = (Φ(S), −∑_{i∈S} c_i)` in the lexicographic order, where `Φ(S) = v(S) ∏_{i∈S} (1 − c_i/B)`.
**Formalization Note.** Assumption 3.1, `B > 0`, `c ≥ 0` and Theorem 4.1's `max_i c_i < B` are binders.
The order on `ℝ ×ₗ ℝ` is lexicographic. -/
theorem thm_4_1_potential_increases {n : ℕ} (v : Finset (Fin n) → ℝ) (B : ℝ) (c : Fin n → ℝ)
(hB : 0 < B) (hv0 : v ∅ = 0) (hm : IsMonotoneSF v) (hs : IsSubmodularSF v)
(hc : ∀ j, 0 ≤ c j) (hcB : ∀ j, c j < B) (S S' : Finset (Fin n))
(h : IsStrictImprovement v B c S S') :
PhiLex v B c S < PhiLex v B c S' := by sorry
end CompDesign
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.