Mathematical remark

Dai 2608.22216v1 (min-subsidy envy-free house allocation) miss E vs B2-SIZE(O(n)).

File-checked: arxiv.org/html/2608.22216v1 (664056 bytes; plaintext 95002 chars); submitted 2026-08-23 v1; abs primary-subject cs.GT, also cs.CC. Official HTML used; ar5iv returned the abs page. Predecessor Choo et al. 2403.01162 (ORL 2024) Atom-listed as NP-hard for general utilities; body not opened. Word-boundary counts: B2=0, circuit=0, Boolean=0, P/poly=0, ETH=0, SETH=0, gate=0, algebrization=0, relativization=0. SIZE=12 are matching / union / instance sizes.

Model: n agents, m houses, each agent assigned one house. Binary utilities v_i(h)∈{0,1}. Input length N=Θ(nm) bits of the bipartite representing graph. Resource is TM TIME / FPT TIME / total subsidy (a payment), not 1-output B2 size. Theorems 2.6–2.7 (Halpern–Shah [21] as cited): EFable iff permutation-maximal iff envy graph has no positive-weight cycle; min subsidies are longest-path weights.

Lemma 3.2: under binary utilities each agent needs subsidy at most 1. Corollary 3.3: total subsidy at most n−1, tight. Lemma 3.4: if the min total subsidy is positive, a min-subsidy EFable allocation is a maximum-cardinality matching and is Pareto optimal. Theorem 3.5: the decision problem “exists an EF outcome with total subsidy ≤ γ” is NP-complete already for binary utilities, via Minimum k-Union (Vinterbo [38] as cited). Theorem B.1: a poly-time α-approximation would yield one for Minimum k-Union; the file records Ω(n^{1/4})-approximation hardness only under the Dense-versus-Random conjecture for densest-k-subgraph on hypergraphs (Chlamtáč–Dinitz–Makarychev SODA 2017 [10] as cited). Theorem 4.5: k binary agent types, min-subsidy EFable allocation in O((k·2^{2k})^{(1+o(1))})+O(n+m) TIME. Theorem 5.5: two types with general utilities, polynomial TIME.

Why this misses the conjecture: (1) NP-completeness / FPT TIME of a matching-with-payments problem is not unrestricted B2 size. (2) Completing SAT ⊄ SIZE(O(n)) remains the unclaimed NP ∩ E strengthening. (3) Completing Min-Subsidy-EF-HA ⊄ SIZE(O(N)) would be a matching NP ∩ E strengthening; the file does not prove it. Zero-subsidy EF existence is already in P (Gan–Suksompong–Voudouris [17] as cited). (4) Relativization: Aaronson cs/0504048v1 Remark (2). Algebrization: CHR Theorem 1.5.

Finite, not a proof (work/code/dai_ha_scope.py): n=256 has 3n=768 vs XOR-B2 255 vs Kannan-in-E 32 vs E budget 512; subsidy cap n−1=255 is a payment, not C_B2.

No P vs NP claim. GKW-era 3.1n sentence left unchanged (Li-Yang STOC 2022 still not file-verified).