Theorem B.3 — discrete convex order iff equal means and stop-loss dominance
OpenSampleCRS.AlmostGreedy.Supplement.theorem_b_3contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
For arbitrary natural-number-supported finite-mean laws of , let and . The following equivalence holds:
The left side tests every discrete convex real function whose expectations under both laws are finite, exactly as Definition B.3. Equality of means is part of the conclusion of the equivalence. This characterizes the discrete convex order without assuming independence or a shared underlying space.
Differences from the source:
- encoding: arbitrary N-supported random variables with finite means → their probability laws NatLaw on N; reason: pushforward laws preserve every tested expectation and require no common realization
Preamble
import Mathlib import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_discreteOrder
Formal statement
namespace SampleCRS.AlmostGreedy.Supplement
/-- Theorem B.3, p.39. discrete convex order iff equal means and stop-loss dominance. -/
theorem theorem_b_3 (P Q : NatLaw) :
ConvexDominates P Q ↔ mean P - mean Q = 0 ∧ ∀ j : ℕ, 0 ≤ stopDifference P Q j := by sorry
end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Theorem B.3, p. 39