Proposition 5, p. 13 — IC iff the buyer payoff b is convex with q(x) a subgradient at x
ProvedMultiItemRev.BundlingOpt.proposition_5convexityincentive-compatibilitymechanism-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a mechanism for goods with buyer payoff on . Then is incentive compatible if and only if is a convex function on and, for every , the vector is a subgradient of at :
This is Rochet's characterization of incentive compatibility; it lets revenue be expressed through the convex function alone.
Formalization Note Convexity on the cone is stated directly: for all and .
Preamble
import Mathlib import Definitions.Def_MultiItemRev_BundlingOpt_Model open MeasureTheory open scoped NNReal ENNReal
Formal statement
namespace MultiItemRev.BundlingOpt
theorem proposition_5 {ι : Type*} [Fintype ι] [Nonempty ι] (M : Mechanism ι) :
IsIC M ↔
((∀ (x y : ι → ℝ≥0) (t : ℝ≥0), t ≤ 1 →
buyerPayoff M (t • x + (1 - t) • y) ≤
(t : ℝ) * buyerPayoff M x + (1 - (t : ℝ)) * buyerPayoff M y) ∧
∀ x x' : ι → ℝ≥0,
∑ i, M.q x i * ((x' i : ℝ) - (x i : ℝ)) ≤ buyerPayoff M x' - buyerPayoff M x) := by sorry
end MultiItemRev.BundlingOpt
Source
Hart and Nisan, Approximate Revenue Maximization with Multiple Items, arXiv:1204.1846v3, p. 13, Proposition 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.