§4, p. 33 (Gibbard) — the relation of a strategy-proof full-range procedure is a strong order, and underlies with PO and IIA
ProvedStrategyProofArrow.Correspondence.gibbard_claimLet , , and let be a strict voting procedure that is strategy-proof and has range . Fix any strong order , and for each strict ballot set let be Gibbard's relation: for ,
where places on top in the order gives them and the other alternatives below in the order of . Then is a strong order for every , so is a strict social welfare function, and
- underlies : for every ;
- satisfies Pareto optimality (PO);
- satisfies independence of irrelevant alternatives (IIA).
The paper cites this from Gibbard's proof of the Gibbard–Satterthwaite theorem and does not prove it; it supplies the existence half of Lemma 8.
Formalization Note The conclusion is stated as the existence of whose relation at is exactly Gibbard's (gibbardRel v Q B, the reflexive closure of ), which also asserts that is a strong order. The hypothesis is the restriction stated by the paper's "first fact" (p. 33), and , are the standing hypotheses of §4. The claim is stated for every choice of , which the paper calls arbitrary.
import Mathlib import Definitions.Def_StrategyProofArrow_Correspondence_Basic
namespace StrategyProofArrow.Correspondence
theorem gibbard_claim {ι A : Type*} [Fintype ι] [Fintype A] [DecidableEq ι] [DecidableEq A]
(hn : 2 ≤ Fintype.card ι) (hm : 3 ≤ Fintype.card A)
(v : StrongProfile ι A → A) (hsp : StrategyProof v) (hrange : Set.range v = Set.univ)
(Q : StrongOrder A) :
∃ μ : StrongProfile ι A → StrongOrder A,
(∀ B x y, (μ B).1.rel x y ↔ gibbardRel v Q B x y) ∧
Underlies μ v ∧ PO μ ∧ IIA μ := by sorry
end StrategyProofArrow.Correspondence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.