Proposition 5.2 -- Rochet's theorem: a decision rule is implementable iff it is cyclically monotone
ProvedMechanismDesign.IncentiveCompat.rochetcyclical-monotonicityincentive-compatibilitymechanism-designp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be an arbitrary set of alternatives, an arbitrary nonempty set of types and an arbitrary utility function. A decision rule is implementable (there is a transfer rule with for all ) if and only if it is cyclically monotone: for every finite sequence of types with ,
This is Rochet's (1987) characterization of implementability. No finiteness, topology or boundedness is assumed on , or .
Formalization Note Both directions are stated. A sequence of length is a map Fin (m+1) → Θ whose first and last entries coincide; Nonempty Θ is the standing assumption of §5.2.
Preamble
import Mathlib import Definitions.Def_MechanismDesign_IncentiveCompat_Model
Formal statement
namespace MechanismDesign.IncentiveCompat
/-- Proposition 5.2 (Rochet 1987, p.100): a decision rule is implementable if and only if it is
cyclically monotone. No structure on the set `A` of alternatives or the nonempty set `Θ` of types
is assumed. -/
theorem rochet {A Θ : Type*} [Nonempty Θ] (u : A → Θ → ℝ) (q : Θ → A) :
Implementable u q ↔ CyclicallyMonotone 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.100, Proposition 5.2 (Rochet 1987)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.