Proposition 8.5 -- every monotone direct mechanism with full range over at least three alternatives is dictatorial
ProvedMechanismDesign.SocialChoice.monotone_dictatorialLet be a finite set of agents and a finite set of alternatives with at least three elements. Let be a direct mechanism on profiles of linear orders whose range is . If is monotone, i.e.
then is dictatorial: there is an agent such that for every profile and every .
This is the Muller–Satterthwaite theorem, the core of the book's proof of the Gibbard–Satterthwaite theorem (following Reny, 2001). Since dominant strategy incentive compatibility implies monotonicity (Proposition 8.2), it strengthens the necessity half of Proposition 8.1.
Formalization Note Monotonicity is the book's Definition 8.4 (arbitrary profile changes, per-agent lower-contour inclusion). The dictator is fixed before the profile is quantified. "The range of is " is surjectivity of on all profiles of linear orders.
import Mathlib import Definitions.Def_MechanismDesign_SocialChoice_Model
namespace MechanismDesign.SocialChoice
/-- **Proposition 8.5** (Börgers, p.146; Muller–Satterthwaite, in Reny's 2001 proof): suppose
that `A` has at least three elements and that the range of `f` is `A`. If `f` is monotone,
then it is dictatorial. -/
theorem monotone_dictatorial {ι A : Type*} [Fintype ι] [Fintype A]
(hA : 3 ≤ Fintype.card A) (f : DirectMechanism ι A) (hrange : Function.Surjective f)
(hf : IsMonotone f) : IsDictatorial f := by sorry
end MechanismDesign.SocialChoice
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.