Theorem 4.1 — tight loss of non-discrimination , , for additive and submodular rewards
ProvedFairTeamContracts.theorem_4_1algorithmic-game-theorycontract-theoryfairnessp2o-gran-per-chapterp2o-plan-paperp2o-v1submodular
Throughout, is a success function (monotone, , values in ) on the agents , and the costs satisfy . Let and be the optimal revenue of non-discriminatory and of fair team contracts. Then:
- the equation has a unique root ();
- for every additive and all costs ,
- the same holds for every submodular ;
- the factor is tight for both classes: there is an instance, additive and submodular, with and .
Restricting a principal to equal shares therefore costs at most a factor of the best fair revenue, and no smaller factor is valid.
Differences from the source:
- encoding: OPT_nd ≥ OPT/(1 + ρ) → optFair f c ≤ (1 + ρ) · optND f c; reason: multiplied by 1 + ρ > 0
- reading: this approximation factor 1 + ρ is tight → an instance, additive and submodular, with 0 < OPT and OPT = (1 + ρ) · OPT_nd; reason: the strongest reading of tightness: the factor is attained, so no smaller factor is valid
- encoding: ρ ∈ (0, 1) is the unique root, used in the bound → clause ∃! ρ ∈ (0, 1) with the cubic = 0, and the bounds for every such ρ; reason: the same ρ by uniqueness
- encoding: submodular (Definition 2.4, for every i ∈ [n]) → published IsSubmodular (diminishing returns for e ∉ B) together with the monotonicity of IsSuccessFn; reason: Definition 2.4's extra cases i ∈ S′ only say a marginal is ≥ 0, which is monotonicity; same class of functions
- encoding: OPT, OPT_nd the revenues of optimal fair / non-discriminatory contracts → suprema optFair, optND over fair / feasible non-discriminatory team contracts; reason: the sets are nonempty and bounded by 1, so the suprema equal the optima, which exist
Preamble
import Mathlib import Definitions.Def_SubsamplingSM_Offline_IsSubmodular import Definitions.Def_FairTeamContracts_IsSuccessFn import Definitions.Def_FairTeamContracts_IsAdditive import Definitions.Def_FairTeamContracts_optFair import Definitions.Def_FairTeamContracts_optND
Formal statement
namespace FairTeamContracts
/-- **Theorem 4.1 (Tight loss of non-discrimination)** (Chen, Castiglioni, Li, *Fair Team Contracts*, arXiv:2512.19388 (manuscript sha256 b8a12d9b…), Theorem 4.1, p.13;
proof pp.15–19). Let `OPT_nd` and `OPT` be the optimal revenue of non-discriminatory and of fair
team contracts. Then:
1. the cubic `ρ³ − ρ² − 2ρ + 1 = 0` has a unique root `ρ ∈ (0, 1)`;
2. for that `ρ`, every additive success function and nonnegative costs give
`OPT_nd ≥ OPT/(1 + ρ)`;
3. the same holds for every monotone, normalized, submodular success function;
4. the factor `1 + ρ` is tight for both classes: some instance, additive and submodular, has
`OPT > 0` and `OPT = (1 + ρ) · OPT_nd`.
**Formalization Note.** The inequality is written `OPT ≤ (1 + ρ) · OPT_nd`. OPT and OPT_nd are
suprema over fair, resp. feasible non-discriminatory, team contracts (see `optFair`, `optND`).
The bounds quantify over every `n`, every success function of the class and every cost vector
`c ≥ 0`. Tightness is stated with equality and `OPT > 0`, so no factor below `1 + ρ` is valid. -/
theorem theorem_4_1 :
(∃! ρ : ℝ, ρ ∈ Set.Ioo (0 : ℝ) 1 ∧ ρ ^ 3 - ρ ^ 2 - 2 * ρ + 1 = 0) ∧
∀ ρ : ℝ, ρ ∈ Set.Ioo (0 : ℝ) 1 → ρ ^ 3 - ρ ^ 2 - 2 * ρ + 1 = 0 →
(∀ (n : ℕ) (f : Finset (Fin n) → ℝ) (c : Fin n → ℝ), IsSuccessFn f → IsAdditive f →
(∀ i, 0 ≤ c i) → optFair f c ≤ (1 + ρ) * optND f c) ∧
(∀ (n : ℕ) (f : Finset (Fin n) → ℝ) (c : Fin n → ℝ), IsSuccessFn f →
SubsamplingSM.Offline.IsSubmodular f → (∀ i, 0 ≤ c i) → optFair f c ≤ (1 + ρ) * optND f c) ∧
(∃ (n : ℕ) (f : Finset (Fin n) → ℝ) (c : Fin n → ℝ), IsSuccessFn f ∧ IsAdditive f ∧
SubsamplingSM.Offline.IsSubmodular f ∧ (∀ i, 0 ≤ c i) ∧
0 < optFair f c ∧ optFair f c = (1 + ρ) * optND f c) := by sorry
end FairTeamContracts
Source
Chen, Castiglioni, Li, Fair Team Contracts, arXiv:2512.19388 (manuscript sha256 b8a12d9b…), Theorem 4.1, p.13 (proof: pp.15–19)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.