Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
MonotoneCompStatics.LinearPerturb.theorem10

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

comparative-staticslattice-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quasisupermodularitysingle-crossingsupermodularity

Let n≥0n \ge 0n≥0 and f:Rn×R→Rf : \mathbb{R}^n \times \mathbb{R} \to \mathbb{R}f:Rn×R→R, (x,t)↦f(x,t)(x, t) \mapsto f(x, t)(x,t)↦f(x,t). Order Rn\mathbb{R}^nRn componentwise and Rn×R\mathbb{R}^n \times \mathbb{R}Rn×R by the product order; joins ∨\vee∨ and meets ∧\wedge∧ are componentwise maxima and minima. Write p⋅x=∑ipixip \cdot x = \sum_i p_i x_ip⋅x=∑i​pi​xi​. Say that fff is supermodular if

f(z)+f(z′)≤f(z∨z′)+f(z∧z′)for all z,z′∈Rn×R.f(z) + f(z') \le f(z \vee z') + f(z \wedge z') \qquad \text{for all } z, z' \in \mathbb{R}^n \times \mathbb{R}.f(z)+f(z′)≤f(z∨z′)+f(z∧z′)for all z,z′∈Rn×R.
  1. f(x,t)+p⋅xf(x, t) + p \cdot xf(x,t)+p⋅x is quasisupermodular in xxx and has the single crossing property in (x;t)(x; t)(x;t) for all p∈Rnp \in \mathbb{R}^np∈Rn if and only if fff is supermodular.
  2. If fff is nondecreasing in xxx (for every fixed ttt), then f(x,t)−w⋅xf(x, t) - w \cdot xf(x,t)−w⋅x is quasisupermodular in xxx and has the single crossing property in (x;t)(x; t)(x;t) for all nonnegative w∈Rnw \in \mathbb{R}^nw∈Rn if and only if fff is supermodular.

In the economic reading, xxx is a vector of activity levels, ttt a parameter, ppp a vector of prices (or www 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 fff is curried, f : (Fin n → ℝ) → ℝ → ℝ; Rn\mathbb{R}^nRn is Fin n → ℝ with Mathlib's pointwise order, p⋅xp \cdot xp⋅x is p ⬝ᵥ x. "fff is supermodular" is read jointly in (x,t)(x, t)(x,t) on the product lattice (the published SupermodularOn with Set.univ), as the paper's proof confirms. "Quasisupermodular in xxx" means for every fixed ttt. "Nondecreasing in xxx" is Monotone (fun x => f x t) for every ttt, a hypothesis of the second equivalence only; "nonnegative www" is 0 ≤ w componentwise. The second statement uses −w⋅x- w\cdot x−w⋅x with w≥0w \ge 0w≥0, not +p⋅x+p\cdot x+p⋅x.

Preamble
import Mathlib
import Definitions.Def_Supermodularity_Monotonicity_SupermodularOn
import Definitions.Def_MonotoneCompStatics_Monotonicity_QuasiSupermodularOn
import Definitions.Def_MonotoneCompStatics_Monotonicity_SingleCrossing
Formal statement
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
Source
Milgrom and Shannon, Monotone Comparative Statics, Econometrica 62 (1994), p. 166 (PDF p. 11), Theorem 10
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me