Lemma 4.1 — is closed under restriction, nonnegative scaling and capping
ProvedSubadditiveMMS580.Amplification.Supplement.lemma_4_1fair-divisionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1q-partitioning
Let and let be a -partitioning valuation on the goods . Then:
- (restriction) for every subset , satisfies the conditions with ground set , i.e. the restriction of to is -partitioning;
- (scaling) for every , the valuation belongs to ;
- (capping) for every , the capped valuation
belongs to .
Capping is what makes capped social welfare usable as a potential in the grouping construction of Proposition 4.3.
Differences from the source:
- encoding: partitions into nonempty groups (Definition 2.1) → 1 ≤ t ≤ q and C : Fin t → Finset (Fin m) with nonempty, pairwise disjoint members whose union is S; reason: the same ordered partitions
- encoding: valuations , normalized and monotone → real set functions on Finset (Fin m) with the published IsNormalized and IsMonotone predicates; reason: normalization and monotonicity give nonnegativity, so the instances are the same
- encoding: the restriction of v to a subset R of goods (a valuation on 2^R) → IsQPartitioningOn q R v: normalization, monotonicity on subsets of R, and supporting prices for partitions of subsets of R; reason: the restriction takes the same values on subsets of R, so these are exactly its Q_q conditions
Preamble
import Mathlib import Definitions.Def_SubadditiveMMS580_Amplification_Supplement_Partitioning import Definitions.Def_MultiAllocToAlloc_Subadditive_Valuation import Definitions.Def_MultiAllocToAlloc_Subadditive_Allocation import Definitions.Def_LittleCharity_MMS_Setting open MultiAllocToAlloc.Subadditive
Formal statement
namespace SubadditiveMMS580.Amplification.Supplement
/-- Lemma 4.1 (Li–Sun, STOC 2027 submission #580, p. 21): for `q ≥ 2` and `v ∈ Q_q`,
(a) for every `R ⊆ M` the valuation satisfies the `Q_q` conditions on the ground set `R`
(restriction), (b) `c · v ∈ Q_q` for every `c ≥ 0` (scaling), and (c) the capped valuation
`v^C(S) = min {v(S), C}` belongs to `Q_q` for every `C ≥ 0` (capping). -/
theorem lemma_4_1 {m : ℕ} (q : ℕ) (hq : 2 ≤ q) (v : Finset (Fin m) → ℝ)
(hv : IsQPartitioning q v) :
(∀ R : Finset (Fin m), IsQPartitioningOn q R v) ∧
(∀ c : ℝ, 0 ≤ c → IsQPartitioning q (fun S => c * v S)) ∧
(∀ C : ℝ, 0 ≤ C → IsQPartitioning q (capped v C)) := by sorry
end SubadditiveMMS580.Amplification.Supplement
Source
Bo Li, Ankang Sun, Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations, STOC 2027 submission #580 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/580.pdf, sha256 7de124b5706e9e49301a281a1eb418a8ae32d04bf4cf0941b969cc3cde85e485, Lemma 4.1, p. 21 (PDF p. 21)