Lemma 12 — PPAD membership of contiguous EF1-outer for goods and for chores
OpenContiguousCake597.Approximate.Supplement.lemma_12fair-divisionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1ppad
Consider agents and items on a path.
- For goods with arbitrary nonnegative rational additive valuations, the search problem of computing a contiguous EF allocation lies in PPAD.
- For chores with arbitrary nonnegative rational additive costs, the search problem of computing a contiguous EF allocation lies in PPAD.
Here EF for goods means: for all one can remove at most one good from , leaving a connected or empty set, so that ; for chores one removes at most one chore from , leaving a connected or empty set, so that . Membership in PPAD is in the sense of §2.1: the problem is total and reduces to End-of-Line, its answers are verifiable in polynomial time, and every valid input has an answer of polynomial length.
This supplies the membership half of Theorem 2, since an EF allocation is EF and EF for every .
Differences from the source:
- encoding: "lies in PPAD" → the published PPAD predicate together with a polynomial-time verifier and short-witness existence; reason: the paper's definition of PPAD in §2.1 includes both requirements, which the published PPAD predicate does not
- reading: n agents → n ≥ 1 agents; reason: the paper's standing convention; with no agents and at least one item no allocation exists and the problem would not be total
Preamble
import Definitions.Def_ContiguousCake597_Approximate_Supplement_Path
Formal statement
namespace ContiguousCake597.Approximate.Supplement
/-- Lemma 12, printed p.13 (PDF 14). Contiguous EF1_outer search lies in PPAD (with the
§2.1 verification and short-witness requirements) for arbitrary nonnegative rational
additive goods valuations and for arbitrary nonnegative rational additive chore costs. -/
theorem lemma_12 :
PaperPPAD (PathProblem false true (.const 1) false) ∧
PaperPPAD (PathProblem true true (.const 1) false) := by sorry
end ContiguousCake597.Approximate.Supplement
Source
Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui, STOC 2027 submission #597 (October 2026), p. 13 (PDF 14), Lemma 12