Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1 — Tight four-thirds loss of full transparency

Proved
TransparencyTeamContracts.Submodular.theorem_4_1

by mikedeng1 · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmic-game-theorymechanism-designp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1

For every finite multi-agent contract instance with a finite nonempty state space, arbitrary prior DDD, nonnegative state-independent costs, and monotone submodular state technologies fω:2[n]→[0,1]f_\omega:2^{[n]}\to[0,1]fω​:2[n]→[0,1], full revelation satisfies

UPF(D)≥34OPT⁡(D).U_P^F(D)\ge\frac34\operatorname{OPT}(D).UPF​(D)≥43​OPT(D).

Here OPT⁡\operatorname{OPT}OPT optimizes the public information and signal-dependent contract jointly with principal-favorable pure Nash equilibrium selection. No zero-baseline or positive-cost restriction is imposed. The factor is sharp even for additive technologies: for every 1≤β<4/31\le\beta<4/31≤β<4/3, there exists a finite additive instance with

UPF(D)>0,OPT⁡(D)>βUPF(D).U_P^F(D)>0,\qquad\operatorname{OPT}(D)>\beta U_P^F(D).UPF​(D)>0,OPT(D)>βUPF​(D).

The two clauses form one goal. The multiplied universal inequality also covers zero optimal payoff and does not require division by the full-information value.

Differences from the source:

  • encoding: finite agents and states, real probabilities and contracts, optimal utilities → Fin indices, a simplex prior, and suprema of operational contract and public-scheme payoffs; reason: finite relabeling preserves all instances; admissible payoff sets are nonempty and bounded, and suprema give the same optimal values without asserting attainment
  • encoding: monotone submodularity with marginals tested for every agent → monotone IsSuccess plus the published diminishing-returns predicate for agents outside the larger set; reason: the omitted membership cases follow from monotonicity, so the function class is identical
  • encoding: full revelation is a 4/3 approximation and that factor is tight even for additive rewards → a multiplied 3/4 utility bound conjoined with a positive-payoff additive counterexample to each beta in [1,4/3); reason: multiplication preserves the approximation guarantee at zero payoff; the quantified sharpness is precisely impossibility of any better approximation factor
  • encoding: public signals on compact spaces and expected payoffs → compact Borel signal spaces, measurable posteriors and strategies, and explicit payoff integrability; reason: these are the usual meaningful-expectation conventions; finite-state measurable contract payoffs are bounded and hence integrable, so no source instance or support size is excluded
Preamble
import Mathlib
import Definitions.Def_TransparencyTeamContracts_Submodular_Information
Formal statement
namespace TransparencyTeamContracts.Submodular

/-- Theorem 4.1, printed p.9 (PDF 11). Both the universal guarantee and the
additive sharpness clause are part of this single goal. -/
theorem theorem_4_1 :
    (∀ (n m : ℕ) (M : Model n m) (D : Belief m),
      (∀ ω, SubsamplingSM.Offline.IsSubmodular (M.f ω)) →
        (3 / 4 : ℝ) * optimalInformation M D ≤ fullInformation M D) ∧
    (∀ β : ℝ, 1 ≤ β → β < (4 / 3 : ℝ) →
      ∃ (n m : ℕ) (M : Model n m) (D : Belief m),
        (∀ ω, FairTeamContracts.IsAdditive (M.f ω)) ∧
        0 < fullInformation M D ∧ β * fullInformation M D < optimalInformation M D) := by sorry

end TransparencyTeamContracts.Submodular
Source
Paul Duetting, Yingkai Li, Inbal Talgam-Cohen, Jinzhao Wu, STOC 2027 submission #1292 (October 2026), Theorem 4.1, printed p.9 (PDF p.11), proof printed pp.15–17 (PDF pp.17–19); https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1292.pdf; PDF SHA-256 0aa8b61daf25346bcfca67a178c55762d05abe3f79b2b66a6d2ad6dfed9b3321
Human review
  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me