Lemma 11 — PPAD-hardness of contiguous EFc and EFc-outer for binary exclusive equal-count goods
OpenContiguousCake597.Approximate.Supplement.lemma_11fair-divisionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1ppad
Fix any integer (including ). Consider goods on a path with binary valuations in which every good has value for exactly one agent and value for all others, and all agents value the same number of goods. Then the search problem of computing a contiguous EF 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 EF in place of EF:
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)