Proof of Theorem 4.1 — strictly profitable opt-out
ProvedCompDesign.thm_4_1_opt_out_iffcompensation-designp2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchypure-nash-equilibriumsubmodular-functions
Throughout, 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 , write , and suppose . Then opting out is strictly profitable, , if and only if , and
This is the opt-out case, from a positive-value state, of the potential argument for Theorem 4.1.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_CompDesignBFM_IsMonotoneSF import Definitions.Def_CompDesignBFM_IsSubmodularSF import Definitions.Def_CompDesignBFM_mcPay import Definitions.Def_CompDesign_util open CompDesignBFM
Formal statement
namespace CompDesign
/-- Opt-out equivalence, 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…).
For an agent `i ∈ S` with `v(S) > 0`, opting out is strictly profitable iff
`B (v(S) − v(S₋ᵢ))/v(S) < c_i`, iff `v(S₋ᵢ) > (1 − c_i/B) v(S)`, where `S₋ᵢ = S ∖ {i}`.
**Formalization Note.** The standing assumptions (Assumption 3.1, `B > 0`, `c ≥ 0`) and the hypothesis
`max_i c_i < B` of Theorem 4.1 are kept as binders. -/
theorem thm_4_1_opt_out_iff {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 : Finset (Fin n)) (i : Fin n) (hi : i ∈ S) (hpos : 0 < v S) :
(util v B c S i < util v B c (S.erase i) i ↔ mcPay v B S i < c i) ∧
(mcPay v B S i < c i ↔ (1 - c i / B) * v S < v (S.erase i)) := 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…), proof of Theorem 4.1, §4.1, p.17 (PDF 20)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.