Theorem 5.2 (corrected) — neutral affine maximizers:
ProvedBalcanDDA.NAM.theorem5_2_pdim_lower_boundConsider agents and alternatives, and let be the class of social-welfare utilities of neutral affine maximizers, where is a maximizer over of , chosen by an arbitrary but fixed tie-breaking rule. Then
i.e. there are valuation profiles and witnesses such that for every some satisfies exactly when .
Combined with the upper bound 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):
- The paper states ; its proof assumes even "without loss of generality" and shatters profiles. The printed bound fails at : the only admissible parameter is , so consists of a single function and . The statement here is , which equals for even .
- The printed set-builder reads ""; Lemma 5.1 one paragraph earlier writes (some agent has weight zero), which is the condition used here.
- The hypotheses and are explicit: for no parameter is admissible and ; for , is a single function. The paper's proof takes ; the theorem is stated for every .
Formalization Note "" is written as the existence of an -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 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, . 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.
import Mathlib import Definitions.Def_FoundationsML_Regression_Shatters import Definitions.Def_BalcanDDA_NAM_Model
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.