Claim 2.4 — Cutoff bound
ProvedFairShareAlmostAll.Slack.Supplement.cutoff_boundanyprice-sharefair-divisionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Work under the standing assumptions of Section 2: agents, an integer , total entitlement , entitlements , a nonempty set of active agents (those with positive APS target ), and goods ordered so that every valuation is nonincreasing. The buckets have prescribed sizes , and the cutoff of an active agent is the first full bucket with , or if there is none. Then every active agent satisfies
with the natural logarithm.
The claim bounds how many buckets lie in an agent's head; it is used in the Markov-inequality step of Proposition 4.1, which conditions each certificate on configurations with small contribution to the jointly controlled sums.
Differences from the source:
- encoding: ranks and buckets as rank intervals → goods
Fin mand the live mission's published bucket, cutoff and active-set definitions; reason: the same objects under zero-based indexing, reused unchanged from the live mission
Preamble
import Mathlib import Definitions.Def_AnyPriceShare_Bidding_Basic import Definitions.Def_FairShareAlmostAll_Slack_FiniteAllocation import Definitions.Def_FairShareAlmostAll_Slack_Instance import Definitions.Def_FairShareAlmostAll_Slack_Buckets
Formal statement
namespace FairShareAlmostAll.Slack.Supplement
open FairShareAlmostAll.Slack AnyPriceShare.Bidding
theorem cutoff_bound {n m : ℕ} (X : Instance n m) (q : ℕ) (h : ConstructionAssumptions X q)
(i : Fin n) (hi : i ∈ active X) :
(cutoff X q i : ℝ) ≤ 2 + 2 * (q : ℝ) * Real.log (1 / X.entitlement i) := by sorry
end FairShareAlmostAll.Slack.Supplement
Source
Tomer Ezra, Tamar Garbuz, Fair Share Allocations for Almost All Agents, STOC 2027 submission #480 (October 2026), printed p. 9 (PDF p. 10), Claim 2.4; proof Appendix A, printed pp. 27–28 (PDF pp. 28–29); standing assumptions §2, printed p. 7 (PDF p. 8); source.pdf SHA256 c9f47a54f6a9e1568951e8e3845ff79c34d51d391a68fd697d37d8ba29cc7491