scripts/fill_logbook.py

"""Write the trackio logbook pages (markdown only; JSON is never touched here)."""

import datetime
import json
import os

ROOT = "/home/ubuntu/samuel/perfpred-complexity-repro"
PAGES = os.path.join(ROOT, ".trackio/logbook/pages")
NOW = "2026-07-25T04:10:00+00:00"

CLAIMS = {
    1: "claim-1-ppad-completeness-at-rho-1-o-eps",
    2: "claim-2-hardness-for-quadratic-loss-affine-shift",
    3: "claim-3-phase-transition-poly-time-ellipsoid-at-rho-1-o-eps-4",
    4: "claim-4-unconditional-2-omega-d-erm-query-lower-bound",
    5: "claim-5-ppad-hardness-on-general-convex-constraint-sets",
    6: "claim-6-pls-hardness-of-local-optima-in-strategic-classification",
}
TITLES = {
    1: "Claim 1: PPAD-completeness at rho <= 1+O(eps)",
    2: "Claim 2: Hardness for quadratic loss + affine shift",
    3: "Claim 3: Phase transition: poly-time ellipsoid at rho <= 1+O(eps^4)",
    4: "Claim 4: Unconditional 2^Omega(d) ERM-query lower bound",
    5: "Claim 5: PPAD-hardness on general convex constraint sets",
    6: "Claim 6: PLS-hardness of local optima in strategic classification",
}


def cell(kind, title, body, pinned=False, cid=None):
    meta = {
        "type": kind,
        "id": cid or ("cell_%012x" % (abs(hash(title + kind + body[:40])) % (16**12))),
        "created_at": NOW,
        "title": title,
    }
    if pinned:
        meta["pinned"] = True
        meta["pinned_at"] = NOW
    return "\n---\n<!-- trackio-cell\n%s\n-->\n%s\n" % (json.dumps(meta), body)


def write(slug, heading, cells):
    d = os.path.join(PAGES, slug)
    os.makedirs(d, exist_ok=True)
    with open(os.path.join(d, "page.md"), "w") as f:
        f.write("# %s\n\n" % heading + "".join(cells))
    print("wrote", slug)


# ------------------------------------------------------------------ claims
BODIES = {}

BODIES[
    1
] = """**Claim (verbatim).** *Theorem 1.2 (restated as Theorem 3.4) proves that computing an
ε-performatively stable point is PPAD-complete even when ρ = Lβ/α ≤ 1 + O(ε), with the explicit
constant ε′ = 0.088/6 ≈ 0.0147 (Section 1.1, Theorem 3.4).*

**Verdict: VERIFIED** (reduction verified executably in both directions; the constant re-derived
from its sources; PPAD-hardness itself is inherited, not executable).

### What is actually executable
PPAD-completeness cannot be run. The executable content of Theorem 3.4 is its reduction: from an
affine VI instance `(A, b)` with `‖A‖₁ ≤ 1`, `‖A‖∞ ≤ 1` (Lemma 3.3, Bernasconi et al. 2024),
build the performative instance `ℓ(x;z) = ½‖x − z‖²`, `D(x) = δ_{g(x)}`,
`g(x) = (I − cA)x − cb` with `c = ε/ε′`. We re-derived and then checked, executably:

| quantity | result |
| --- | --- |
| gap identity `perf-gap(x) = c · VI-gap(x)` for **every** x | 1600 random checks, d ∈ {1,…,100}, max **relative error 4.8e-12** |
| set equality `{ε-stable} = {ε′-VI}` | exhaustive 201×201 grid on [0,1]², 30 instances (1.21M points): **symmetric difference 0** |
| solver round trip (projected extragradient) | 30/30 solved instances satisfy both conditions; Lemma G.1 bound `‖x*−G(x*)‖ ≤ √(ε/α)` holds 30/30 |
| `ρ = Lβ/α = ‖I − cA‖₂ ≤ 1 + c` | **1000/1000** random instances; `A = −I` attains equality exactly (gap 0.0) |
| `‖A‖₂ ≤ √(‖A‖₁‖A‖∞)` (the proof's step) | holds in 1000/1000 |

`α = β = 1` for this loss (Hessian = I), so `ρ = L = ‖I − cA‖₂`, giving `ρ ≤ 1 + ε/ε′ = 1 + 68.18 ε`.

### The constant ε′ = 0.088/6
Recomputed symbolically: `0.088/6 = 0.0146667`, which rounds to the paper's `0.0147`. Its
provenance is **not stated in either cited source** and had to be composed from Bernasconi et al.'s
*proof*:

* Pure-Circuit (Deligkas, Fearnley, Hollender, Melissourgos, JACM 2024), Thm 4.4: ε-Nash in
  polymatrix games is PPAD-hard for all `ε < 2√73 − 17 = 0.08800749…`. The paper's 0.088 clears
  this strict threshold with **7.5e-6 of margin** — a rounding to 0.0881 would have been false.
* Bernasconi et al. (arXiv:2411.03248 **v1/v2**) set `ρ* = ε*/6`, the /6 being the normalisation
  that forces `‖D‖₁, ‖D‖∞ ≤ 1` for a degree-3 graph with `α_ij ∈ [−2,2]`.
* Their own footnote says the constant could be taken larger (their payoffs are unnormalised), so
  **0.088/6 is valid but conservative** — the paper understates rather than overstates.
* Citation drift: the cited "Theorem 4.4" exists only in v1/v2; arXiv v3 renumbers it to Thm 3.4.

### Boundary audit of the scaling constant
`pdftotext` collapses the stacked fraction `ε/ε′` in the theorem statement into `εε′`. We settled
the reading executably rather than by eye (and then confirmed it against the rendered PDF): with
`c = ε·ε′` the implied VI accuracy is `ε/c = 1/ε′ = 68.2`, vacuous against the required 0.0147, and
we exhibit a witness point with perf-gap `3.3e-05 ≤ ε = 1e-3` but VI gap **2.27**. Only `c = ε/ε′`
makes the reduction work — as `sympy` confirms by solving `ε/c = ε′`.

### Scale, seeds, limitation
Seed 20260725; d ∈ {1,2,3,5,10,20,25,50,100}; CPU, ~15 s.
**Limitation:** we verify the reduction, not PPAD-hardness. Lemma 3.3 is taken as given, and the
instances we push through the reduction are random affine VIs, not PPAD-hard ones (generating those
is the hard problem itself).

Artifacts: `scripts/claim1_thm34_reduction.py`, `outputs/claim1_thm34_reduction.json`.
"""

BODIES[
    2
] = """**Claim (verbatim).** *This PPAD-hardness persists in the simple setting where the loss is
quadratic, ℓ(x;z) = ½||x−z||², and the distribution shift D(x) is given by an affine map g(x)
(Section 3.1, Equation 2-3, Theorem 3.4).*

**Verdict: VERIFIED.**

### Independent method
The specialisation is checked in four independent pieces, symbolically and numerically.

1. **The two losses coincide in x.** The paper's hard class uses `ℓ = ½‖x‖² − xᵀz` (Eq. 2) while
   the theorem states `ℓ = ½‖x−z‖²`. `sympy` gives identical gradients and a difference of
   `½‖z‖²`, independent of x — same argmin, same stability condition.
2. **α = β = 1 exactly.** Hessian in x is the identity (eigenvalues all 1.0), and
   `‖∇ₓℓ(x;z) − ∇ₓℓ(x;z′)‖ = ‖z − z′‖` identically (ratio 1.0 on 2000 random pairs), so β = 1 is
   tight. Hence `ρ = L·β/α = L = ‖I − cA‖₂`, verified against a power-iteration estimate of the
   Lipschitz constant of g (max relative deviation **2.0e-04**).
3. **The choice of distribution is irrelevant** (the paper's remark after Eq. 3). Replacing the
   point mass by `N(g(x), σ²I)`, σ ∈ {0, 0.1, 1, 5}, n = 20000 samples: the argmin of the expected
   loss is unchanged to **1.7e-02 (1.2 Monte-Carlo standard errors)** and the W1 sensitivity equals
   the mean shift to **8.8e-02 (2.5 s.e.)** — both consistent with exact equality plus sampling
   noise, as the Kantorovich dual with a linear test function predicts.
4. **Closed-form stable points.** Unconstrained, `x* = g(x*) ⟺ Ax* = −b`; the closed form
   `x* = −A⁻¹b` satisfies `x* = g(x*)` to **1.5e-14** on 20 instances (d = 5).

### Hypomonotonicity of this family
`F(x) = x − g(x) = c(Ax + b)` is σ-hypomonotone with `σ = max(0, −c·λ_min((A+Aᵀ)/2)) ≤ c`,
confirmed for c ∈ {0.01, 0.0682, 0.2, 0.5, 1.0} (5/5), and always inside the Prop. D.6 bound
`σ + σ²/2` (5/5). This is the quantity that Theorem 3.5 exploits, so the two halves of the paper
meet on the same instance family.

### Boundary audit: RRM at, below and above ρ = 1
With `g(x) = −ρx` (Example D.3 generalised), 400 iterations from x₀ = 0.7:

| ρ | measured contraction factor | predicted (Lβ/α) | final distance to x* = 0 |
| --- | --- | --- | --- |
| 0.50 | 0.5000 | 0.50 | 2.7e-121 |
| 0.90 | 0.9000 | 0.90 | 3.5e-19 |
| 0.99 | 0.9900 | 0.99 | 1.3e-02 |
| 1.00 | 1.0000 | 1.00 | 7.0e-01 — **cycles forever** (Example D.3) |
| 1.01, 1.20 | — | — | saturates at the boundary, never converges |

The measured contraction rate equals `Lβ/α` to four decimals, so Perdomo et al.'s rate and the
paper's Proposition 3.8 are reproduced exactly, and the failure at ρ = 1 is reproduced exactly.

**Limitation:** the affine/quadratic specialisation is verified as an instance family; the hardness
of that family still rests on Lemma 3.3.
Seed 20260725, CPU, ~20 s. Artifacts: `scripts/claim2_quadratic_affine.py`,
`outputs/claim2_quadratic_affine.json`.
"""

BODIES[
    3
] = """**Claim (verbatim).** *Theorem 3.5 shows a phase transition to tractability: when
ρ ≤ 1 + O_ε(ε⁴), an ε-performatively stable point can be computed in poly(d, log(1/ε)) time via an
ellipsoid-method algorithm exploiting hypomonotonicity (Section 3.1, Theorem 3.5).*

**Verdict: VERIFIED**, with a strictly sharper hypomonotonicity constant than the paper's.

### 1. The algorithm, implemented and timed
We implemented the square-root-form ellipsoid method for the VI on the ℓ₂ ball, with the separation
oracle of Theorem D.1 (`⟨F(x_k), x − x_k⟩ ≤ 0` is valid for every solution when F is monotone).
105 runs over d ∈ {2, 4, 8, 16, 32} × ε ∈ {1e-2 … 1e-8} × 3 seeds, **all 105 reached the target**:

> **iterations = 2.03 · d^1.957 · (log 1/ε)^0.993,  R² = 0.992**

against the theoretical `O(d² log(1/ε))`. Both exponents land within 5% of the predicted 2 and 1.
No cut was ever invalid on the monotone instances (0 of ~10⁵).

### 2. The exponent ε⁴, re-derived
Prop. D.6 gives `ε′ = sqrt(2D·sqrt((2+σ)(ε + (σ+σ²/2)D²)))`. `sympy` evaluates
`lim_{ε→0} ε′/ε^{1/4} = 2^{3/4}√D(D²+1)^{1/4}`, finite and non-zero, so `ε′ = Θ(ε^{1/4})` when
σ ≤ ε; inverting for a target accuracy δ yields `ε ~ δ⁴`, i.e. **ρ ≤ 1 + Θ(δ⁴)**. That is exactly
the claim's exponent, obtained independently of the paper's prose.

### 3. The phase transition, measured
40 configurations (rotation angle θ × expansiveness σ, ρ = 1 + σ, d = 4):

* the Prop. D.5 VI certificate holds in **40/40**, the Prop. D.6 fixed-point certificate in **40/40**;
* the certificates scale as **σ^0.51** (VI) and **σ^0.26** (fixed point) versus the predicted ½ and ¼;
* **the mechanism is visible.** The fraction of ellipsoid cuts that cut away the true solution is
  **0.00 while the operator is monotone and 1.00 as soon as it is hypomonotone**. At θ = 30° the
  operator stays monotone up to σ ≈ 0.155: for σ ≤ 0.1 the achieved fixed-point gap is ~1e-17, and
  at σ = 0.3, 0.5, 1.0 it jumps to 3e-17, 1.6e-02, 8.9e-01. At θ = 0° (maximally hypomonotone) the
  achieved gap is **1.4·σ for every σ**, from 1.4e-06 at σ = 1e-6 up to 1.2 at σ = 1.

### 4. Sharper constant than the paper
Identity (11) is exact (`sympy`), and it simplifies to `⟨u, u − w⟩`. Its minimum over
`‖w‖ ≤ (1+σ)‖u‖` is attained at `w = (1+σ)u` and equals **−σ‖u‖²**. So `F = id − T` is *exactly*
σ-hypomonotone; the paper's `σ + σ²/2` is valid but loose by σ²/2 (a factor 1.5 at σ = 1). The
theorem holds a fortiori.

### 5. RRM vs ellipsoid at ρ ≥ 1 (the paper's motivating point)
| setting | ellipsoid fixed-point gap | RRM best gap in 5000 iterations |
| --- | --- | --- |
| θ = 90°, ρ = 1.00 | 0.0 (1185 iters) | 7.9e-01 |
| θ = 90°, ρ = 1.01 | 1.6e-17 | 5.7e-01 |
| θ = 90°, ρ = 1.10 | 4.0e-17 | 7.1e-01 |
| θ = 30°, ρ = 1.01 | 6.4e-17 | 2.7e-01 |

ρ > 1 alone does *not* imply intractability — exactly the paper's argument for why Theorem 3.4 is
needed at all.

### Honest negative result
On our instance families the ellipsoid attains accuracy δ ≈ 1.4σ, i.e. it only needs
`ρ ≤ 1 + O(δ)`, far better than the certified `1 + O(δ⁴)`. The paper's bound is a worst-case
guarantee and we could not instantiate a worst case — constructing one is the PPAD-hard problem
itself. This is a limitation of the reproduction, not a contradiction; it mirrors the gap between
Theorem 3.5 and Diakonikolas (2025) that the paper itself flags as open.

Seed 20260725, CPU, ~3 min. Artifacts: `scripts/claim3_ellipsoid_phase.py`,
`outputs/claim3_ellipsoid_phase.json`, `figs/claim3_ellipsoid_phase.png`.
"""

BODIES[
    4
] = """**Claim (verbatim).** *Corollary 3.7 establishes an unconditional information-theoretic lower
bound: any algorithm requires 2^Ω(d) expected-risk-minimization (ERM) queries to find an
ε-performatively stable point even when ρ ≤ 1 + O_ε(ε), and even for constant ε (Section 3.1,
Corollary 3.7).*

**Verdict: VERIFIED** (the reduction and the query equivalence are exact; the underlying
Hirsch–Papadimitriou–Vavasis bound is inherited; the empirical probe is labelled **toy**).

### 1. Proposition 3.2 and the query equivalence — the crux
The corollary rests on one observation: an ERM query of the constructed instance is worth exactly
one query of T. With `g(x) = (1−λ)x + λT(x)` and `λ = ε/ε′`, checked over d ∈ {2, 5, 20} and
λ ∈ {1, 0.5, 0.1, 0.01}, 400 random points each:

| check | result |
| --- | --- |
| `‖x − G(x)‖ = λ‖x − T(x)‖` | max error **1.4e-16** |
| `ρ = Lip(g) ≤ 1 + λL` | 12/12 configurations |
| `T(x) = (G(x) − (1−λ)x)/λ` recovered from **one** ERM query | max error **5.6e-15** |

The oracles are therefore information-theoretically equivalent, and the Hirsch et al. bound
transfers with no loss — this is precisely the sentence the corollary rests on, and it is exact.

### 2. What "even for constant ε" means
Theorem 3.6 gives `c((1/ε − 10)L)^{d−2}`. Evaluated symbolically at L = 1:

| ε | 1/10 | 1/11 | 1/12 | 1/20 | 1/100 |
| --- | --- | --- | --- | --- | --- |
| base | 0.000 | 1.000 | **2.000** | 10.0 | 90.0 |

So the bound is `≥ c·2^{d−2} = 2^Ω(d)` exactly when **ε ≤ 1/12**, and is vacuous for ε > 1/11. The
corollary's "even when ε is a constant" is correct, and we pin down which constants: below 1/11.
Combined with Prop. 3.2 this is `ρ ≤ 1 + (ε/ε′)L = 1 + O(ε)`, as claimed.

### 3. Toy probe: how the exponential actually shows up
We built a hidden-path Brouwer family on the grid `{0,…,m−1}^d` (m = 3): a random self-avoiding
path of length ≈ √N, the direction field is the default `+e₁` off the path, so an off-path query is
consistent with every instance that misses that cell. The natural strategy (probe until you hit the
path, then follow it) needs, median over 40 seeds:

| d | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| ERM queries | 4 | 6 | 10 | 19 | 32.5 | 58 | 92.5 | 186.5 |

Fitted: **queries ~ 1.737^d, R² = 0.998**, against the predicted `√m = 1.732`. Exponential in d,
with the predicted base.

**Label: toy.** Blocker: this is our own discrete family with the same information-hiding
mechanism, not the Hirsch–Papadimitriou–Vavasis continuous Brouwer construction, and it measures
the cost of the strategies we implement rather than proving a lower bound over all algorithms. The
unconditional lower bound itself is inherited from Hirsch et al. (1989) and is not re-proved here.

Seed 20260725, CPU, ~40 s. Artifacts: `scripts/claim4_erm_query_lb.py`,
`outputs/claim4_erm_query_lb.json`, `figs/claim4_query_lb.png`.
"""

BODIES[
    5
] = """**Claim (verbatim).** *Theorem 3.12 extends PPAD-hardness of performative stability from the
hypercube constraint set to any well-bounded general convex constraint set (Section 3.3,
Theorem 3.12, Definition 3.11).*

**Verdict: VERIFIED, with three defects in the write-up recorded below** (none of which affects
the theorem).

### The whole construction, executed
We implemented Appendix E end-to-end: the equilateral triangle `A₁=(0,0)`, `A₂=(√3,0)`,
`A₃=(√3/2,3/2)` (side √3, circumradius 1, verified); the ε-ThickBrouwer colouring (17) with
ε = 1/8 on the 8×8 grid (n = 3); the nearest-side colouring (18) outside; the bit-extraction circuit
of Algorithm 1 with bounded operations and ramp width 1/L, `L = (k+2)2^{n+1}`; and the k = 16
sampled-colour operator `F(x)`. Direction vectors verified: `a⊥+b⊥+c⊥ = 0` and each is orthogonal
to its side.

Then we brute-force scanned four different well-bounded domains at 400×400, plus a local
refinement:

| domain X | min gap on scan | refined minimum | inside the triangle? | all 3 colours? | conclusion holds for every ε up to |
| --- | --- | --- | --- | --- | --- |
| unit disk (triangle inscribed) | 0.0301 | **3.2e-06** | yes | yes | 0.25 |
| disk R = 1.6 | 0.0463 | **8.8e-06** | yes | yes | 0.50 |
| square (ℓ∞ ball) | 0.0311 | **4.7e-06** | yes | yes | 0.25 |
| irregular 7-gon | 0.0327 | **4.8e-06** | yes | yes | 0.25 |

"Conclusion holds" means: **every** scanned point with VI gap ≤ ε lies inside the triangle *and*
its well-positioned samples carry all three colours — which is exactly what the proof needs to
recover a trichromatic square, and hence a 2D-Sperner solution. It holds far beyond the paper's
ε′ (1/32), and breaks at ε = 0.5, so the boundary is located too.

Supporting checks: **Lemma E.4** (at most two of the k samples poorly positioned) holds with the
observed maximum exactly 2; Sperner's lemma gives 3 trichromatic squares on the grid, all 3 of
which yield a trichromatic triangle; the empirical `Lip(F) = 28.3` with `2ⁿ = 8` gives
`Lip(F/2ⁿ) = 3.5 = O(1)` and `ε″ = ε′/2ⁿ = 2.0e-03 = O(2⁻ⁿ)`, as the rescaling step claims. Both
case bounds of the proof hold on the executed operator with the paper's literal rule (18):
case 1 `max F_x = −0.658 ≤ −0.633`, case 2 `max F_y = −0.398 ≤ −0.313`.

**Corollary 3.13** (the performative version) also checks out: with `g(x) = x + cF(x)` the
performative stability gap equals `c ×` the VI gap to **7.0e-17**.

### Defect 1 — an arithmetic slip in the constant
The proof sets ε = 1/8 and then writes "`k ≥ 16` and `ε′ ≤ ε/8 = 1/32`". But **ε/8 = 1/64, not
1/32**, and the slip is load-bearing for one line: the second case of the proof yields
`(ε/2)((k−2)/(2k) − 2/k) = 0.019531`, which **clears 1/64 = 0.015625 but not 1/32 = 0.03125**.
(Case 1 yields 0.5084 and clears both.) The argument goes through unchanged with ε′ ≤ 1/64; we also
computed the minimal k for which case 2 reaches ε/8: **k ≥ 12**, so the stated k ≥ 16 is fine.
Alternatively the printed 1/32 is consistent if ε = 1/4, contradicting the ε = 1/8 fixed earlier.

### Defect 2 — incompatible coordinates
Definition 3.11 places the inner ball at the origin (`B_{R1}(0) ⊆ X`), and the proof inscribes the
triangle in that ball while *also* setting `A₁ = (0,0)`. Both cannot hold: with A₁ at the origin the
circumcentre is at `(√3/2, 1/2)` and `|A₂| = |A₃| = √3 ≠ 1`. Cosmetic — we work in the paper's
coordinates and put the inner unit ball at the circumcentre.

### Defect 3 — F is not continuous outside the triangle
Rule (18) assigns the colour of the *nearest* side, an argmin, which is discontinuous across the
angle bisectors; the k-sample average of a discontinuous function is still discontinuous. Yet
Remark E.5 asserts F is a well-behaved arithmetic circuit, and the VI (4) needs continuity for a
solution to exist at all. Inside the triangle the bit-extraction ramp does deliver continuity. We
restored it outside by blending the tied sides over a quarter of a grid cell; every blended
direction still points inward, so the argument is unaffected, but the case-1 numerical bound then
loosens from −0.658 to −0.487 (against the printed −0.633).

**Limitation:** the colouring we feed in is a random admissible ThickBrouwer colouring, not the
output of a PPAD-hard 2D-Sperner instance; PPAD-hardness is inherited from Chen & Deng (2009). We
verify that the *reduction* does what the theorem needs.

Seed 20260725, n = 3, k = 16, 4 domains × 400², CPU, ~4 min.
Artifacts: `scripts/claim5_sperner_convex.py`, `outputs/claim5_sperner_convex.json`,
`figs/claim5_sperner_convex.png`.
"""

BODIES[
    6
] = """**Claim (verbatim).** *For the special case of strategic classification, Theorem 4.4 shows that
computing a local optimum of the performative risk under single-label updates is PLS-hard,
complementing prior NP-hardness results for global performative optimality (Abstract,
Section 1.1, Theorem 4.4).*

**Verdict: FALSIFIED as proved.** The reduction of Appendix F is **not** solution-preserving: the
instances it produces have strategic local optima that encode no cut at all, and one of them is the
constant classifier `f ≡ 1`, computable in O(1) without looking at the graph. The theorem's
*statement* may still be true — a different reduction could establish it — but it is not
established by this proof. A guard-point repair we tried does not fix it.

### The counterexample (exact, exhaustive, hand-checkable)
Take the graph with a single edge (0,1) of weight 1. The construction gives
`X = {x_{0−}, x_{1−}, x_{e+}, x_{e−}}` with `h = (0,0,1,0)` and weights `(1,1,2,3)`, `M = 7`.
Consider `f ≡ 1`:

| classifier | M·U |
| --- | --- |
| `f ≡ 1` | **2.0** |
| flip `x_{0−}` | 2.0 |
| flip `x_{1−}` | 2.0 |
| flip `x_{e+}` | 2.0 |
| flip `x_{e−}` | 2.0 |
| best classifier | 6.0 |

No single flip improves, so `f ≡ 1` is a strategic local optimum (Definition 4.3). Its vertex
labelling is `(1,1)`, a cut of weight 0, while the max cut is 1 — **not** a local max cut. The
Contestant's best response is unique in every one of these configurations (staying pays 1 for a
1-labelled point; moving pays 1 − 0.8 = 0.2 > 0 for a 0-labelled point with a close 1-labelled
neighbour), so no tie-breaking convention can rescue it — and since all four neighbours attain
*exactly* the same utility, `f ≡ 1` also satisfies Definition 4.3 read literally with equality.

**Why it happens, in general.** When every label is 1 no point deviates (staying pays 1, moving
pays at most 1 − 0.8). Flipping one label to 0 makes that point deviate to any close point still
labelled 1, so `f(Δ(x))` is unchanged and no other point is affected. Hence:

> `f ≡ 1` is a strategic local optimum of **every** instance in which each `h = 0` point has a
> close neighbour — and the construction guarantees exactly that (`x_{v−}` is close to its incident
> `x_{(u,v)+}`, and `x_{(u,v)−}` is close to `x_{(u,v)+}`).

**Where the proof breaks.** Appendix F's first claim says a Jury with `f(x_{(u,v)−}) = 1` gains at
least 1/M by flipping it to 0 "because it ensures that the negative edge point is classified
correctly". That silently assumes `f(x_{(u,v)+}) = 0`. If `f(x_{(u,v)+}) = 1`, the point
strategically deviates to `x_{(u,v)+}` after the flip and is still misclassified: the gain is 0.

### Exhaustive enumeration
Every one of the `2^|X|` classifiers, for 11 graphs (n ≤ 5), with the Contestant's exact best
response — 27 920 classifiers for the published construction and 418 848 for the repair attempt,
**446 768 in total**:

| construction | direction 1 (local opt ⇒ local max cut) | direction 2 (local max cut ⇒ local opt) |
| --- | --- | --- |
| as published | **FAILS on 11/11 graphs** — e.g. on a 4-vertex 4-edge graph, 42 of the 46 strategic local optima are spurious against only 4 local max cuts | holds 11/11 |
| + guard point per edge (our repair attempt) | **still fails** 11/11 | holds 11/11 |

### What does survive
* the cost function is a metric (0 triangle violations, symmetric, zero diagonal);
* the utility identity `M·U(f) = w(cut) + const` on cut-induced classifiers: spread **1.4e-14**;
* Eq. (19)–(20): flipping `x_{(u,v)−}` from 1 to 0 gains exactly `1/M` **when `f(x_{(u,v)+}) = 0`**;
* Eq. (22) and (24): the utility deltas of a vertex flip equal the cut deltas, max error **9.3e-15**;
* the **global** optima are exactly the max cuts, so the paper's remark that the construction
  re-proves NP-hardness of global strategic optimality is unaffected.

So the analysis is correct on the sub-family the proof has in mind, and the failure is precisely
that local search is not confined to that sub-family.

### Also: the cost values are not free
The paper says the two cost values may be set to "arbitrary" values in (0,1) and (1,∞). The metric
property forces `c_far ≤ 2·c_close`: 0.8/1.2 and 0.9/1.1 are metrics, while 0.5/1.2, 0.5/1.5 and
0.1/5.0 each produce **40 triangle-inequality violations**. The theorem's "even when c is a metric"
still holds for the chosen 0.8/1.2.

**Limitation:** PLS-hardness itself is inherited from the PLS-completeness of LocalMaxCut
(Schäffer & Yannakakis 1991). We falsify the reduction, not the complexity class statement, and we
did not find a repair.

Seed 20260725, CPU, ~2 min. Artifacts: `scripts/claim6_pls_localmaxcut.py`,
`outputs/claim6_pls_localmaxcut.json`.
"""

for n, slug in CLAIMS.items():
    write(slug, TITLES[n], [cell("markdown", TITLES[n], BODIES[n])])

# ------------------------------------------------------------------ index
index = """# Reproduction: On the Computational Complexity of Performative Prediction

## Pages

| Page |
| --- |
| [Executive summary](#/executive-summary) |
"""
for n, slug in CLAIMS.items():
    index += "| [%s](#/%s) |\n" % (TITLES[n], slug)
index += "| [Conclusion](#/conclusion) |\n"
with open(os.path.join(PAGES, "index.md"), "w") as f:
    f.write(index)
print("wrote index.md")

# ------------------------------------------------------------------ summary
SUMMARY = """Paper: [arXiv:2601.20180](https://arxiv.org/abs/2601.20180) ·
[OpenReview kkhVljGiMS](https://openreview.net/forum?id=kkhVljGiMS) ·
reproduction by [SabaPivot](https://huggingface.co/SabaPivot). No official code release exists
(arXiv listing, ancillary files, GitHub search, Papers-with-Code, Semantic Scholar, alphaXiv and
the authors' pages all checked).

**Outcome: five of the six claims reproduce; the sixth is falsified as proved.** This is a pure
complexity paper — no code, no experiments, 34 pages — so we reproduced the *executable* content:
every reduction was implemented and checked for solution preservation in both directions, every
explicit constant was recomputed from its sources, and the one algorithm in the paper (the
ellipsoid method of Theorem 3.5) was implemented and fitted against its claimed complexity, giving
**iterations = 2.03·d^1.957·(log 1/ε)^0.993 (R² = 0.992)** versus the predicted `d² log(1/ε)`.
Claims 1–5 hold: the Theorem 3.4 reduction satisfies `perf-gap = (ε/ε′)·VI-gap` exactly (symmetric
difference **0** between the ε-stable and ε′-VI sets over 1.21M exhaustively enumerated points), the
constant `ε′ = 0.088/6` traces to `2√73 − 17 = 0.0880075` with 7.5e-6 of margin, one ERM query
recovers `T(x)` to 5.6e-15 so the 2^Ω(d) bound transfers intact, and the full Appendix E
Sperner construction runs on four different well-bounded convex domains with every ε-solution
landing inside the triangle on a trichromatic square. **Claim 6 is falsified:** enumerating all
`2^|X|` classifiers on 11 graphs (446 768 in total) shows the constant classifier `f ≡ 1` is a
strategic local optimum of *every* instance the Appendix F reduction produces, encoding the empty
cut — so the reduction is not solution-preserving and the published proof of PLS-hardness does not
go through. We also found three smaller defects (an ε/8 = 1/32 arithmetic slip that its own case
analysis cannot support, incompatible coordinates in Definition 3.11 vs the proof, and a
discontinuous operator outside the triangle) and one place where the paper is *too conservative*
(F = id − T is exactly σ-hypomonotone, not σ + σ²/2).

## Scope & cost

| Item | Value |
| --- | --- |
| Scope | all 6 claims, independently reproduced from the arXiv PDF; no official code exists |
| Hardware | CPU only (no GPU), 1 machine, numpy + sympy + scipy |
| Compute time | ~11 minutes total across 6 scripts |
| Cost | $0.00 |
| Seeds | 20260725 everywhere |
| Artifacts | 6 scripts, 6 JSON result files, 3 figures |
"""

POSTER_PLACEHOLDER = """````html
<p>poster_embed.html pending</p>
````"""

write(
    "executive-summary",
    "Executive summary",
    [
        cell(
            "markdown",
            "Executive summary",
            SUMMARY,
            pinned=True,
            cid="cell_8c66c9c92879",
        ),
        cell(
            "figure",
            "Reproduction poster (poster_embed.html)",
            POSTER_PLACEHOLDER,
            pinned=True,
            cid="cell_e15a1c7fda7a",
        ),
    ],
)

# ------------------------------------------------------------------ conclusion
CONCLUSION = """### Verdicts

| Claim | Result | Key number |
| --- | --- | --- |
| 1 — Thm 3.4, PPAD-hardness at ρ ≤ 1 + ε/ε′, ε′ = 0.088/6 | **verified** | symmetric difference **0** between the ε-stable and ε′-VI sets over 1.21M grid points |
| 2 — quadratic loss + affine shift | **verified** | α = β = 1 exactly; RRM contraction 0.9900 measured at ρ = 0.99, cycles at ρ = 1 |
| 3 — Thm 3.5 phase transition | **verified** | iterations = 2.03·d^1.957·(log 1/ε)^0.993, R² = 0.992 |
| 4 — Cor 3.7, 2^Ω(d) ERM queries | **verified** (toy probe) | T recovered from one ERM query to 5.6e-15; toy family needs 1.737^d queries (predicted √3 = 1.732) |
| 5 — Thm 3.12, general convex domains | **verified** (3 write-up defects) | refined minimum VI gap 3.2e-06, inside the triangle, trichromatic, on 4/4 domains |
| 6 — Thm 4.4, PLS-hardness | **falsified as proved** | `f ≡ 1` is a strategic local optimum of every produced instance; 446 768 classifiers exhaustively enumerated |

### How to rerun

```bash
hf buckets sync hf://buckets/SabaPivot/repro-perfpred-complexity-artifacts ./perfpred-repro
cd perfpred-repro
python -m venv .venv && .venv/bin/pip install numpy scipy sympy matplotlib
for s in 1 2 3 4 5 6; do .venv/bin/python scripts/claim${s}_*.py; done
```

Every script is CPU-only, seeded with 20260725, writes its own JSON into `outputs/`, and finishes
in under four minutes. `scripts/common.py` holds the shared helpers. Total runtime ~11 minutes.

### What a follow-up should do

The open item is Theorem 4.4. The gadget of Appendix F cannot be rescued by local patching: any
instance in which every `h = 0` point has a close neighbour admits `f ≡ 1` as a strategic local
optimum, and removing that property removes the deviations the reduction is built on. Establishing
PLS-hardness of strategic local optimality needs a construction in which some `h = 0` points are
isolated *and* the cut structure is still forced.
"""

ARTIFACT = """The complete reproduction bundle: 6 scripts, 6 JSON result files, 3 figures, the poster
sources, and the paper PDF.

```
scripts/   common.py, claim1_thm34_reduction.py, claim2_quadratic_affine.py,
           claim3_ellipsoid_phase.py, claim4_erm_query_lb.py,
           claim5_sperner_convex.py, claim6_pls_localmaxcut.py
outputs/   claim{1..6}_*.json          (every number quoted in this logbook)
figs/      claim3_ellipsoid_phase.png, claim4_query_lb.png, claim5_sperner_convex.png
poster/    poster.html, poster.pdf, poster.png, poster_embed.html
paper/     paper.txt (extracted text of arXiv:2601.20180)
```

**Download:** <https://huggingface.co/buckets/SabaPivot/repro-perfpred-complexity-artifacts>

```bash
hf buckets sync hf://buckets/SabaPivot/repro-perfpred-complexity-artifacts ./perfpred-repro
cd perfpred-repro && python scripts/claim1_thm34_reduction.py
```
"""

write(
    "conclusion",
    "Conclusion",
    [
        cell("markdown", "Verdicts and rerun instructions", CONCLUSION),
        cell("artifact", "Reproduction bundle", ARTIFACT),
    ],
)
print("done")