Answer: Polynomial-time solvable; the exact core is always nonempty.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe core of the multicommodity flow game with transferable pay- offis non-empty. Furthermore, a payoffallocation in the core can be computed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an explicit finite routing-role graph, rational type masses \(\mu_t\), per-unit capacities \(c_t\), symmetric demand densities \(d_{tu}\), and allowed route templates, define \(V(z)\) as the maximum routed flow for a coalition with type masses \(0\le z_t\le\mu_t\), capacities \(c_tz_t\), and pair demands \(d_{tu}z_tz_u\) for distinct types and \(d_{tt}z_t^2/2\) within a type. Compute nonnegative per-unit payoffs \(p_t\) such that \(\sum_t\mu_tp_t=V(\mu)\) and \(\sum_tz_tp_t\ge V(z)\) for every coalition vector \(z\).
A society is given by its support: \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
The input includes an undirected routing graph on these types (loops permitted), nonnegative binary-rational per-unit capacities \(c_t\), symmetric nonnegative binary-rational demand densities \(d_{tu}\), and explicitly listed route templates. A template is a graph walk with at least two vertex occurrences, whose endpoints specify its unordered commodity; equal endpoint types represent distinct agents of that type.
Let \(\mathcal P_{tu}\) be the templates for commodity \(\{t,u\}\), and let \(a_{tP}\) count occurrences of type \(t\) in template \(P\), including endpoints. Each occurrence consumes capacity; there are no edge capacities.
For every real coalition vector \(0\le z\le\mu\), only templates whose types have positive coalition mass are available. Define \(D_{tu}(z)=d_{tu}z_tz_u\) for \(t\ne u\), and \(D_{tt}(z)=d_{tt}z_t^2/2\).
Define \(V(z)=\max\{\sum_P f_P: f_P\ge0,\ \sum_P a_{tP}f_P\le c_tz_t\ \forall t,\ \sum_{P\in\mathcal P_{tu}}f_P\le D_{tu}(z)\ \forall t\le u\}\). Each unordered commodity contributes once to the objective.
The exact core-allocation problem asks for rational per-unit payoffs \(p_t\ge0\) satisfying \(\sum_t\mu_tp_t=V(\mu)\) and \(\sum_tz_tp_t\ge V(z)\) for every real \(0\le z\le\mu\), or a determination that no such allocation exists.
Is this exact core-allocation problem solvable in polynomial time, or is it NP-hard? State running times in \(m,\tau,R,L\), where \(m\) is the graph encoding length, \(R\) is the total number of listed template vertex occurrences, and \(L\) is the total binary input length.
For the discrete transferable-payoff multicommodity flow game with node capacities, pair demands, and coalitions restricted to their induced graphs, the core is always nonempty and an allocation is computable in polynomial time ([Markakis–Saberi](https://www.sciencedirect.com/science/article/abs/pii/S0167923604001691)). No result settling this precise continuous mass model was located.
The exact core-allocation problem is polynomial-time solvable. Its core is always nonempty. One optimal solution of the grand-coalition LP dual yields a rational allocation satisfying every real coalition constraint.
The proof below applies to the stated continuous mass model, including repeated template occurrences, loops, and equal endpoint types.
Let \(\mathcal P\) be the set of listed templates, and let \(k(P)\) denote the unordered endpoint commodity of template \(P\).
The LP defining \(V(\mu)\) is feasible because the zero flow is feasible. It has a finite attained optimum: every variable \(f_P\) is bounded above by the finite demand \(D_{k(P)}(\mu)\), so its feasible region is compact.
Introduce dual variables \(y_t\ge0\) for type capacities and \(q_{tu}\ge0\) for unordered commodity demands. The dual is
\(\displaystyle \min\left\{\sum_t c_t\mu_t y_t+\sum_{t\le u}D_{tu}(\mu)q_{tu}:\ \sum_t a_{tP}y_t+q_{k(P)}\ge1\ \text{for every }P,\ y,q\ge0\right\}.\)
For example, setting every \(y_t=1\) and every \(q_{tu}=0\) is feasible, because each template has at least two occurrences. By LP strong duality, an optimal dual solution satisfies
\(\displaystyle \sum_t c_t\mu_t y_t+\sum_{t\le u}D_{tu}(\mu)q_{tu}=V(\mu).\)
Fix a rational optimal dual solution. Section 5 establishes that one can be computed exactly in polynomial time.
Fix any real coalition vector \(0\le z\le\mu\), and any flow feasible for that coalition. Dual feasibility and nonnegativity give
\(\displaystyle \sum_P f_P\le\sum_P\left(\sum_t a_{tP}y_t+q_{k(P)}\right)f_P.\)
Reordering the finite sums and applying the coalition’s capacity and demand constraints yields
\(\displaystyle \sum_P f_P\le\sum_t c_tz_ty_t+\sum_{t\le u}D_{tu}(z)q_{tu}.\)
Consequently,
\(\displaystyle V(z)\le\sum_t c_tz_ty_t+\sum_{t\le u}D_{tu}(z)q_{tu}.\)
This argument respects template availability. Indeed, if \(z_t=0\), the capacity constraint for type \(t\) reads \(\sum_P a_{tP}f_P\le0\). Since its summands are nonnegative, every template containing \(t\) must have zero flow. Thus unavailable templates may equivalently be retained with zero flow.
For distinct types \(t,u\), put \(x=z_t/\mu_t\) and \(w=z_u/\mu_u\). The positive support masses make these ratios well defined, and \(x,w\in[0,1]\). Hence
\(\displaystyle x+w-2xw=x(1-w)+w(1-x)\ge0.\)
Multiplying by the nonnegative quantity \(d_{tu}\mu_t\mu_u/2\) gives
\(\displaystyle D_{tu}(z)=d_{tu}z_tz_u\le\frac{d_{tu}}2(\mu_u z_t+\mu_t z_u).\)
For a diagonal commodity, \(z_t^2\le\mu_tz_t\), and therefore
\(\displaystyle D_{tt}(z)=\frac{d_{tt}z_t^2}{2}\le\frac{d_{tt}\mu_t}{2}z_t.\)
Both bounds are equalities when \(z=\mu\). This equality is what allows us to obtain an efficient allocation while covering every coalition.
Use the symmetric notation \(q_{ut}=q_{tu}\). Define
\(\displaystyle p_t=c_ty_t+\frac12\sum_{u\ne t}d_{tu}\mu_uq_{tu}+\frac12d_{tt}\mu_tq_{tt}.\)
Every term is nonnegative, so \(p_t\ge0\).
Efficiency. In the sum \(\sum_t\mu_tp_t\), each distinct-endpoint commodity receives two contributions of \(d_{tu}\mu_t\mu_uq_{tu}/2\), while each diagonal commodity receives \(d_{tt}\mu_t^2q_{tt}/2\). Thus
\(\displaystyle \sum_t\mu_tp_t=\sum_t c_t\mu_ty_t+\sum_{t<u}d_{tu}\mu_t\mu_uq_{tu}+\sum_t\frac{d_{tt}\mu_t^2}{2}q_{tt}=V(\mu).\)
The last equality is grand-coalition strong duality.
Every coalition constraint. For arbitrary real \(0\le z\le\mu\), the same regrouping gives
\(\displaystyle \sum_tz_tp_t=\sum_t c_tz_ty_t+\sum_{t<u}\frac{d_{tu}q_{tu}}2(\mu_uz_t+\mu_tz_u)+\sum_t\frac{d_{tt}\mu_tq_{tt}}2z_t.\)
By Section 3 and \(q_{tu}\ge0\), this is at least
\(\displaystyle \sum_t c_tz_ty_t+\sum_{t\le u}D_{tu}(z)q_{tu},\)
which is at least \(V(z)\) by Section 2. Therefore the constructed allocation lies in the exact core.
Let \(K=|\mathcal P|\), and let \(Q\) be the number of commodities having at least one template. Demand constraints for commodities without templates can be omitted, with their dual variables set to zero. Because each template has at least two occurrences,
\(\displaystyle K\le R/2,\qquad Q\le K.\)
The resulting dual has \(N=\tau+Q\) variables and \(K\) template inequalities.
For completeness, this dual can be restricted to the cube \(0\le(y,q)\le1\) without changing its optimum. To see this, clip each coordinate exceeding one to one. In any affected template inequality, that coordinate has a positive integer coefficient: either an occurrence count \(a_{tP}\ge1\), or the commodity coefficient one. Its clipped contribution alone is therefore at least one. Every unaffected inequality remains unchanged. Clipping preserves feasibility and cannot increase the objective, whose coefficients are nonnegative.
The restricted dual is consequently a nonempty compact rational polytope. It has a rational optimal vertex. Its constraint coefficients are integers of absolute value at most \(\max\{1,R\}\), and its right-hand sides are zero or one. Cramer’s rule and Hadamard’s determinant bound show that each coordinate of a vertex has binary encoding length
\(\displaystyle O\!\left(N\bigl(\log(N+1)+\log(R+1)\bigr)\right).\)
The objective coefficients \(c_t\mu_t\) and \(D_{tu}(\mu)\) have encoding length \(O(L)\) each, because they are products of at most three input rationals, with an optional factor \(1/2\).
Thus a dense encoding of the restricted dual has length at most
\(\displaystyle B=O\!\left((\tau+R)^2\log(R+2)+(\tau+R)(L+1)\right).\)
Exact rational LP optimization is polynomial in the LP encoding length; this concerns exact solutions, rather than merely approximate objective values. See [Gleixner–Steffy, Section 1.3](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf).
The algorithm therefore consists of preprocessing the listed templates, solving one rational LP, and evaluating the payoff formula. Including reading the graph encoding, its bit running time is
\(\displaystyle m+\operatorname{poly}(B+L+\tau+R)=\operatorname{poly}(m+\tau+R+L).\)
The output payoffs have polynomial binary length. If there are no templates, the algorithm simply returns \(p_t=0\) for every type.
No coalition enumeration or coalition-separation oracle is required: the proved demand inequalities certify all real coalition constraints simultaneously.
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated problem. The allocation construction is correct for every real coalition, and the exact computation has polynomial bit complexity. I found no major or minor mathematical issues.
The primal feasibility and boundedness arguments are valid. Zero flow is feasible. For each template \(P\), nonnegativity and its commodity demand constraint imply
\[
0\le f_P\le D_{k(P)}(\mu).
\]
All demands are finite, and there are finitely many explicitly listed templates. Thus the feasible region is closed and bounded, and the objective attains a finite maximum.
The displayed dual is correct:
The proposed dual feasible point is valid because \(\sum_t a_{tP}\ge2\). The hypotheses for finite-dimensional LP strong duality are satisfied, so the asserted equality of optimal objective values is justified. Rational optimal-solution existence and computation are addressed in Section 5.
Finding: Correct.
Multiplying each dual template inequality by \(f_P\ge0\) preserves its direction. Summing and regrouping is valid because the template set is finite. Applying the coalition constraints is valid because \(y_t,q_{tu}\ge0\).
The resulting bound
\[
V(z)\le \sum_t c_tz_ty_t+\sum_{t\le u}D_{tu}(z)q_{tu}
\]
therefore holds for every real \(z\) in the specified box. This argument requires no rationality assumption on \(z\).
The template-availability argument is also correct. If \(z_t=0\), then the capacity constraint has right-hand side zero. Every template containing \(t\) has \(a_{tP}>0\), so nonnegative flows force its flow to vanish. This remains true when \(c_t=0\).
Repeated occurrences, loops, and equal endpoints cause no discrepancy: their capacity consumption is already represented by the occurrence counts.
Finding: Correct.
For distinct types, positivity of \(\mu_t,\mu_u\) makes the ratios well defined. The bounds \(0\le z\le\mu\) give \(x,w\in[0,1]\). The identity
\[
x+w-2xw=x(1-w)+w(1-x)
\]
and its nonnegativity are correct. Multiplication by \(d_{tu}\mu_t\mu_u/2\ge0\) produces exactly the claimed bound, with the correct factor of one half.
For diagonal commodities, \(z_t^2\le\mu_tz_t\) follows from \(0\le z_t\le\mu_t\). The diagonal demand bound correctly retains its defining factor of one half.
Both inequalities are equalities at \(z=\mu\), including when a demand density is zero.
Finding: Correct.
The definition of \(p_t\) is unambiguous under the stated symmetric convention for \(q_{tu}\). Every summand is nonnegative.
The efficiency computation counts each off-diagonal commodity exactly twice, with one half of its grand-coalition demand contribution assigned to each endpoint type. Each diagonal commodity contributes exactly once with the required factor of one half. Consequently,
\[
\sum_t\mu_tp_t=V(\mu).
\]
For an arbitrary coalition, the regrouped payoff formula is correct. The demand inequalities can be multiplied by \(q_{tu}\) because these variables are nonnegative. Combining them with Section 2 gives
\[
\sum_tz_tp_t\ge V(z).
\]
The quantifier is genuinely over all real coalitions in the box. No coalition enumeration, separation procedure, or restriction to rational coalitions is hidden in the argument.
Finding: Correct; the constructed allocation satisfies every requested condition.
The size estimates \(K\le R/2\) and \(Q\le K\) are correct. Commodities without templates have identically zero primal flow sums, so omitting their demand constraints and setting their dual variables to zero is valid.
The clipping argument is sound. If a clipped coordinate occurs in a template inequality, its coefficient is a positive integer. After clipping, that contribution alone is at least one; all remaining contributions remain nonnegative. An inequality containing no clipped coordinate is unchanged. Nonnegative objective coefficients ensure that clipping cannot increase the objective.
Thus the bounded dual has the same optimum and is a nonempty compact rational polytope. An optimal vertex exists. The asserted coordinate-length bound follows from the stated integer coefficient and right-hand-side bounds using Cramer’s rule and Hadamard’s inequality.
The objective coefficients have encoding length \(O(L)\): each uses at most three input rational factors and possibly division by two. The stated dense encoding bound accounts for the template inequalities, coordinate bounds, and objective coefficients.
The invoked exact rational LP theorem applies to an explicitly encoded rational LP and returns an exact optimal solution in polynomial bit time. The cited [Gleixner–Steffy Section 1.3](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf) explicitly confirms this exact, rather than approximate, polynomial-time guarantee. Its hypotheses are satisfied here.
Evaluating the payoff formula uses polynomially many rational arithmetic operations on numbers of polynomial encoding length. Therefore the running-time claim
\[
m+\operatorname{poly}(B+L+\tau+R)
=\operatorname{poly}(m+\tau+R+L)
\]
is justified. It is a polynomial bit-complexity claim, without an asserted specific exponent.
The no-template case is handled correctly: all coalition values are zero, and the zero allocation satisfies the requirements.
Finding: Correct.
The proof establishes polynomial-time exact core allocation and universal core nonemptiness for the precise continuous mass model. It does not rely on extending the discrete-game result cited in the task.
No additional mathematical clarification or repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.