Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 11 — PPAD-hardness of contiguous EFc and EFc-outer for binary exclusive equal-count goods

Open
ContiguousCake597.Approximate.Supplement.lemma_11

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

fair-divisionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1ppad

Fix any integer c≥0c\ge0c≥0 (including c=0c=0c=0). Consider goods on a path with binary valuations in which every good has value 111 for exactly one agent and value 000 for all others, and all agents value the same number of goods. Then the search problem of computing a contiguous EFccc allocation on such instances is PPAD-hard: every search problem in PPAD reduces to it by a polynomial-time search reduction. The same holds with EFcouterc_{\mathrm{outer}}couter​ in place of EFccc:

∀R∈PPAD:R≤p\textscEFc-Pathbin,R≤p\textscEFcouter-Pathbin.\forall R\in\mathrm{PPAD}:\quad R\le_p \textsc{EF}c\text{-Path}_{\mathrm{bin}},\qquad R\le_p \textsc{EF}c_{\mathrm{outer}}\text{-Path}_{\mathrm{bin}}.∀R∈PPAD:R≤p​\textscEFc-Pathbin​,R≤p​\textscEFcouter​-Pathbin​.

Only hardness is asserted; totality of the relation is not claimed by this statement. This lemma supplies the hardness half of Theorem 2 for a fixed budget.

Differences from the source:

  • encoding: "computing ... is PPAD-hard" → every problem of the published class PPAD search-reduces to the encoded relation whose answers are all complete contiguous allocations satisfying the notion; reason: the standard meaning of PPAD-hardness of a search problem with the paper's encodings
  • reading: n agents → n ≥ 1 agents; reason: the paper's standing convention (with no agents and at least one good there is no allocation); it only restricts the target instances, which the reduction must produce
Preamble
import Definitions.Def_ContiguousCake597_Approximate_Supplement_Path
Formal statement
namespace ContiguousCake597.Approximate.Supplement

/-- Lemma 11, printed p.11 (PDF 12), proof printed p.12 (PDF 13). For every fixed
`c ≥ 0`, contiguous goods EFc and EFc_outer search are PPAD-hard on binary
exclusive-ownership equal-count instances. Hardness only; no totality is asserted. -/
theorem lemma_11 (c : ℕ) :
    (∀ R ∈ QuasiStrictNE.PPAD,
      CardinalMatching.SearchReduces R (PathProblem false false (.const c) true)) ∧
    (∀ R ∈ QuasiStrictNE.PPAD,
      CardinalMatching.SearchReduces R (PathProblem false true (.const c) true)) := by sorry

end ContiguousCake597.Approximate.Supplement
Source
Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui, STOC 2027 submission #597 (October 2026), p. 11 (PDF 12), Lemma 11; proof p. 12 (PDF 13)

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