Proposition 5.7 -- Bikhchandani et al.: weak monotonicity suffices on rich domains (finite A)
ProvedMechanismDesign.IncentiveCompat.rich_weaklyMonotone_implementableSuppose that the set of alternatives is finite and let be a reflexive and transitive, possibly incomplete, relation on . Assume that
- the type set is rich with respect to : for every that represents () there is a type with for all ; and
- the type set is consistent with : for every type , the function represents .
Then every weakly monotone decision rule is implementable: some gives
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 , the total order , and types with ; the rule giving to , to and to every other type is weakly monotone but not implementable. Types need not be identified with their utility vectors (two types may share one).
import Mathlib import Definitions.Def_MechanismDesign_IncentiveCompat_Model
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.