Lemma 9 — decoding with error at most 1/100
ProvedContiguousCake597.Approximate.lemma_9cake-cuttingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1ppad
Let be any nonempty directed graph with every indegree at most two, and use its constructed cake on . Let be any complete -envy-free allocation with real cuts and arbitrary assignment permutation , where , , , and for the number of graph vertices. Put and . For every player this explicitly decoded vector satisfies
Here sums the decoded strategies of the incoming neighbors of , with a self-loop counted once. The sign is positive in this absolute-value formula. No equilibrium property, price inequality or localization property is assumed. This is the quantitative estimate used by the final threshold-game decoder.
Differences from the source:
- encoding: matrix row u is the in-neighbor set → the sum over graph edges v→u; reason: the published graph adjacency arguments are transposed relative to the paper's matrix convention
Preamble
import Definitions.Def_ContiguousCake597_Approximate_Analysis
Formal statement
namespace ContiguousCake597.Approximate
/-- Lemma 9, printed p.10 (PDF 11), proof continues on printed p.11
(PDF 12). The sign and constant are literal. -/
theorem lemma_9 (G : HZTractability.ThrGraph) (hn : 1 ≤ G.n)
(hdeg : ∀ v, G.indeg v ≤ 2) (T : Allocation ℝ (N G))
(hT : AnalyticAnswer G T) :
∀ u : Fin G.n,
|T.cuts (specialPiece G u).succ - (a G u : ℝ) * B G +
12 * incoming G T u| ≤ 1/100 := by sorry
end ContiguousCake597.Approximate
Source
Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui, STOC 2027 submission #597 (October 2026), p. 10 (PDF 11), Lemma 9, proof continues p.11 (PDF 12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.