Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.13 — nearby type vectors at which every agent's utility maximizer is unique

Proved
AlgMechDesign.Local.generic_unique_maximizers

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmic-game-theorymechanism-designp2o-batch-p200bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling

Let (x,p)(x, p)(x,p) be a truthful mechanism for task scheduling. For every positive type vector ttt and every ε>0\varepsilon > 0ε>0 there is a positive type vector t′t't′ with

∥t−t′∥∞=max⁡i,j∣tji−tj′i∣<ε\|t - t'\|_\infty = \max_{i, j} |t^i_j - t'^i_j| < \varepsilon∥t−t′∥∞​=i,jmax​∣tji​−tj′i​∣<ε

such that, for every agent iii, the set xi(t′)x^i(t')xi(t′) is the unique maximizer of iii's utility pi(X,t′−i)−t′i(X)p^i(X, t'^{-i}) - t'^i(X)pi(X,t′−i)−t′i(X) among the sets XXX attainable against t′−it'^{-i}t′−i.

The lemma turns the weak inequalities of Lemma 4.7 into strict ones at a type vector arbitrarily close to any given one; the lower-bound argument for local mechanisms starts from such a type vector.

Formalization Note ∥⋅∥\|\cdot\|∥⋅∥ is Mathlib's norm on Fin n → Fin k → ℝ, the sup norm over agents and tasks. The mechanism is arbitrary: no measurability of the allocation or payment functions is assumed.

Preamble
import Mathlib
import Definitions.Def_AlgMechDesign_Local_Model
import Definitions.Def_AlgMechDesign_Local_Prices
Formal statement
namespace AlgMechDesign.Local

/-- Lemma 4.13, p. 180: for a truthful mechanism, every positive type vector `t` and every
`ε > 0` there is a positive type vector `t'` with `‖t − t'‖ < ε` (sup norm) at which, for every
agent `i`, `xⁱ(t')` is the unique maximizer of `i`'s utility among the attainable sets. -/
theorem generic_unique_maximizers {n k : ℕ} (alloc : (Fin n → Fin k → ℝ) → (Fin k → Fin n))
    (pay : (Fin n → Fin k → ℝ) → Fin n → ℝ) (htr : IsTruthful alloc pay)
    (t : Fin n → Fin k → ℝ) (ht : IsType t) (ε : ℝ) (hε : 0 < ε) :
    ∃ t' : Fin n → Fin k → ℝ, IsType t' ∧ ‖t - t'‖ < ε ∧
      ∀ i : Fin n, IsUniqueMaximizer alloc pay t' i := by sorry

end AlgMechDesign.Local
Source
Nisan, Ronen, Algorithmic Mechanism Design, Games Econ. Behav. 35, 2001, p. 180, Lemma 4.13
Human review
  • Endorsed by Shuze Chen · Oct 1, 2026

    Confirmed by the moderator at approval.

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