Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.2 (corrected) — neutral affine maximizers: Pdim(U)≥⌊n/2⌋\mathrm{Pdim}(\mathcal U) \ge \lfloor n/2 \rfloorPdim(U)≥⌊n/2⌋

Proved
BalcanDDA.NAM.theorem5_2_pdim_lower_bound

by mikedeng1 · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

learning-theorymechanism-designp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-paperp2o-v1pseudo-dimension

Consider n≥1n\ge1n≥1 agents and m≥2m\ge2m≥2 alternatives, and let U={uρ∣ρ∈R≥0n, {i∣ρ[i]=0}≠∅}\mathcal U=\{u_\rho \mid \rho\in\mathbb R^n_{\ge0},\ \{i\mid\rho[i]=0\}\ne\emptyset\}U={uρ​∣ρ∈R≥0n​, {i∣ρ[i]=0}=∅} be the class of social-welfare utilities uρ(v)=∑i=1nvi(ψρ(v))u_\rho(v)=\sum_{i=1}^n v_i(\psi_\rho(v))uρ​(v)=∑i=1n​vi​(ψρ​(v)) of neutral affine maximizers, where ψρ(v)\psi_\rho(v)ψρ​(v) is a maximizer over j∈[m]j\in[m]j∈[m] of ∑iρ[i]vi(j)\sum_{i}\rho[i]v_i(j)∑i​ρ[i]vi​(j), chosen by an arbitrary but fixed tie-breaking rule. Then

Pdim(U) ≥ ⌊n2⌋,\mathrm{Pdim}(\mathcal U)\ \ge\ \Bigl\lfloor \frac n2\Bigr\rfloor ,Pdim(U) ≥ ⌊2n​⌋,

i.e. there are ⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋ valuation profiles v(1),…,v(⌊n/2⌋)∈Rnmv^{(1)},\dots,v^{(\lfloor n/2\rfloor)}\in\mathbb R^{nm}v(1),…,v(⌊n/2⌋)∈Rnm and witnesses z(1),…,z(⌊n/2⌋)∈Rz^{(1)},\dots,z^{(\lfloor n/2\rfloor)}\in\mathbb Rz(1),…,z(⌊n/2⌋)∈R such that for every b∈{0,1}⌊n/2⌋b\in\{0,1\}^{\lfloor n/2\rfloor}b∈{0,1}⌊n/2⌋ some uρ∈Uu_\rho\in\mathcal Uuρ​∈U satisfies uρ(v(ℓ))>z(ℓ)u_\rho(v^{(\ell)})>z^{(\ell)}uρ​(v(ℓ))>z(ℓ) exactly when bℓ=1b_\ell=1bℓ​=1.

Combined with the upper bound Pdim(U)=O(nln⁡m)\mathrm{Pdim}(\mathcal U)=O(n\ln m)Pdim(U)=O(nlnm) that the paper derives from its Theorem 3.3 and Lemma 5.1, this shows that the general pseudo-dimension bound is tight up to logarithmic factors.

Corrections relative to the printed statement (p. 23):

  1. The paper states Pdim(U)≥n/2\mathrm{Pdim}(\mathcal U)\ge n/2Pdim(U)≥n/2; its proof assumes nnn even "without loss of generality" and shatters n/2n/2n/2 profiles. The printed bound fails at n=1n=1n=1: the only admissible parameter is ρ=0\rho=0ρ=0, so U\mathcal UU consists of a single function and Pdim(U)=0<12\mathrm{Pdim}(\mathcal U)=0<\tfrac12Pdim(U)=0<21​. The statement here is ⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋, which equals n/2n/2n/2 for even nnn.
  2. The printed set-builder reads "{ρ[i]∣i=0}≠∅\{\rho[i]\mid i=0\}\neq\emptyset{ρ[i]∣i=0}=∅"; Lemma 5.1 one paragraph earlier writes {i∣ρ[i]=0}≠∅\{i\mid\rho[i]=0\}\neq\emptyset{i∣ρ[i]=0}=∅ (some agent has weight zero), which is the condition used here.
  3. The hypotheses n≥1n\ge1n≥1 and m≥2m\ge2m≥2 are explicit: for n=0n=0n=0 no parameter is admissible and U=∅\mathcal U=\emptysetU=∅; for m=1m=1m=1, U\mathcal UU is a single function. The paper's proof takes m=2m=2m=2; the theorem is stated for every m≥2m\ge2m≥2.

Formalization Note "Pdim(U)≥N\mathrm{Pdim}(\mathcal U)\ge NPdim(U)≥N" is written as the existence of an NNN-tuple of profiles shattered by namClass ψ in the sense of FoundationsML.Regression.Shatters, which uses the strict threshold t i < g (z i). The paper leaves sign(0)\mathrm{sign}(0)sign(0) unspecified; since a shattering is witnessed by finitely many functions, the strict and non-strict readings shatter the same tuples. n / 2 is natural-number division, ⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋. The theorem holds for every outcome rule ψ satisfying IsArgmaxSelector ψ, i.e. for every tie-breaking rule.


Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.

Preamble
import Mathlib
import Definitions.Def_FoundationsML_Regression_Shatters
import Definitions.Def_BalcanDDA_NAM_Model
Formal statement
namespace BalcanDDA.NAM

/-- Theorem 5.2 (Balcan et al., arXiv:1908.02894v4, p. 23), corrected to `⌊n/2⌋`: for
`n ≥ 1` agents, `m ≥ 2` alternatives and every argmax outcome rule `ψ`, the class of NAM
welfare functions pseudo-shatters some `⌊n/2⌋` valuation profiles, i.e.
`Pdim(U) ≥ ⌊n/2⌋`. -/
theorem theorem5_2_pdim_lower_bound (n m : ℕ) (hn : 1 ≤ n) (hm : 2 ≤ m)
    (ψ : (Fin n → ℝ) → (Fin n → Fin m → ℝ) → Fin m) (hψ : IsArgmaxSelector ψ) :
    ∃ v : Fin (n / 2) → (Fin n → Fin m → ℝ),
      FoundationsML.Regression.Shatters (namClass ψ) v := by sorry

end BalcanDDA.NAM
Source
Balcan et al., How Much Data Is Sufficient to Learn High-Performing Algorithms?, arXiv:1908.02894v4, p. 23, Theorem 5.2 (proof pp. 23–24); pseudo-dimension p. 6, eq. (1)
Human review
  • Endorsed by Shuze Chen · Oct 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 4, 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