scripts/claim1_thm34_reduction.py

"""Claim 1 -- Theorem 1.2 / Theorem 3.4 of arXiv:2601.20180.

"Finding an eps-performatively stable point per Definition 2.4 is PPAD-hard even
 when L*beta/alpha <= 1 + eps/eps' for eps' = 0.088/6 ~= 0.0147."

PPAD-hardness itself is not executable.  What IS executable is the reduction
that carries the hardness (proof of Theorem 3.4, Appendix G):

    given (A,b) with ||A||_1 <= 1, ||A||_inf <= 1, and target accuracies
    eps (performative) and eps' (VI), set  c = eps/eps'  and

        loss    l(x;z) = 1/2 ||x - z||_2^2          (alpha = beta = 1)
        shift   D(x)   = point mass at g(x) = (I - cA) x - c b   (L = ||I-cA||_2)

    Then x* is an eps-performatively stable point of that instance
    IFF x* is an eps'-approximate solution of the affine VI  F(x) = A x + b
    on the hypercube, and rho = L*beta/alpha <= 1 + c.

We verify: (i) the exact gap identity in both directions, (ii) the rho bound and
its tightness, (iii) the spectral-norm inequality the proof uses, (iv) the
explicit constant 0.088/6, and (v) a boundary audit of the scaling constant.

Run:  python scripts/claim1_thm34_reduction.py
"""

import numpy as np
import sympy as sp

from common import (
    box_proj,
    box_vi_gap,
    dump,
    norm1,
    norminf,
    random_affine_vi,
)

SEED = 20260725
res = {"seed": SEED, "paper": "arXiv:2601.20180", "claim": "Theorem 1.2 / 3.4"}


# --------------------------------------------------------------------------
# 0. the explicit constant eps' = 0.088/6
# --------------------------------------------------------------------------
eps_p = sp.Rational(88, 1000) / 6
res["constant"] = {
    "eps_prime_exact": str(eps_p),
    "eps_prime_float": float(eps_p),
    "paper_states": 0.0147,
    "abs_err_vs_paper_rounding": abs(float(eps_p) - 0.0147),
    "rounds_to_4dp": float(sp.N(eps_p, 6)),
    "matches_paper_rounding": round(float(eps_p), 4) == 0.0147,
    "implied_rho_slope_1_over_eps_prime": float(1 / eps_p),
}
print("eps' = 0.088/6 =", float(eps_p), " -> rho <= 1 + %.3f eps" % float(1 / eps_p))


# --------------------------------------------------------------------------
# 1. the reduction, implemented literally
# --------------------------------------------------------------------------
def build_instance(A, b, eps, eps_prime):
    """Theorem 3.4's reduction.  Returns (g, c) with g the distribution map."""
    c = eps / eps_prime
    d = A.shape[0]
    M = np.eye(d) - c * A

    def g(x):
        return M @ x - c * b

    return g, c, M


def perf_stability_gap(xstar, g):
    """max_{x in X} <x* - x, E_z[grad_x l(x*;z)]> with l = 1/2||x-z||^2, z=g(x*).

    grad_x l(x*; z) = x* - z = x* - g(x*).  Definition 2.4 asks this gap <= eps.
    """
    return box_vi_gap(xstar, xstar - g(xstar))


def rrm_map(x, g):
    """G(x) = argmin_{x' in [0,1]^d} E_{z~D(x)} l(x';z) = proj(g(x))."""
    return box_proj(g(x))


rng = np.random.default_rng(SEED)

# ---- 1a. exact gap identity  perf_gap(x*) = (eps/eps') * vi_gap(x*)
ident = []
for d in [1, 2, 3, 5, 10, 25, 50, 100]:
    for trial in range(20):
        A, b = random_affine_vi(d, rng)
        eps = float(10 ** rng.uniform(-6, -1))
        g, c, _ = build_instance(A, b, eps, float(eps_p))
        for _ in range(10):
            x = rng.uniform(0, 1, size=d)
            pg = perf_stability_gap(x, g)
            vg = box_vi_gap(x, A @ x + b)
            ident.append(abs(pg - c * vg) / max(1e-300, abs(pg) + abs(c * vg)))
ident = np.array(ident)
res["gap_identity"] = {
    "n_checks": int(ident.size),
    "max_relative_error": float(ident.max()),
    "median_relative_error": float(np.median(ident)),
    "statement": "perf_gap(x) == (eps/eps') * vi_gap(x) exactly, for every x",
}
print("gap identity: %d checks, max rel err %.3e" % (ident.size, ident.max()))

# ---- 1b. solution preservation in BOTH directions, on an exhaustive 2-D grid
gridres = 201
xs = np.linspace(0, 1, gridres)
XX, YY = np.meshgrid(xs, xs, indexing="ij")
grid = np.stack([XX.ravel(), YY.ravel()], axis=1)
both_dir = []
for trial in range(30):
    A, b = random_affine_vi(2, rng)
    eps = float(10 ** rng.uniform(-4, -1))
    g, c, _ = build_instance(A, b, eps, float(eps_p))
    V = grid @ A.T + b
    vg = np.sum(np.maximum(grid * V, (grid - 1.0) * V), axis=1)
    G = grid @ (np.eye(2) - c * A).T - c * b
    W = grid - G
    pg = np.sum(np.maximum(grid * W, (grid - 1.0) * W), axis=1)
    set_perf = pg <= eps * (1 + 1e-12)
    set_vi = vg <= float(eps_p) * (1 + 1e-12)
    both_dir.append(
        {
            "trial": trial,
            "eps": eps,
            "n_eps_perf_stable": int(set_perf.sum()),
            "n_eps_prime_vi": int(set_vi.sum()),
            "symmetric_difference": int(np.logical_xor(set_perf, set_vi).sum()),
        }
    )
res["exhaustive_2d_solution_preservation"] = {
    "grid": "%d x %d over [0,1]^2 (%d points/instance)"
    % (gridres, gridres, grid.shape[0]),
    "n_instances": len(both_dir),
    "total_symmetric_difference": sum(t["symmetric_difference"] for t in both_dir),
    "per_instance": both_dir,
}
print(
    "exhaustive 2-D: total symmetric difference between the eps-stable set and the "
    "eps'-VI set = %d (out of %d points x %d instances)"
    % (
        sum(t["symmetric_difference"] for t in both_dir),
        grid.shape[0],
        len(both_dir),
    )
)


# ---- 1c. round trip through an actual solver (projected extragradient on the VI)
def extragradient(A, b, iters=20000, step=0.2, x0=None, rng=None):
    d = A.shape[0]
    x = box_proj(rng.uniform(0, 1, size=d) if x0 is None else x0)
    for _ in range(iters):
        y = box_proj(x - step * (A @ x + b))
        x = box_proj(x - step * (A @ y + b))
    return x


roundtrip = []
for d in [2, 5, 20]:
    for trial in range(10):
        A, b = random_affine_vi(d, rng)
        eps = 1e-3
        g, c, _ = build_instance(A, b, eps, float(eps_p))
        xs_ = extragradient(A, b, rng=rng)
        vg = box_vi_gap(xs_, A @ xs_ + b)
        pg = perf_stability_gap(xs_, g)
        # fixed-point gap of RRM at the solution (Lemma G.1: <= sqrt(eps/alpha))
        fp = float(np.linalg.norm(xs_ - rrm_map(xs_, g)))
        roundtrip.append(
            {
                "d": d,
                "vi_gap": vg,
                "perf_gap": pg,
                "eps": eps,
                "perf_gap_le_eps": bool(pg <= eps),
                "vi_gap_le_eps_prime": bool(vg <= float(eps_p)),
                "rrm_fixed_point_gap": fp,
                "lemma_G1_bound_sqrt_eps_over_alpha": float(np.sqrt(eps)),
                "lemma_G1_holds": bool(fp <= np.sqrt(eps) + 1e-12),
            }
        )
res["solver_round_trip"] = roundtrip
print(
    "solver round trip: %d/%d solved instances satisfy both eps-stability and "
    "eps'-VI; Lemma G.1 bound holds in %d/%d"
    % (
        sum(r["perf_gap_le_eps"] and r["vi_gap_le_eps_prime"] for r in roundtrip),
        len(roundtrip),
        sum(r["lemma_G1_holds"] for r in roundtrip),
        len(roundtrip),
    )
)


# --------------------------------------------------------------------------
# 2. rho = L beta / alpha <= 1 + eps/eps'
# --------------------------------------------------------------------------
# alpha and beta of l(x;z) = 1/2||x-z||^2 : Hessian_x = I -> alpha = beta = 1,
# and ||grad_x l(x;z) - grad_x l(x;z')|| = ||z-z'|| -> beta = 1 (tight).
rho_checks = []
worst_ratio = 0.0
for d in [2, 5, 10, 50]:
    for trial in range(250):
        A, b = random_affine_vi(d, rng)
        c = 1e-2
        M = np.eye(d) - c * A
        L = float(np.linalg.norm(M, 2))  # exact Lipschitz constant of the affine g
        bound = 1 + c
        schur = float(np.sqrt(norm1(A) * norminf(A)))
        rho_checks.append(
            {
                "d": d,
                "L": L,
                "bound_1_plus_c": bound,
                "ok": bool(L <= bound + 1e-12),
                "spec_le_schur": bool(np.linalg.norm(A, 2) <= schur + 1e-12),
            }
        )
        worst_ratio = max(worst_ratio, L / bound)
# tightness: A = -I attains L = 1 + c exactly (and ||A||_1 = ||A||_inf = 1)
d = 8
c = 1e-2
A_tight = -np.eye(d)
L_tight = float(np.linalg.norm(np.eye(d) - c * A_tight, 2))
res["rho_bound"] = {
    "alpha": 1.0,
    "beta": 1.0,
    "n_random_checks": len(rho_checks),
    "all_within_bound": all(r["ok"] for r in rho_checks),
    "spectral_le_sqrt_1_inf_always": all(r["spec_le_schur"] for r in rho_checks),
    "worst_L_over_bound": worst_ratio,
    "tight_example": {
        "A": "-I",
        "c": c,
        "L": L_tight,
        "bound": 1 + c,
        "gap": abs(L_tight - (1 + c)),
    },
}
print(
    "rho bound: %d/%d random instances satisfy L <= 1+c; worst L/(1+c) = %.6f; "
    "A=-I attains equality (|L-(1+c)| = %.2e)"
    % (
        sum(r["ok"] for r in rho_checks),
        len(rho_checks),
        worst_ratio,
        abs(L_tight - (1 + c)),
    )
)


# --------------------------------------------------------------------------
# 3. boundary audit of the scaling constant
# --------------------------------------------------------------------------
# The theorem is typeset as rho <= 1 + eps/eps' (a stacked fraction; pdftotext
# collapses it to "eps eps'").  We check executably which reading is the correct
# one, by asking what VI accuracy each scaling actually buys.
audit = {}
d = 6
A, b = random_affine_vi(d, rng)
eps = 1e-3
for name, c in [
    ("c = eps/eps'  (fraction reading)", eps / float(eps_p)),
    ("c = eps*eps'  (product reading)", eps * float(eps_p)),
]:
    g = lambda x, c=c: (np.eye(d) - c * A) @ x - c * b
    # implied VI accuracy for an eps-performatively stable point is eps/c
    implied = eps / c
    # explicit witness: a point that is eps-stable but far from an eps'-VI point
    x = box_proj(rng.uniform(0, 1, size=d))
    for _ in range(200):  # push it to a *bad* VI point while staying eps-stable
        x = box_proj(x + 0.05 * (A @ x + b))
    audit[name] = {
        "c": c,
        "implied_vi_accuracy_eps_over_c": implied,
        "usable_for_lemma_3_3": bool(implied <= float(eps_p) + 1e-12),
        "witness_perf_gap": perf_stability_gap(x, g),
        "witness_vi_gap": box_vi_gap(x, A @ x + b),
        "witness_is_eps_stable": bool(perf_stability_gap(x, g) <= eps),
        "witness_is_eps_prime_vi": bool(box_vi_gap(x, A @ x + b) <= float(eps_p)),
        "rho_bound": 1 + c,
    }
res["scaling_audit"] = audit
for k, v in audit.items():
    print(
        "  %-34s c=%.3e -> implied VI accuracy %.4g (need <= %.4g): %s"
        % (
            k,
            v["c"],
            v["implied_vi_accuracy_eps_over_c"],
            float(eps_p),
            "OK" if v["usable_for_lemma_3_3"] else "VACUOUS",
        )
    )


# --------------------------------------------------------------------------
# 3b. provenance of the constant 0.088/6, re-derived symbolically
# --------------------------------------------------------------------------
# Pure-Circuit (Deligkas, Fearnley, Hollender, Melissourgos, JACM 2024), Thm 4.4:
#   "It is PPAD-hard to find an eps-NE in a polymatrix game for all
#    eps < 2*sqrt(73) - 17 ~= 0.088, even in degree-3 bipartite games with two
#    strategies per player."
# Bernasconi et al. (arXiv:2411.03248v1) Thm 4.4 reduces degree-3 polymatrix to
# affine VI on the hypercube, dividing the operator by 6 to force
# ||D||_1, ||D||_inf <= 1, hence  rho* = eps*/6.
thr = 2 * sp.sqrt(73) - 17
res["constant_provenance"] = {
    "pure_circuit_threshold_exact": str(thr),
    "pure_circuit_threshold_float": float(thr),
    "paper_uses_0_088": True,
    "0.088_admissible_strictly_below_threshold": bool(sp.Rational(88, 1000) < thr),
    "margin": float(thr - sp.Rational(88, 1000)),
    "bernasconi_normalisation_divisor": 6,
    "reason_for_6": (
        "degree-3 graph and alpha_ij in [-2,2] give row/column absolute sums <= 6; "
        "dividing the operator by 6 enforces ||D||_1, ||D||_inf <= 1 and rescales "
        "the additive error by the same factor (rho* = eps*/6)."
    ),
    "eps_prime_from_exact_threshold": float(thr / 6),
    "eps_prime_from_rounded_0.088": float(eps_p),
    "difference": float(abs(thr / 6 - eps_p)),
    "conclusion": (
        "0.088/6 is a valid (slightly conservative) instantiation: 0.088 < "
        "2*sqrt(73)-17 = 0.0880075, so the strict inequality of Pure-Circuit Thm 4.4 "
        "is respected with only 7.5e-6 of slack. Neither cited paper states the "
        "value 0.088/6 itself; it must be composed from Bernasconi's *proof*."
    ),
}
print(
    "3b. constant chain: 0.088 < 2sqrt(73)-17 = %.7f (margin %.2e); "
    "0.088/6 = %.7f vs exact/6 = %.7f"
    % (float(thr), float(thr - sp.Rational(88, 1000)), float(eps_p), float(thr / 6))
)


# --------------------------------------------------------------------------
# 4. symbolic re-derivation of the proof chain (sympy)
# --------------------------------------------------------------------------
e, ep, cc = sp.symbols("epsilon epsilon_prime c", positive=True)
x1, xs1, a11, b1 = sp.symbols("x xstar a b", real=True)
# 1-D symbolic instance: g(x) = (1-c a) x - c b ; grad = x* - g(x*) = c(a x* + b)
grad = xs1 - ((1 - cc * a11) * xs1 - cc * b1)
res["symbolic"] = {
    "grad_simplifies_to": str(sp.simplify(grad)),
    "equals_c_times_F": bool(sp.simplify(grad - cc * (a11 * xs1 + b1)) == 0),
    "solve_c_for_eps_prime_target": str(sp.solve(sp.Eq(e / cc, ep), cc)),
}
print(
    "symbolic: grad = %s ; c solving eps/c = eps' is c = %s"
    % (
        res["symbolic"]["grad_simplifies_to"],
        res["symbolic"]["solve_c_for_eps_prime_target"],
    )
)

res["verdict"] = {
    "reduction_correct": bool(
        ident.max() < 1e-9
        and sum(t["symmetric_difference"] for t in both_dir) == 0
        and all(r["ok"] for r in rho_checks)
    ),
    "constant_arithmetic_correct": bool(round(float(eps_p), 4) == 0.0147),
    "note": (
        "PPAD-hardness itself is inherited from Lemma 3.3 (Bernasconi et al. 2024) "
        "and is not executable; what is verified here is that the reduction of "
        "Theorem 3.4 is solution-preserving in both directions with the stated "
        "rho bound."
    ),
}
dump("claim1_thm34_reduction.json", res)