Proposition 5.3 -- with lottery outcomes, q is implementable iff q(θ) is a subgradient of a convex U
ProvedMechanismDesign.IncentiveCompat.lottery_subgradientLet be a finite set of outcomes and let the alternatives be all lotteries . Let the type set be a nonempty convex set of vectors of Bernoulli utilities, and let the utility of lottery for type be the expected utility . Then a decision rule is implementable if and only if there is a function , convex on , such that for every the vector is a subgradient of at :
This is the lottery case of Rochet's theorem in the language of convex analysis.
Formalization Note The page writes ""; the intended domain is the type set . In Lean U is a function on of which only the values on matter (convexity and the subgradient inequality are both relative to ). Θ is the subtype of a set S; nonemptiness is the standing assumption of §5.2.
import Mathlib import Definitions.Def_MechanismDesign_IncentiveCompat_Model
namespace MechanismDesign.IncentiveCompat
/-- Proposition 5.3 (p.103). Alternatives are the lotteries `Δ(Ω)` over a finite outcome set
`Ω`; types are the vectors `θ ∈ S ⊆ ℝ^Ω` of Bernoulli utilities, `S` nonempty and convex; the
utility of lottery `p` for type `θ` is `p · θ`. Then `q` is implementable if and only if there
is a function `U`, convex on `S`, such that `q(θ)` is a subgradient of `U` at `θ` (relative
to `S`) for every `θ ∈ S`. -/
theorem lottery_subgradient {Ω : Type*} [Fintype Ω] (S : Set (Ω → ℝ)) (hS : Convex ℝ S)
(hSne : S.Nonempty) (q : S → stdSimplex ℝ Ω) :
Implementable (fun (p : stdSimplex ℝ Ω) (θ : S) => lotteryUtility p (θ : Ω → ℝ)) q ↔
∃ U : (Ω → ℝ) → ℝ, ConvexOn ℝ S U ∧
∀ θ : S, IsSubgradientOn S U (θ : Ω → ℝ) ((q θ : stdSimplex ℝ Ω) : Ω → ℝ) := by sorry
end MechanismDesign.IncentiveCompat
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.