Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The constructive class H2\mathcal H_2H2​ and rational sources

Definition
SupplyRevenue_Supplement_Classes

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

buy-manyitem-pricingp2o-gran-per-chapterp2o-plan-paperp2o-v1posted-pricingrevenue-maximizationxos-valuations

Let M=[m]M=[m]M=[m] be the items. A value vvv on bundles has at most two nonnegative additive clauses if there are a,c∈R≥0Ma,c\in\mathbb R_{\ge 0}^Ma,c∈R≥0M​ with

v(T)=max⁡{∑j∈Taj, ∑j∈Tcj}for all T⊆Mv(T)=\max\Bigl\{\sum_{j\in T}a_j,\ \sum_{j\in T}c_j\Bigr\}\qquad\text{for all }T\subseteq Mv(T)=max{j∈T∑​aj​, j∈T∑​cj​}for all T⊆M

(a=ca=ca=c gives a single clause). The value is additive on a block B⊆MB\subseteq MB⊆M if v(T)=∑j∈Tv({j})v(T)=\sum_{j\in T}v(\{j\})v(T)=∑j∈T​v({j}) for every T⊆BT\subseteq BT⊆B.

A buyer belongs to the constructive class H2\mathcal H_2H2​ if there is one partition M=B1⊔B2M=B_1\sqcup B_2M=B1​⊔B2​, either block possibly empty, fixed for the buyer and shared by all of its supported types (types of positive mass), such that every supported type has at most two nonnegative additive clauses and is additive on B1B_1B1​ and on B2B_2B2​. An instance is in H2\mathcal H_2H2​ when every buyer is, each buyer with its own partition. The partition is part of the promise only; it is never given to an algorithm.

A rational source is an item-pricing source whose every mixture weight, and every price of an item in the assortment of every atom, is a rational number.

These are the promises of the H2\mathcal H_2H2​ rows of Theorem 1.2 and of its sampled interface.

Formalization Note B2B_2B2​ is the complement of B1B_1B1​. Values are already normalized and monotone in the base model. Prices of items outside an assortment are never read and are unrestricted. The helper toRat x returns the rational equal to a real xxx when one exists (else 000); it is exact on rational sources and is how sampled offers are reported as rational data. Subadditivity is not redefined here: Theorem 1.2 uses the published SubmodOrder.Subadditive.

Definition code
import Mathlib
import Definitions.Def_SupplyRevenue_Classes
import Definitions.Def_SupplyRevenue_CapRev

namespace SupplyRevenue
namespace Supplement

/-!
# The constructive class `𝓗₂` and rational sources

Mahboub, Rahgoshay, *Supply-Sensitive Revenue Recovery under Unknown Buyer Order* (manuscript, sha256 c04de641…),
p.3: "The constructive class H₂ has at most two nonnegative
additive clauses per type. For each buyer there exists an unknown fixed partition M = B_{i1} ⊔ B_{i2}, allowing an empty
block, such that every supported type satisfies v_i(T) = Σ_{j∈T} v_i({j}) on either block. The partition is
buyer-specific and persistent across types, not supplied"; p.3: "a rational source … supplied".

**Formalization Note** Subadditivity (p.2) is not defined here: the theorems use the published
`SubmodOrder.Subadditive`, the same predicate `v(S ∪ T) ≤ v(S) + v(T)`. Values are already normalized and monotone (`SupplyRevenue.Buyer`). Class membership of a buyer
concerns supported types only (mass `> 0`), as in the published `Buyer.InClass`. In `𝓗₂` the block `B₁` is chosen once
per buyer, before the type, and `B₂` is its complement; either block may be empty. "On either block" is read as: on each
of the two blocks the value is additive over subsets of that block. A two-clause value is `max` of two nonnegative
additive functions; equal clauses give a single clause. A rational source has rational weights and rational prices on
every assortment item; the prices of items outside an assortment are never read and are unrestricted. `toRat x` is the
rational equal to `x` when there is one (and `0` otherwise); it is exact on rational sources.
-/

/-- A value with at most two nonnegative additive clauses: `v(T) = max{a(T), c(T)}` with `a, c ≥ 0` (p.3). -/
def IsTwoClause {m : ℕ} (v : Finset (Fin m) → ℝ) : Prop :=
  ∃ a c : Fin m → ℝ, (∀ j, 0 ≤ a j) ∧ (∀ j, 0 ≤ c j) ∧
    ∀ T : Finset (Fin m), v T = max (∑ j ∈ T, a j) (∑ j ∈ T, c j)

/-- `v` is additive on the block `B`: `v(T) = Σ_{j∈T} v({j})` for every `T ⊆ B` (p.3). -/
def AdditiveOn {m : ℕ} (v : Finset (Fin m) → ℝ) (B : Finset (Fin m)) : Prop :=
  ∀ T ⊆ B, v T = ∑ j ∈ T, v {j}

/-- A buyer is in `𝓗₂` (p.3): one partition `M = B₁ ⊔ B₂` (`B₂ = B₁ᶜ`, either block possibly empty), fixed for the
buyer and shared by all its supported types, such that every supported type has at most two nonnegative additive clauses
and is additive on each block. -/
def BuyerInH2 {m : ℕ} (b : Buyer m) : Prop :=
  ∃ B₁ : Finset (Fin m), ∀ θ, 0 < b.mass θ →
    IsTwoClause (b.val θ) ∧ AdditiveOn (b.val θ) B₁ ∧ AdditiveOn (b.val θ) B₁ᶜ

/-- Every buyer of the instance is in `𝓗₂` (each with its own partition). -/
def InstanceInH2 {n m : ℕ} (D : Instance n m) : Prop :=
  ∀ i, BuyerInH2 (D i)

/-- A rational source (p.3): every weight, and every price of an item in the assortment of every atom, is rational. -/
def IsRationalSource {n m : ℕ} (σ : Source n m) : Prop :=
  ∀ i, (∀ a, ∃ q : ℚ, (σ i).weight a = q) ∧
    ∀ a, ∀ j ∈ ((σ i).atom a).assort, ∃ q : ℚ, ((σ i).atom a).price j = q

open Classical in
/-- The rational equal to a real number, when there is one; `0` otherwise. -/
noncomputable def toRat (x : ℝ) : ℚ :=
  if h : ∃ q : ℚ, (q : ℝ) = x then h.choose else 0

theorem toRat_cast (q : ℚ) : toRat (q : ℝ) = q := by
  have h : ∃ q' : ℚ, (q' : ℝ) = q := ⟨q, rfl⟩
  classical
  unfold toRat
  rw [dif_pos h]
  exact_mod_cast h.choose_spec

end Supplement
end SupplyRevenue
Source
Mahboub, Rahgoshay, Supply-Sensitive Revenue Recovery under Unknown Buyer Order (manuscript, sha256 c04de641…), §1.1, p.3 (class H₂; sampled interface: rational source)

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