Proposition 8.2 -- dominant strategy incentive compatibility implies monotonicity
ProvedMechanismDesign.SocialChoice.dsic_monotonemechanism-designp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1social-choicestrategy-proofness
Let be a finite set of agents, a finite set of alternatives, and a direct mechanism on profiles of linear orders. If is dominant strategy incentive-compatible, that is, for all , , , then is monotone in the sense of Maskin:
This is the first step of the book's proof of the Gibbard–Satterthwaite theorem: it reduces strategy-proofness to the weaker, purely ordinal condition of monotonicity.
Formalization Note Monotonicity here is the book's Definition 8.4, which compares arbitrary profiles and (all agents may change at once); it is not the one-agent deviation property of other texts.
Preamble
import Mathlib import Definitions.Def_MechanismDesign_SocialChoice_Model
Formal statement
namespace MechanismDesign.SocialChoice
/-- **Proposition 8.2** (Börgers, p.144): if `f` is dominant strategy incentive-compatible, then
it is monotone. -/
theorem dsic_monotone {ι A : Type*} [Fintype ι] [DecidableEq ι] [Fintype A]
(f : DirectMechanism ι A) (hf : IsDSIC f) : IsMonotone f := by sorry
end MechanismDesign.SocialChoice
Source
Börgers, An Introduction to the Theory of Mechanism Design, Oxford University Press 2015, DOI 10.1093/acprof:oso/9780199734023.001.0001, p.144, Proposition 8.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.