Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

q-partitioning valuations Qq\mathcal Q_qQq​, capped valuations vCv^CvC, the guarantee ρ(c)\rho(c)ρ(c) and the grouping bound Fd(x)F_d(x)Fd​(x)

Definition
SubadditiveMMS580_Amplification_Supplement_Partitioning

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

fair-divisionmaximin-sharep2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1q-partitioning

Goods form a finite set M={0,…,m−1}M=\{0,\dots,m-1\}M={0,…,m−1}; a valuation is a set function v:2M→Rv:2^M\to\mathbb Rv:2M→R.

  1. qqq-partitioning valuations (Definition 2.1). Let q≥2q\ge2q≥2 and R⊆MR\subseteq MR⊆M. A valuation vvv satisfies the Qq\mathcal Q_qQq​ conditions on the ground set RRR if v(∅)=0v(\emptyset)=0v(∅)=0, v(S)≤v(T)v(S)\le v(T)v(S)≤v(T) whenever S⊆T⊆RS\subseteq T\subseteq RS⊆T⊆R, and for every S⊆RS\subseteq RS⊆R and every ordered partition (C1,…,Ct)(C_1,\dots,C_t)(C1​,…,Ct​) of SSS into 1≤t≤q1\le t\le q1≤t≤q nonempty groups there are supporting prices w1,…,wt≥0w_1,\dots,w_t\ge0w1​,…,wt​≥0 with
∑j=1twj=v(S),∑j∈Jwj≤v(⋃j∈JCj)for every J⊆[t].\sum_{j=1}^t w_j=v(S),\qquad \sum_{j\in J}w_j\le v\Big(\bigcup_{j\in J}C_j\Big)\quad\text{for every }J\subseteq[t].j=1∑t​wj​=v(S),j∈J∑​wj​≤v(j∈J⋃​Cj​)for every J⊆[t].

The prices may depend on SSS and on the partition. The class Qq\mathcal Q_qQq​ consists of the valuations satisfying these conditions on R=MR=MR=M. 2. The capped valuation (§4.1): for C≥0C\ge0C≥0, vC(S)=min⁡{v(S),C}v^C(S)=\min\{v(S),C\}vC(S)=min{v(S),C}. 3. The guarantee function of equation (1):

ρ(c)={c11−5c,0<c≤1,16,1≤c≤65,2(c−1)7c−6,65≤c≤2,14,c≥2.\rho(c)=\begin{cases}\dfrac{c}{11-5c},&0<c\le1,\\[4pt] \dfrac16,&1\le c\le\frac65,\\[4pt] \dfrac{2(c-1)}{7c-6},&\frac65\le c\le2,\\[4pt] \dfrac14,&c\ge2.\end{cases}ρ(c)=⎩⎨⎧​11−5cc​,61​,7c−62(c−1)​,41​,​0<c≤1,1≤c≤56​,56​≤c≤2,c≥2.​

Adjacent branches agree at c=1, 6/5, 2c=1,\ 6/5,\ 2c=1, 6/5, 2. 4. The grouping bound of equation (8) and its crossing points (Lemma B.1): for d>0d>0d>0 and xxx real,

Fd(x)=(1−x/d)+2d−1,xd=4d26d−1,F_d(x)=\frac{(1-x/d)^+}{2d-1},\qquad x_d=\frac{4d^2}{6d-1},Fd​(x)=2d−1(1−x/d)+​,xd​=6d−14d2​,

where t+=max⁡{t,0}t^+=\max\{t,0\}t+=max{t,0}.

These objects state Theorem 1.2 and its supporting results in §4 and Appendix B: Qq\mathcal Q_qQq​ is the valuation class of the theorem, ρ\rhoρ its guarantee, and FdF_dFd​, xdx_dxd​ the guarantee from ddd groups of agents.

Formalization Note Qq\mathcal Q_qQq​ is defined through a ground-set-relative predicate so that restriction to a subset RRR of goods (Lemma 4.1) is the same predicate with ground set RRR. Partitions are indexed by Fin t\mathrm{Fin}\,tFint. In the formula for ρ\rhoρ the branches are taken on the half-open intervals (−∞,1](-\infty,1](−∞,1], (1,6/5](1,6/5](1,6/5], (6/5,2](6/5,2](6/5,2], (2,∞)(2,\infty)(2,∞); only arguments c>0c>0c>0 are ever used. Normalization and monotonicity on all of MMM are the published predicates MultiAllocToAlloc.Subadditive.IsNormalized and IsMonotone.

Definition code
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
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, Definition 2.1 p. 9; eq. (1) p. 3; §4.1 p. 21 (capped valuation); eq. (8) p. 24 and Lemma B.1 p. 42 (F_d, x_d)

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