\section{A weighted comparison of the path matchings}
\label{sec:general-path-full-budget}
The path comparison in Section~\ref{sec:general-path-packing} bounds
the initial matching and the matching obtained from disjoint paths
separately. Both bounds depend on the same deviations $Q,R$ of the
matching-class and layer masses. Keeping those common terms while
taking a weighted average gives a stronger estimate. Use the notation
of that section, including a maximal path packing of mass $\mu$, and
define
\[
 P(x,\mu)=\frac{(x-\mu)^2}{b}-\frac{x^2}{k},\qquad
 h(\mu)=c\mu^2-d\mu,\quad
 c=\frac12\left(1-\frac2{b+1}\right)^2,\quad d=\frac4{b+1}.
\]
The two actual matchings satisfy
\[
 C_0\le1-1/S-Q-R-E+o(1),\qquad
 C_{\rm path}\le1-1/S-Q-R-h(\mu)+o(1).
\]
Moreover $R+E\ge P(x,\mu)-o(1)$ by
\eqref{eq:general-path-resource}. For any $0\le\lambda\le1$, give
weight $\lambda$ to the original matching and $1-\lambda$ to the
path matching. Since $R\ge0$,
\[
 Q+R+\lambda E+(1-\lambda)h
 \ge Q+\lambda P+(1-\lambda)h-o(1).
\]
In particular, the terms $Q$ and $R$ are used only once in this
comparison.

Put
\[
 q_0=\frac{S}{k(S-k)},\qquad x_0=\frac{k}{S},\qquad
 K_0=\frac{k}{S(S-k)},
\]
and define the symmetric matrix and vector
\begin{equation}\label{eq:general-budget-matrix}
 M_\lambda=
 \begin{pmatrix}
 q_0+\lambda(1/b-1/k)&-\lambda/b\\
 -\lambda/b&\lambda/b+(1-\lambda)c
 \end{pmatrix},\qquad
 v_\lambda=
 \begin{pmatrix}1/(S-k)\\(1-\lambda)d/2\end{pmatrix}.
\end{equation}
Then the loss is at least
\[
 q_0(x-x_0)^2+\lambda P(x,\mu)+(1-\lambda)h(\mu)
 =\begin{pmatrix}x&\mu\end{pmatrix}M_\lambda
   \begin{pmatrix}x\\\mu\end{pmatrix}
 -2v_\lambda^T\begin{pmatrix}x\\\mu\end{pmatrix}+K_0.
\]
Both endpoint matrices are positive definite:
$M_0=\operatorname{diag}(q_0,c)$, and
$\det M_1=1/[b(S-k)]>0$.
Thus $M_\lambda\succ0$ throughout $[0,1]$.
Completing the square, without imposing additional restrictions on
$x$ or $\mu$, gives the following theorem.

\begin{theorem}\label{thm:general-full-budget}
For every integer $k/2\le b<k$ and every $\lambda\in[0,1]$, set
\[
 \Delta_b(\lambda)=K_0-v_\lambda^TM_\lambda^{-1}v_\lambda.
\]
Then
\[
 \boxed{\gamma(\ell)\le
 \frac12-\frac1{2S}-\frac12\Delta_b(\lambda).}
\]
All entries are rational when $\lambda$ is rational. The bound is
uniform in $N\ge2M$ and uses the original matching order.
\end{theorem}

For fixed $\ell$ and $b$, the best weight in this theorem can be
found by solving a polynomial of degree at most four. Write
\[
 D(\lambda)=\det M_\lambda,\qquad
 N(\lambda)=(M_\lambda)_{22}(v_\lambda)_1^2
 -2(M_\lambda)_{12}(v_\lambda)_1(v_\lambda)_2
 +(M_\lambda)_{11}(v_\lambda)_2^2.
\]
Here $D$ has degree at most two and $N$ degree at most three, and
\[
 \Delta_b(\lambda)=K_0-\frac{N(\lambda)}{D(\lambda)}.
\]
Its stationary equation is the explicit quartic
\begin{equation}\label{eq:general-budget-quartic}
 N(\lambda)D'(\lambda)-N'(\lambda)D(\lambda)=0.
\end{equation}
The function $\Delta_b$ is concave: before minimizing in $(x,\mu)$,
the displayed loss is affine in $\lambda$, and an infimum of affine
functions is concave. Thus an interior stationary point is a global
maximum. If the derivative has opposite signs at the endpoints,
the maximum is the unique stationary point; uniqueness follows also
from analyticity, since a nonconstant analytic concave function cannot
have an interval of maxima. Otherwise the appropriate endpoint is
used. This describes the optimum for each fixed $b$ exactly.

The accompanying checker sets $b=k/2$, reconstructs the quartic with
rational coefficients, isolates its maximizing root by exact rational
bisection, and verifies rational weights arbitrarily close to it.
The finite bounds in the introduction use these rational weights
when they improve the estimate from
Theorem~\ref{thm:general-clean-criterion}. The optimization concerns
only the weight of these two matching comparisons for the fixed
path length $b$.

The weighted comparison also determines the next term in an
asymptotic upper bound. Substitute $b=k/2$ and
$\lambda=1-\sqrt{8/k}$ into the rational formula. Expansion of its
two-by-two inverse gives
\[
 \Delta_{k/2}(\lambda)=\frac1{15k}
 -\frac{4\sqrt2}{25k^{3/2}}+O\!\left(\frac{\log k}{k^2}\right).
\]
Thus
\[
 \gamma(\ell)\le\frac12-\frac1{5k}
 +\frac{2\sqrt2}{25k^{3/2}}
 +O\!\left(\frac{\log k}{k^2}\right).
\]
For example, this expansion can be checked after writing
$\varepsilon=1-\lambda$: the first two losses below $1/(15k)$ are
$\varepsilon/(25k)$ and $8/(25\varepsilon k^2)$, whose sum is
minimized at $\varepsilon=\sqrt{8/k}$.
This expansion includes its correction terms; it does not assert
the finite inequality $\gamma(\ell)\le1/2-1/(5k)$.