q-partitioning valuations , capped valuations , the guarantee and the grouping bound
DefinitionSubadditiveMMS580_Amplification_Supplement_PartitioningGoods form a finite set ; a valuation is a set function .
- -partitioning valuations (Definition 2.1). Let and . A valuation satisfies the conditions on the ground set if , whenever , and for every and every ordered partition of into nonempty groups there are supporting prices with
The prices may depend on and on the partition. The class consists of the valuations satisfying these conditions on . 2. The capped valuation (§4.1): for , . 3. The guarantee function of equation (1):
Adjacent branches agree at . 4. The grouping bound of equation (8) and its crossing points (Lemma B.1): for and real,
where .
These objects state Theorem 1.2 and its supporting results in §4 and Appendix B: is the valuation class of the theorem, its guarantee, and , the guarantee from groups of agents.
Formalization Note is defined through a ground-set-relative predicate so that restriction to a subset of goods (Lemma 4.1) is the same predicate with ground set . Partitions are indexed by . In the formula for the branches are taken on the half-open intervals , , , ; only arguments are ever used. Normalization and monotonicity on all of are the published predicates MultiAllocToAlloc.Subadditive.IsNormalized and IsMonotone.
import Mathlib
import Definitions.Def_MultiAllocToAlloc_Subadditive_Valuation
/-!
# q-partitioning valuations, capped valuations, the guarantee `ρ` and the grouping bound `F_d`
Bo Li, Ankang Sun, *Toward Constant-Factor Maximin Share Guarantees for Subadditive
Valuations*, STOC 2027 submission #580 (October 2026): Definition 2.1 p. 9 (the class `Q_q`),
eq. (1) p. 3 (`ρ`), §4.1 p. 21 (capped valuation `v^C`), eq. (8) p. 24 and Lemma B.1 p. 42
(`F_d(x)`, `x_d`).
Conventions. Goods are `Fin m`; a valuation is a real set function `Finset (Fin m) → ℝ`;
normalization and monotonicity are the published predicates
`MultiAllocToAlloc.Subadditive.IsNormalized` / `IsMonotone`.
-/
set_option autoImplicit false
namespace SubadditiveMMS580.Amplification.Supplement
open MultiAllocToAlloc.Subadditive
/-- Definition 2.1 (p. 9) relative to a ground set `R ⊆ M`: `v` is normalized, monotone on the
subsets of `R`, and for every `S ⊆ R` and every ordered partition `(C_1, …, C_t)` of `S` into
`1 ≤ t ≤ q` nonempty groups there are supporting prices `w_1, …, w_t ≥ 0` with
`∑_j w_j = v(S)` and `∑_{j ∈ J} w_j ≤ v(⋃_{j ∈ J} C_j)` for every `J ⊆ [t]`. -/
def IsQPartitioningOn {m : ℕ} (q : ℕ) (R : Finset (Fin m)) (v : Finset (Fin m) → ℝ) : Prop :=
v ∅ = 0 ∧
(∀ S T : Finset (Fin m), S ⊆ T → T ⊆ R → v S ≤ v T) ∧
∀ S : Finset (Fin m), S ⊆ R → ∀ t : ℕ, 1 ≤ t → t ≤ q → ∀ C : Fin t → Finset (Fin m),
(∀ j, (C j).Nonempty) → (∀ j k, j ≠ k → Disjoint (C j) (C k)) →
Finset.univ.biUnion C = S →
∃ w : Fin t → ℝ, (∀ j, 0 ≤ w j) ∧ ∑ j, w j = v S ∧
∀ J : Finset (Fin t), ∑ j ∈ J, w j ≤ v (J.biUnion C)
/-- Definition 2.1 (p. 9): the class `Q_q` of `q`-partitioning valuations on all goods `M`. -/
def IsQPartitioning {m : ℕ} (q : ℕ) (v : Finset (Fin m) → ℝ) : Prop :=
IsQPartitioningOn q Finset.univ v
/-- §4.1 (p. 21): the capped valuation `v^C(S) = min {v(S), C}`. -/
noncomputable def capped {m : ℕ} (v : Finset (Fin m) → ℝ) (C : ℝ) : Finset (Fin m) → ℝ :=
fun S => min (v S) C
/-- Eq. (1) (p. 3): `ρ(c) = c/(11 − 5c)` for `0 < c ≤ 1`, `1/6` for `1 ≤ c ≤ 6/5`,
`2(c − 1)/(7c − 6)` for `6/5 ≤ c ≤ 2`, and `1/4` for `c ≥ 2` (adjacent branches agree at
`1, 6/5, 2`). Only arguments `c > 0` are used. -/
noncomputable def rho (c : ℝ) : ℝ :=
if c ≤ 1 then c / (11 - 5 * c)
else if c ≤ 6 / 5 then 1 / 6
else if c ≤ 2 then 2 * (c - 1) / (7 * c - 6)
else 1 / 4
/-- Eq. (8) (p. 24) and Lemma B.1 (p. 42): `F_d(x) = (1 − x/d)^+ / (2d − 1)`. -/
noncomputable def Fd (d x : ℝ) : ℝ := max (1 - x / d) 0 / (2 * d - 1)
/-- Lemma B.1 (p. 42): the crossing point `x_d = 4d² / (6d − 1)`. -/
noncomputable def xd (d : ℝ) : ℝ := 4 * d ^ 2 / (6 * d - 1)
end SubadditiveMMS580.Amplification.Supplement