Answer: Unavoidable exponential-output obstruction: for polynomial-size acyclic instances, every explicit \(\epsilon\)-cover has at least \(2^\tau\) members whenever \(0<\epsilon<1/2\). Therefore no algorithm can compute such covers in time polynomial in \(m,\tau,d,L,1/\epsilon\).
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateGiven a factor graph, a solution x is Pareto optimal if and only if x is present in the marginal functions zj(xj) of all variables xj of the factor graph, once they have converged.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite water network with an acyclic factor graph, a large population of size \(N\), rational masses \(\mu_t\) over \(\tau\) user types, finite action menus \(D_t\), rational utilities \(f_t(a)\), physical flow constraints, and a piecewise-linear regulatory score \(G\), find a finite set of feasible allocations forming an \(\epsilon\)-cover of the Pareto-optimal objective vectors. An allocation has \(x_{t,a}\geq 0\), \(\sum_{a\in D_t}x_{t,a}=\mu_t\), total type withdrawal \(N\sum_{a\in D_t}a x_{t,a}\), and objectives \(U_t=\mu_t^{-1}\sum_{a\in D_t}x_{t,a}f_t(a)\) together with \(G\); normalize objective coordinates before measuring the cover.
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
The input includes a binary-encoded integer population scale \(N\geq1\), nonempty finite menus \(D_t\subset\mathbb{Q}_{>0}\), and rational utility tables \(f_t:D_t\to\mathbb{Q}\). Type descriptions specify where their actions withdraw or release water.
An allocation consists of divisible masses \(x_{t,a}\geq0\) satisfying \(\sum_{a\in D_t}x_{t,a}=\mu_t\), together with nonnegative physical flows \(z\). Its aggregate type actions are \(q_t=N\sum_{a\in D_t}a x_{t,a}\).
Feasibility requires the supplied rational linear flow-conservation, reservoir-availability, and capacity constraints on \((q,z)\); physical violations are forbidden. Normative requirements have supplied affine slacks \(\ell_j(q,z)\), with satisfaction meaning \(\ell_j(q,z)\geq0\), and regulatory score \(G(q,z)=\sum_j\min\{0,\ell_j(q,z)\}\).
The incidence graph between variable nodes (one allocation block per type and one node per auxiliary flow) and individual physical constraints, normative score terms, and unary type utilities must be acyclic. Assume the feasible set is nonempty and bounded.
Maximize all coordinates of \(F(x,z)=(U_1,\ldots,U_\tau,G)\), where \(U_t=\mu_t^{-1}\sum_{a\in D_t}x_{t,a}f_t(a)\). Supplied rational bounds \(b_i^-<b_i^+\) enclose each coordinate's feasible range; write \(\widehat F_i=(F_i-b_i^-)/(b_i^+-b_i^-)\).
For rational \(0<\epsilon<1\), an \(\epsilon\)-cover is a finite set \(S\) of rational feasible allocations such that every Pareto-optimal allocation \(p\) has some \(s\in S\) with \(\|\widehat F(p)-\widehat F(s)\|_\infty\leq\epsilon\). Let \(m\) count network vertices, edges, and local constraints, \(d=\sum_t|D_t|\), and \(L\) be the total input bit length; \(\tau\) is unrestricted.
Can such an \(\epsilon\)-cover be computed in time polynomial in \(m,\tau,d,L,1/\epsilon\), or is there an NP-hardness or unavoidable superpolynomial-output obstruction?
For the finite-domain acyclic model, Amigoni–Castelletti–Giuliani state that intersecting converged variable marginals characterizes exactly the Pareto-optimal allocations. [Source](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p821.pdf)
B-MOMS has a proved Pareto-optimality guarantee on acyclic finite-domain factor graphs. [Source](https://aamas.csc.liv.ac.uk/Proceedings/aamas2011/papers/A3_B52.pdf)
For continuous convex feasible regions with positive linear objectives and a fixed objective count, Papadimitriou–Yannakakis establish efficient multiplicative Pareto approximation under their single-objective approximation condition; this differs from the normalized metric cover above. [Source](https://www.cs.purdue.edu/homes/yexiang/courses/18fall-cs590/papers/papadimitriou2000.pdf)
There is an unconditional exponential-output obstruction. For infinitely many support sizes \(\tau\), there are instances of polynomial encoding length with \(d=2\tau\), \(m=O(\tau)\), and a connected acyclic incidence graph for which every \(\epsilon\)-cover has at least \(2^\tau\) members whenever \(0<\epsilon<1/2\).
Consequently, explicitly computing such a cover cannot take time polynomial in \(m,\tau,d,L,1/\epsilon\). This conclusion requires no complexity-theoretic assumption.
Let \(\tau=2^h\), where \(h\geq1\). There are exactly \(\tau\) supported types. Set
\(N=\tau,\qquad \mu_t=1/\tau,\qquad D_t=\{1,2\},\qquad f_t(1)=0,\qquad f_t(2)=1.\)
The masses are positive dyadic rationals and sum to \(1\).
For each type define \(y_t=\tau x_{t,2}\). The allocation constraints are equivalent to
\(0\leq y_t\leq1,\qquad x_{t,1}=(1-y_t)/\tau,\qquad x_{t,2}=y_t/\tau.\)
Therefore,
\(q_t=N(x_{t,1}+2x_{t,2})=1+y_t,\qquad U_t=\mu_t^{-1}x_{t,2}=y_t.\)
We now specify the water network. Each type withdraws from a separate source supplying exactly \(2\) units. Its residual outflow \(r_t\) obeys the physical conservation constraint
\(q_t+r_t=2,\qquad r_t\geq0.\)
These residual flows enter a full binary merging tree. Each internal vertex has two incoming flows and one outgoing flow, with the conservation equation
\(r_{\mathrm{out}}=r_{\mathrm{left}}+r_{\mathrm{right}}.\)
All flows are nonnegative. Write \(R\) for the root outflow. The conservation equations imply
\(r_t=1-y_t,\qquad R=\sum_{t=1}^{\tau}(1-y_t)=\tau-\sum_{t=1}^{\tau}y_t.\)
There is one normative requirement, with affine slack
\(\ell=R-\tau.\)
Thus its satisfaction requires a total residual outflow of at least \(\tau\). Its regulatory score is
\(G=\min\{0,R-\tau\}=-\sum_{t=1}^{\tau}y_t,\)
because every feasible allocation has \(R\leq\tau\). In particular, the regulatory objective is nonconstant.
Choose the supplied bounds
\(b_t^-=0,\quad b_t^+=1\quad(1\leq t\leq\tau),\qquad b_G^-=-\tau,\quad b_G^+=0.\)
They enclose the feasible coordinate ranges. The normalized objective vector is consequently
\(\widehat F(y)=\left(y_1,\ldots,y_\tau,\;1-\frac1\tau\sum_{t=1}^{\tau}y_t\right).\)
Every \(y\in[0,1]^\tau\) determines a feasible allocation: use the allocation masses above, set each leaf residual to \(1-y_t\), and set every internal flow to the sum of its descendant leaf residuals. These values satisfy every conservation equation and are nonnegative.
Conversely, every feasible allocation determines such a \(y\), and conservation uniquely determines all its flows. Hence the feasible set is parametrized exactly by \([0,1]^\tau\). It is nonempty and bounded: allocation masses are bounded by \(1/\tau\), and every auxiliary flow is at most \(\tau\). Rational \(y\) gives a rational feasible allocation.
The required incidence graph is a tree. To verify this explicitly, first consider only flow variables and merging constraints. Start with the root flow variable. At each internal vertex, attach a conservation factor to its outgoing flow and attach two new incoming flow variables to that factor. This recursively constructs a tree.
At each leaf flow, attach its source conservation factor and its type allocation block. Finally, attach each unary utility factor to its type block and the normative factor to the root flow. Each attachment preserves connectedness and acyclicity. If block normalization constraints are represented explicitly, they merely add unary leaves.
Moreover, every physical factor involves at most three variable nodes, and the normative factor is unary.
There are \(\tau\) source constraints, \(\tau-1\) merging constraints, and \(2\tau-1\) auxiliary flow variables. Thus \(m=O(\tau)\) and \(d=2\tau\). All numerical data have bit length \(O(\log\tau)\), and the complete input has length polynomial in \(\tau\).
Here domination means that every objective is at least as large and at least one is strictly larger.
Suppose the allocation corresponding to \(y'\) dominates the allocation corresponding to \(y\). Comparing the type utilities gives
\(y'_t\geq y_t\qquad\text{for every }t.\)
Comparing the regulatory scores gives
\(-\sum_t y'_t\geq-\sum_t y_t,\)
so \(\sum_t y'_t\leq\sum_t y_t\).
But the coordinatewise inequalities imply that every difference \(y'_t-y_t\) is nonnegative. Their sum is nonpositive, so every difference must be zero. Thus \(y'=y\), and all objective coordinates are equal. This contradicts the required strict improvement.
Therefore every feasible allocation is Pareto-optimal.
For each \(v\in\{0,1\}^\tau\), let \(p_v\) be its corresponding rational feasible allocation. All \(2^\tau\) allocations are Pareto-optimal by the preceding section.
If \(v\neq w\), some type coordinate differs by \(1\). Every normalized coordinate lies in \([0,1]\), so
\(\|\widehat F(p_v)-\widehat F(p_w)\|_\infty=1.\)
Fix \(0<\epsilon<1/2\). A single feasible allocation \(s\) cannot cover two distinct members \(p_v,p_w\). Otherwise, the triangle inequality would give
\(\|\widehat F(p_v)-\widehat F(p_w)\|_\infty\leq\|\widehat F(p_v)-\widehat F(s)\|_\infty+\|\widehat F(s)-\widehat F(p_w)\|_\infty\leq2\epsilon<1,\)
contradicting their separation.
Since every \(p_v\) must be covered, every \(\epsilon\)-cover satisfies
\(|S|\geq2^\tau.\)
This argument permits arbitrary feasible cover members; it does not restrict them to the selected binary allocations.
For completeness, the bound is attained on this family when \(\epsilon=1/4\). Take all allocations corresponding to
\(c\in\{1/4,3/4\}^\tau.\)
Given any \(y\in[0,1]^\tau\), choose each \(c_t\) so that \(|y_t-c_t|\leq1/4\). The normalized regulatory coordinate also differs by at most \(1/4\), because
\(\left|\frac1\tau\sum_t(y_t-c_t)\right|\leq\frac1\tau\sum_t|y_t-c_t|\leq1/4.\)
These \(2^\tau\) rational allocations therefore form a \(1/4\)-cover.
Set \(\epsilon=1/4\), so \(1/\epsilon=4\) is constant. Along this family, all input parameters are polynomially bounded in \(\tau\), while every explicit cover contains at least \(2^\tau\) allocations. Merely writing the output therefore exceeds every polynomial bound in the stated parameters.
The obstruction concerns explicit covers. A compact description of a family of allocations would be a different output requirement.
There is no conflict with the cited results:
Thus the target question is settled by unavoidable superpolynomial output size, even with binary menus and conservation factors involving at most three variables.
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the task through an unconditional exponential output-size obstruction. No major or minor mathematical issues were found. The proof establishes that explicit covers cannot always be computed in the requested polynomial time; it does not claim NP-hardness.
The restriction to support sizes \(\tau=2^h\), with \(h\geq1\), supplies an infinite family and ensures that every mass \(\mu_t=1/\tau\) is a positive dyadic rational. The masses sum to \(1\), the population scale \(N=\tau\) is an admissible binary-encoded integer, and the menus and utilities meet the stated rationality and positivity requirements. The types have distinct withdrawal locations, so using identical menus and utilities does not collapse the support size.
The parametrization \(y_t=\tau x_{t,2}\) is exactly equivalent to the allocation constraints. In particular, nonnegativity and \(x_{t,1}+x_{t,2}=1/\tau\) give \(0\leq y_t\leq1\), with the inverse formulas stated by the prover.
Both objective calculations are correct:
Source conservation therefore gives \(r_t=1-y_t\). Summing conservation through the merging tree gives \(R=\tau-\sum_t y_t\). Consequently, \(R-\tau=-\sum_t y_t\leq0\), so the regulatory score is exactly \(G=-\sum_t y_t\), including the boundary case \(y=0\).
The bounds enclose the full coordinate ranges and have strictly positive widths. The normalized regulatory coordinate is correctly calculated as \(1-\tau^{-1}\sum_t y_t\).
The normative requirement is allowed to be violated: it contributes to the score rather than restricting physical feasibility. Thus the construction uses the task’s intended distinction between physical constraints and normative terms.
The claimed correspondence with \([0,1]^\tau\) holds in both directions.
For each \(y\) in that cube, the specified allocation masses satisfy their normalization and nonnegativity constraints. Leaf residuals are nonnegative, and descendant sums define nonnegative internal flows satisfying every merging equation.
Conversely, every feasible allocation determines a point of the cube. Source conservation fixes the leaf residuals, and the merging equations then uniquely fix every remaining flow. There are no additional free flow variables.
This proves nonemptiness, boundedness, and the asserted parametrization. Every flow is bounded above by \(\tau\). Rational \(y\) produces rational masses and flows, so the selected corner allocations and the later cover members satisfy the output rationality requirement.
The acyclicity argument uses the required incidence graph, with one variable node per allocation block.
The recursive construction of the flow-variable and merging-factor graph adds each new factor through one existing outgoing-flow node and introduces two new incoming-flow nodes. It therefore preserves connectedness and introduces no cycle.
At each leaf, attaching a source factor and a new type block also preserves the tree structure. Utility factors, the normative factor, and any explicit allocation normalization or nonnegativity factors are unary attachments. They cannot create cycles.
The counts are correct: a full binary tree with \(\tau\) leaves has \(\tau-1\) internal vertices and \(2\tau-1\) associated flow variables. Including source vertices, edges, and local constraints keeps \(m=O(\tau)\). Also, \(d=2\tau\).
All supplied numbers have bit length \(O(\log\tau)\). Listing the network, type locations, tables, and constraints requires only polynomial input length. No exponentially large data are hidden in the construction.
The domination argument is complete and uses the appropriate definition: coordinatewise improvement with at least one strict improvement.
If an allocation corresponding to \(y'\) dominates one corresponding to \(y\), the utility coordinates require \(y'_t\geq y_t\) for every type. The regulatory coordinate requires \(\sum_t y'_t\leq\sum_t y_t\).
Thus all differences \(y'_t-y_t\) are nonnegative while their sum is nonpositive. Every difference must vanish. All objective values are then equal, contradicting strict improvement.
This proves that every feasible allocation is Pareto-optimal, including interior and boundary allocations.
For distinct binary vectors \(v,w\), some utility coordinate differs by exactly \(1\). All normalized coordinates lie in \([0,1]\), so their objective vectors have infinity-norm distance exactly \(1\).
If one cover member covered both corresponding allocations, the triangle inequality would force their distance to be at most \(2\epsilon<1\). This is impossible. Therefore each cover member covers at most one of the \(2^\tau\) selected Pareto-optimal allocations, and \(|S|\geq2^\tau\).
The argument allows arbitrary feasible cover members. It does not assume that members themselves are binary corners. The strict range \(0<\epsilon<1/2\) is correctly maintained.
The optional attainment claim at \(\epsilon=1/4\) is also correct. Each coordinate can be approximated within \(1/4\) by either \(1/4\) or \(3/4\). The normalized regulatory-coordinate error is bounded by the average absolute coordinate error, hence also by \(1/4\). The resulting \(2^\tau\) rational feasible allocations cover the entire feasible set.
Fixing \(\epsilon=1/4\) makes \(1/\epsilon\) constant. Every requested input parameter is polynomially bounded in \(\tau\), whereas an explicit cover requires at least \(2^\tau\) entries. Writing those entries already rules out the requested polynomial running time. No complexity-theoretic assumption is needed.
The cited results are contextual rather than premises of this proof:
No repairs or additional clarifications are 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.