Theorem 10 — f + p·x (resp. f − w·x, w ≥ 0, f nondecreasing) is quasisupermodular with single crossing for all prices iff f is supermodular
ProvedMonotoneCompStatics.LinearPerturb.theorem10Let and , . Order componentwise and by the product order; joins and meets are componentwise maxima and minima. Write . Say that is supermodular if
- is quasisupermodular in and has the single crossing property in for all if and only if is supermodular.
- If is nondecreasing in (for every fixed ), then is quasisupermodular in and has the single crossing property in for all nonnegative if and only if is supermodular.
In the economic reading, is a vector of activity levels, a parameter, a vector of prices (or a vector of nonnegative input costs) that enter linearly. Supermodularity is never necessary for the argmax to be monotone, but by this theorem it is exactly the condition under which the ordinal conditions of the Monotonicity Theorem survive every such linear price term.
Formalization Note is curried, f : (Fin n → ℝ) → ℝ → ℝ; is Fin n → ℝ with Mathlib's pointwise order, is p ⬝ᵥ x. " is supermodular" is read jointly in on the product lattice (the published SupermodularOn with Set.univ), as the paper's proof confirms. "Quasisupermodular in " means for every fixed . "Nondecreasing in " is Monotone (fun x => f x t) for every , a hypothesis of the second equivalence only; "nonnegative " is 0 ≤ w componentwise. The second statement uses with , not .
import Mathlib import Definitions.Def_Supermodularity_Monotonicity_SupermodularOn import Definitions.Def_MonotoneCompStatics_Monotonicity_QuasiSupermodularOn import Definitions.Def_MonotoneCompStatics_Monotonicity_SingleCrossing
namespace MonotoneCompStatics.LinearPerturb
/-- Milgrom and Shannon (1994), p. 166, Theorem 10. Let `f : ℝⁿ × ℝ → ℝ` (curried).
(1) `f(x, t) + p · x` is quasisupermodular in `x` and has the single crossing property in
`(x; t)` for all `p ∈ ℝⁿ` iff `f` is supermodular (jointly in `(x, t)` on `ℝⁿ × ℝ`).
(2) If `f` is nondecreasing in `x`, then `f(x, t) − w · x` is quasisupermodular in `x` and has the
single crossing property in `(x; t)` for all nonnegative `w ∈ ℝⁿ` iff `f` is supermodular. -/
theorem theorem10 {n : ℕ} (f : (Fin n → ℝ) → ℝ → ℝ) :
((∀ p : Fin n → ℝ, (∀ t, MonotoneCompStatics.Monotonicity.QuasiSupermodularOn (fun x => f x t + p ⬝ᵥ x) Set.univ) ∧
MonotoneCompStatics.Monotonicity.SingleCrossing (fun x t => f x t + p ⬝ᵥ x)) ↔
Supermodularity.Monotonicity.SupermodularOn
(fun z : (Fin n → ℝ) × ℝ => f z.1 z.2) Set.univ) ∧
((∀ t, Monotone (fun x => f x t)) →
((∀ w : Fin n → ℝ, 0 ≤ w →
(∀ t, MonotoneCompStatics.Monotonicity.QuasiSupermodularOn (fun x => f x t - w ⬝ᵥ x) Set.univ) ∧
MonotoneCompStatics.Monotonicity.SingleCrossing (fun x t => f x t - w ⬝ᵥ x)) ↔
Supermodularity.Monotonicity.SupermodularOn
(fun z : (Fin n → ℝ) × ℝ => f z.1 z.2) Set.univ)) := by sorry
end MonotoneCompStatics.LinearPerturb
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.