Proof of Theorem 4.1 — strictly profitable opt-in
ProvedCompDesign.thm_4_1_opt_in_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 (the hypothesis of Theorem 4.1). Let . Then:
- if opting in is strictly profitable, , then ;
- opting in is strictly profitable if and only if ;
- if , then
This is the opt-in case of the potential argument for Theorem 4.1: a strictly profitable opt-in raises .
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-in 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`: a strictly profitable opt-in needs `v(S ∪ {i}) > 0`; it is strictly profitable
iff `B (v(S ∪ {i}) − v(S))/v(S ∪ {i}) > c_i`; and, when `v(S ∪ {i}) > 0`, this holds iff
`(1 − c_i/B) v(S ∪ {i}) > v(S)`.
**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. The payment at `S ∪ {i}` is `mcPay`, which for
`v(S ∪ {i}) > 0` is `B (v(S ∪ {i}) − v(S))/v(S ∪ {i})` since `(S ∪ {i}) ∖ {i} = S`. -/
theorem thm_4_1_opt_in_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) :
(util v B c S i < util v B c (insert i S) i → 0 < v (insert i S)) ∧
(util v B c S i < util v B c (insert i S) i ↔ c i < mcPay v B (insert i S) i) ∧
(0 < v (insert i S) →
(c i < mcPay v B (insert i S) i ↔ v S < (1 - c i / B) * v (insert i S))) := 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.