Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 5.7 -- Bikhchandani et al.: weak monotonicity suffices on rich domains (finite A)

Proved
MechanismDesign.IncentiveCompat.rich_weaklyMonotone_implementable

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

incentive-compatibilitymechanism-designp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1rich-domainweak-monotonicity

Suppose that the set AAA of alternatives is finite and let RRR be a reflexive and transitive, possibly incomplete, relation on AAA. Assume that

  1. the type set is rich with respect to RRR: for every v:A→Rv : A \to \mathbb Rv:A→R that represents RRR (aRb⇒v(a)≥v(b)aRb \Rightarrow v(a) \ge v(b)aRb⇒v(a)≥v(b)) there is a type θ\thetaθ with u(a,θ)=v(a)u(a,\theta) = v(a)u(a,θ)=v(a) for all a∈Aa \in Aa∈A; and
  2. the type set is consistent with RRR: for every type θ\thetaθ, the function u(⋅,θ)u(\cdot,\theta)u(⋅,θ) represents RRR.

Then every weakly monotone decision rule qqq is implementable: some t:Θ→Rt : \Theta \to \mathbb Rt:Θ→R gives

u(q(θ),θ)−t(θ)≥u(q(θ′),θ)−t(θ′)for all θ,θ′.u(q(\theta),\theta) - t(\theta) \ge u(q(\theta'),\theta) - t(\theta') \qquad \text{for all } \theta,\theta'.u(q(θ),θ)−t(θ)≥u(q(θ′),θ)−t(θ′)for all θ,θ′.

With Proposition 5.1, weak monotonicity then characterizes implementability on such domains; this is Theorem 1 of Bikhchandani, Chatterji, Lavi, Mu'alem, Nisan and Sen (2006), which covers multi-object auctions with free disposal.

Formalization Note Condition 2 is part of Bikhchandani et al.'s rich-domain assumption (their domain is exactly the set of utility vectors consistent with the order) but is missing from the book's Definition 5.10. Without it the statement is false: take A={a,b,c}A = \{a,b,c\}A={a,b,c}, RRR the total order a⪰b⪰ca \succeq b \succeq ca⪰b⪰c, and types Θ={θ∈R3:θa≥θb≥θc}∪{(0,1,0)}\Theta = \{\theta \in \mathbb R^3 : \theta_a \ge \theta_b \ge \theta_c\} \cup \{(0,1,0)\}Θ={θ∈R3:θa​≥θb​≥θc​}∪{(0,1,0)} with u(x,θ)=θxu(x,\theta) = \theta_xu(x,θ)=θx​; the rule giving ccc to (0,1,0)(0,1,0)(0,1,0), bbb to (0,0,−1)(0,0,-1)(0,0,−1) and aaa to every other type is weakly monotone but not implementable. Types need not be identified with their utility vectors (two types may share one).

Preamble
import Mathlib
import Definitions.Def_MechanismDesign_IncentiveCompat_Model
Formal statement
namespace MechanismDesign.IncentiveCompat

/-- Proposition 5.7 (Bikhchandani et al. 2006, Theorem 1; p.109), in the corrected form: `A` is
finite, `R` is a reflexive and transitive relation on `A`, every `v : A → ℝ` representing `R` is
the utility function of some type (the book's Definition 5.10), and every type's utility function
represents `R` (the consistency of the domain in Bikhchandani et al., which the book's
definition omits and without which the statement is false). Then every weakly monotone decision
rule is implementable. -/
theorem rich_weaklyMonotone_implementable {A Θ : Type*} [Finite A] [Nonempty Θ]
    (u : A → Θ → ℝ) (R : A → A → Prop) (hrefl : ∀ a, R a a)
    (htrans : ∀ a b c, R a b → R b c → R a c) (hrich : IsRichWRT u R)
    (hcons : IsConsistentWRT u R) (q : Θ → A) (hq : WeaklyMonotone u q) :
    Implementable u q := by sorry

end MechanismDesign.IncentiveCompat
Source
Börgers, An Introduction to the Theory of Mechanism Design, Oxford University Press 2015, DOI 10.1093/acprof:oso/9780199734023.001.0001, p.109, Proposition 5.7, Definition 5.10 (p.108); Bikhchandani, Chatterji, Lavi, Mu'alem, Nisan, Sen, Econometrica 74(4) (2006) 1109–1132, §3.1 rich-domain assumption and Theorem 1
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

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