Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 12 — PPAD membership of contiguous EF1-outer for goods and for chores

Open
ContiguousCake597.Approximate.Supplement.lemma_12

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

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

Consider n≥1n\ge1n≥1 agents and mmm items on a path.

  1. For goods with arbitrary nonnegative rational additive valuations, the search problem of computing a contiguous EF1outer1_{\mathrm{outer}}1outer​ allocation lies in PPAD.
  2. For chores with arbitrary nonnegative rational additive costs, the search problem of computing a contiguous EF1outer1_{\mathrm{outer}}1outer​ allocation lies in PPAD.

Here EF1outer1_{\mathrm{outer}}1outer​ for goods means: for all i,ji,ji,j one can remove at most one good from XjX_jXj​, leaving a connected or empty set, so that νi(Xi)≥νi(Xj∖G)\nu_i(X_i)\ge\nu_i(X_j\setminus G)νi​(Xi​)≥νi​(Xj​∖G); for chores one removes at most one chore from XiX_iXi​, leaving a connected or empty set, so that κi(Xi∖G)≤κi(Xj)\kappa_i(X_i\setminus G)\le\kappa_i(X_j)κi​(Xi​∖G)≤κi​(Xj​). 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 EF1outer1_{\mathrm{outer}}1outer​ allocation is EFccc and EFcouterc_{\mathrm{outer}}couter​ for every c≥1c\ge1c≥1.

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

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