Answer: Polynomial-time solvable exactly in \((m+\tau+s+L)^{O(1)}\) bit operations.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe message from prosumer j to its in-neighbor parent p j defined in equation 7 can be assessed as µ j→pj = o j · Y k∈out(j) µj→k · Y i∈in(j)\{pj} µi→j [Dpj j] (10) and the message from prosumer j to its out-neighbor parent p j de- fined in equation 6 can be assessed as µ j→pj = oj · Y k∈out( j)\{pj} µ j→k · Y i∈in(j) µi→j [−D jpj]. (11) Furthermore, the computational complexity of assessing each mes- sage is O(N jC jnoj + N2 jC2 j) where N j is the number of neighbors of j and C j is the largest capacity of any of the links connected to j.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a radial feeder \(H=(V,E)\), finite types \(T\) located at feeder nodes, rational masses \(\mu_t\) summing to \(1\), and each type’s finite integral offer menu \(Q_t\subseteq\mathbb{Z}\) with rational utilities \(u_t(q)\), compute a welfare-maximizing allocation of mass to offers and signed edge flows. The allocation variables \(a_{tq}\geq 0\) must satisfy \(\sum_{q\in Q_t}a_{tq}=\mu_t\); at each node \(v\), incoming flow minus outgoing flow must equal \(\sum_{t\in T_v}\sum_{q\in Q_t}q\,a_{tq}\); and each edge flow must satisfy \(|f_e|\leq\kappa_e\), where \(\kappa_e\) is capacity per unit of normalized population. The objective is to maximize \(\sum_t\sum_{q\in Q_t}a_{tq}u_t(q)\).
Let \(H=(V,E)\) be a finite undirected tree with \(m=|V|\), arbitrarily oriented for recording signed flows. Each edge has a binary-rational capacity \(\kappa_e\geq0\), measured per unit of normalized population; there is no external energy supply or disposal.
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Each type has a specified node \(\ell(t)\in V\) and an explicitly listed finite menu \(Q_t\subseteq\mathbb Z\) containing \(0\), with values \(u_t(q)\in\mathbb Q\) of either sign, including a finite value at \(0\). Positive quantities mean consumption and negative quantities mean production; unlisted quantities are unavailable.
Mass may be divided among mutually exclusive offers: choose real \(a_{tq}\geq0\) and signed real flows \(f_e\) satisfying \(\sum_{q\in Q_t}a_{tq}=\mu_t\), \(|f_e|\leq\kappa_e\), and, at every node \(v\), \(\sum_{e\text{ entering }v}f_e-\sum_{e\text{ leaving }v}f_e=\sum_{t:\ell(t)=v}\sum_{q\in Q_t}q a_{tq}\). Zero net consumption permits energy relay.
The optimization problem is to compute an allocation and flows maximizing \(\sum_t\sum_{q\in Q_t}a_{tq}u_t(q)\). Let \(s=\sum_t|Q_t|\) and let \(L\) be the total binary input length; state running times in \(m,\tau,s,L\). Any maximizing allocation is acceptable.
Is this continuous energy-allocation problem solvable in polynomial time in \(m,\tau,s,L\), or is it NP-hard?
For discrete prosumers, [RadPro](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2015/aamas/p1285.pdf) computes each tree message in \(O(d_j C_j s_j+d_j^2C_j^2)\) operations, where \(d_j\) is node degree, \(C_j\) the largest incident integral capacity, and \(s_j\) the menu size; this is a numerical-capacity bound, not a polynomial binary-input bound.
A [continuous-energy follow-up](https://www.iiia.csic.es/media/filer_public/ea/e6/eae6d188-b1ca-4269-842b-5aaa99b707c8/5500.pdf) gives a mixed-integer formulation for individual prosumers with piecewise-linear valuations, rather than divisible type masses. No result settling exactly the mass-allocation problem above was located.
The problem is solvable exactly in polynomial time in \(m,\tau,s,L\). Divisible type masses make the stated optimization problem a rational linear program of polynomial encoding length.
Let \(B\) be the signed node-edge incidence matrix of the given orientation: for an edge \(e\) directed from \(x\) to \(y\), let \(B_{xe}=-1\), \(B_{ye}=1\), and all other entries in its column be zero.
Introduce one real variable \(a_{tq}\) for every explicitly listed offer \(q\in Q_t\), and one real variable \(f_e\) for every edge. Maximize
\( \displaystyle \sum_{t=1}^{\tau}\sum_{q\in Q_t}u_t(q)a_{tq} \)
subject to:
Every coefficient and right-hand side is rational. In particular, each quantity \(q\) is a fixed integer coefficient, so \(q\,a_{tq}\) is linear in the decision variables.
This formulation is exact: its feasible points are precisely the allocations and flows allowed by the question, and its objective is precisely their welfare. There are no integrality restrictions to enforce, because the premises explicitly allow each type’s mass to be divided among offers.
Summing all node equations cancels every flow term, since each column of \(B\) sums to zero. Thus every feasible point satisfies
\( \displaystyle \sum_{t=1}^{\tau}\sum_{q\in Q_t}q\,a_{tq}=0, \)
as required by the absence of external supply or disposal. The node equations also permit relay through a node with zero net consumption.
The feasible set is nonempty. Set \(a_{t0}=\mu_t\), set every other allocation variable to zero, and set every flow to zero. This is feasible because every menu contains \(0\) and every capacity is nonnegative.
Nonnegativity and the type-mass equations imply \(0\leq a_{tq}\leq\mu_t\leq 1\). Each flow lies in the finite interval \([-\kappa_e,\kappa_e]\). Consequently, the feasible set is bounded. It is also closed, being defined by finitely many linear equalities and non-strict inequalities.
The feasible set is therefore a nonempty compact polytope. The linear objective is continuous and hence attains a finite maximum. Negative utilities, including negative values at \(0\), do not affect this argument.
Because the graph is a tree, \(|E|=m-1\). The formulation has
\(n=s+m-1\)
variables. Replacing every equality by two inequalities gives
\(M=s+2(m-1)+2\tau+2m\)
inequalities, counting allocation nonnegativity and both flow bounds.
In a dense matrix representation, the total binary encoding length \(T\), including the objective, satisfies
\(T=O(L+Mn).\)
Indeed, each original numerical datum is copied only a constant number of times: quantities appear in the node constraints, masses in the type constraints, capacities in the flow bounds, and utilities in the objective. The remaining matrix entries are \(0\), \(1\), or \(-1\). Thus the formulation can be constructed in polynomial time in \(m,\tau,s,L\), without enumerating any intermediate quantity or capacity value.
We apply the standard exact rational linear-programming theorem: an explicitly given rational linear program can be solved in time polynomial in its binary encoding length, with an exact rational optimizer returned whenever the feasible set is nonempty and the optimum is finite. Exact polynomial-time methods are discussed in Section 1.3 of [*Linear Programming using Limited-Precision Oracles*](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf).
All hypotheses hold here: the formulation is explicit and rational, its encoding length is polynomially bounded, and Section 2 proves feasibility and a finite attained optimum. Redundant balance equations or zero capacities cause no difficulty; the theorem does not require a full-dimensional feasible set.
The resulting running time is
\((m+\tau+s+L)^{O(1)}\)
bit operations, and the returned coordinates directly give the requested maximizing allocation and flows.
For completeness, exact output has polynomial length as well. A bounded rational polytope has an optimal vertex. At a vertex, \(n\) linearly independent tight constraints determine the coordinates. Clearing denominators produces an integer system whose entries have \(O(L)\) bits. Hadamard’s inequality bounds the absolute values of its determinant and the column-replacement determinants by \(n^{n/2}2^{O(nL)}\). Cramer’s rule therefore gives each coordinate numerator and denominator with \(O(n(L+\log n))\) bits.
For an indivisible prosumer, selecting one offer requires a discrete choice. Here, the premise permits arbitrary nonnegative portions of a type’s mass to select different offers. The variables \(a_{tq}\) represent those portions directly.
Accordingly, neither a numerical-capacity dynamic program nor a mixed-integer formulation is needed for this mass-allocation model. Arbitrary menu values and large binary-encoded capacities remain coefficients and bounds in a polynomial-size linear program.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the stated mass-allocation problem: an exact maximizing allocation and flows can be computed in polynomially many bit operations in \(m,\tau,s,L\). No major or minor mathematical issues were found.
The incidence convention agrees with the task: an edge directed into a node contributes positively, and an edge directed out contributes negatively. Consequently, the displayed node equations have the correct signs.
There is one allocation variable for every available offer, and no variables for unavailable quantities. Nonnegativity and the type equations enforce precisely the permitted division of each type’s mass. The two flow bounds are equivalent to \(|f_e|\leq\kappa_e\).
All coefficients are rational. In particular, each \(q\) is input data, so the term \(q a_{tq}\) is linear. The objective matches the requested welfare exactly. No integrality condition is required or omitted.
Every incidence column has one entry \(1\) and one entry \(-1\). Summing the node equations therefore gives
\[
\sum_t\sum_{q\in Q_t}q a_{tq}=0.
\]
This correctly enforces the absence of external supply or disposal. A node with zero net consumption can have equal incoming and outgoing net flow, so the formulation also permits relay.
The proposed allocation using only offer \(0\), with every flow zero, satisfies all constraints. This uses exactly the stated hypotheses that each menu contains \(0\) and capacities are nonnegative.
From nonnegativity and the type equations, \(0\leq a_{tq}\leq\mu_t\leq1\). Every flow is bounded by its finite rational capacity. The feasible set is closed and bounded in finite-dimensional space and hence compact. The continuous linear objective therefore attains a finite maximum. Utilities of either sign cause no exception.
Since the tree has \(m-1\) edges, the number of variables is
\[
n=s+m-1.
\]
After replacing equalities by pairs of inequalities, the count is
\[
M=s+2(m-1)+2\tau+2m.
\]
The four contributions are allocation nonnegativity, flow bounds, type equations, and node equations, respectively. Redundancy does not invalidate these counts or the formulation.
Each listed quantity, mass, capacity, and utility occurs only a constant number of times in the constructed LP. Negation and equality duplication increase encoding length by only a constant factor. All remaining dense matrix entries have constant encoding length. Thus
\[
T=O(L+Mn)
\]
is justified.
Neither large capacities nor large quantities require enumeration of their numerical ranges. The construction is polynomial in the requested parameters.
The prover states the necessary theorem precisely: explicitly encoded rational LPs admit polynomial-time exact optimization when feasible with finite optimum. The formulation meets these hypotheses, as verified above.
The cited Section 1.3 does discuss exact polynomial-time algorithms for rational LPs, including recovery of exact rational solutions; it supports the theorem invoked here. The prover relies on that general result, rather than on the paper’s later conditional oracle algorithms. See [*Linear Programming using Limited-Precision Oracles*, Section 1.3](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf).
Lower-dimensional feasible sets, redundant equations, and zero capacities introduce no missing hypothesis. Therefore the claimed bound
\[
(m+\tau+s+L)^{O(1)}
\]
in bit operations follows.
A nonempty bounded polytope has an optimal vertex, and a vertex is determined by \(n\) independent tight constraints, including when the polytope is lower-dimensional. The denominator-clearing, Hadamard, and Cramer bounds stated in the output correctly give polynomial-length rational coordinates.
The one-node case, singleton menus, zero capacities, and negative utilities are all covered by the argument. The discussion of discrete prosumers correctly identifies divisibility as the relevant distinction and does not rely on the numerical-capacity dynamic-programming bound.
Actionable feedback: No repair or additional clarification is necessary. The formulation, theorem application, and complexity accounting establish the claimed result.
⟨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.