| paper | d4-conf-atal-2015-0348 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
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\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
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 continuum of interchangeable water users grouped by reach, crop, rights, action menu, and utility parameters. Decision variables are the population fractions \(x_{t,a}\) assigned to each finite action; aggregate withdrawals scale with \(N\), while the Pareto vector records each type’s average utility \(U_t\) and the network regulatory score \(G\).
Type-average utility erases differences in outcomes within a class, so it loses the paper’s agent-by-agent Pareto comparisons; the proponent acknowledges that change and offers class-level welfare as a rationale, but does not establish that the authors would accept it.
fatal: False
The mirror extends the acyclic Pareto-frontier recovery task underlying Proposition 1 to class-average objectives over a continuous population. It leaves the finite-agent marginal algorithm, the cyclic-graph approximation experiments, and the paper’s other experimental findings untouched.
The strongest honest mirror is the paper’s Pareto-frontier problem for a basin with many small water users and a relatively small number of distinct user profiles. Think of thousands of farms drawing from shared canals: users at the same reach with the same crop, water rights, feasible withdrawal options, and utility parameters are indistinguishable for the model. A type includes all of those features, including location. If there are \(N\) users but only \(\tau\) such profiles, with \(N\gg\tau\), the society is a distribution \(\mu\) over those types. Reservoir inflows and capacities can remain fixed physical quantities; total withdrawals are computed from the population masses.
My anchor is Proposition 1, proved in this paper (with a proof sketch). It says that, once the marginal functions have converged, an assignment \(x\) is Pareto optimal if and only if it appears in the marginal function \(z_j(x_j)\) of every variable \(x_j\) in the factor graph. This is the correctness claim behind assembling the frontier from the marginals. It is not a theorem that the problem is in P: the paper’s formal runtime bound is unnumbered, and its main scaling evidence is experimental. The paper cites the acyclic-graph guarantee from Delle Fave et al. [6]; that result is external, rather than an anchor proved here.
Here is the continuous problem I would put to a prover, and the one I would lead with: Type-Continuum Water Pareto Cover. An instance gives a river interaction graph, preferably with an acyclic factor graph to match the paper’s exact-frontier setting; a large population size \(N\); rational type masses \(\mu_t\) summing to one; and, for each type \(t\), a finite action menu \(D_t\) and the paper’s utility values \(f_t(a)\). Physical flow constraints and normative scores are specified for the network. The action menus stay finite: the continuum is in the population, not in the water-allocation choices.
The decision variables are \(x_{t,a}\geq 0\), the fraction of the whole population that is type \(t\) and takes action \(a\), with \(\sum_{a\in D_t}x_{t,a}=\mu_t\). Thus type \(t\)’s total withdrawal is \(N\sum_a a x_{t,a}\). The objective vector has one coordinate per type, \(U_t=\mu_t^{-1}\sum_a x_{t,a}f_t(a)\), plus the aggregate regulatory score \(G\) for the network’s normative constraints. Physical constraints determine feasibility; the Pareto comparison is over \((U_1,\ldots,U_\tau,G)\). Given \(\epsilon>0\), the requested solution is a finite set of feasible population allocations whose objective vectors come within \(\epsilon\), coordinatewise, of every Pareto-optimal objective vector. Objective coordinates can be normalized to make the additive tolerance comparable across dimensions.
I expect this problem to be tractable for fixed \(\tau\). Each individual’s action set remains finite, but the mass variables allow a type’s population to be split across its available actions. The type utilities are then linear in \(x\), and the physical network constraints are linear in aggregate flows. With the paper’s piecewise-linear constraint scores, weighted-sum queries over the attainable objective region are LPs; those queries support constructing an \(\epsilon\)-cover. The qualification matters: the number of objective coordinates grows with \(\tau\), and an explicit exact frontier can have many faces. I would not claim polynomial time in unrestricted \(\tau\) or a compact explicit listing of every frontier point.
This is a plausible question for the authors because it retains their regulator’s task: explore trade-offs among stakeholder objectives while respecting shared water constraints. A discrete assignment embeds when every \(x_{t,a}\) is a multiple of \(1/N\), so the population model is a high-multiplicity relaxation of the assignment problem. The proposed mirror covers the paper’s frontier-recovery result for that water-management problem, especially its acyclic case. It does not claim to mirror the paper’s strategic-behavior question, its cyclic-edge-cut approximation experiments, or every feature of its generated systems.
The soft spot is that the paper studies a small number of autonomous decision-makers and gives each one a separate objective coordinate. My mirror replaces those coordinates with a type’s average utility, and permits a homogeneous population to be divided among actions. That changes the Pareto object. It is defensible for a regulator comparing welfare across stakeholder classes, but an author who regards each organization’s individual outcome as essential may reject it as a different question. Further questions follow directly: how does complexity depend on \(\tau\) and \(\epsilon\); what frontier guarantees hold for cyclic networks; and how large is the gap between the discrete assignment frontier and its mass relaxation?
The proponent has one anchor: Proposition 1, which says that on a finite acyclic factor graph a Pareto-optimal assignment appears in every variable’s converged marginal function. That is a correctness characterization, not a complexity result. The paper’s runtime bound is unnumbered, and the reported scaling evidence is experimental. So there is no named complexity theorem here to continuize; the proposed Pareto-cover problem is a new computational question built around a different output.
The model also gives “agent” a more specific meaning than member of a large population. An agent controls a decision at a particular place in a river network and contributes a distinct objective; the flow constraints link those positions. As a watershed grows, its locations and factor scopes generally grow too, so describing more of it tends to increase the number of relevant types along with the system size. Repeating identical users at one reach is plausible, but that is a special regime. The paper’s city, dam, farms, and ecological points are different roles at different network positions, and its farm agents may already stand for groups of users.
In that repeated-user regime, the proposed type-average utility changes the Pareto object. The paper compares a vector with one coordinate per active agent. For two identical users, outcomes giving utilities \((1,0)\) and \((0,1)\) are incomparable under that order; both collapse to average utility \(1/2\). A regulator could reasonably choose to compare type averages, but that is a substantive change in what counts as a trade-off. Preserving the original distinction would require tracking the distribution of outcomes within each type and specifying a Pareto order for those distributions. Proposition 1’s finite-assignment statement would then no longer be the result being mirrored. Forbidding within-type mixtures avoids that change, but leaves one finite action choice per type rather than a genuinely divisible population decision.
There is a good case for studying many interchangeable irrigators in a shared hydraulic cell, with class-level welfare and aggregate flow constraints. That looks like a sensible high-multiplicity water-management problem, and its mass-allocation formulation may be useful. But it does not rescue the specific anchor: it changes the objective semantics and replaces the paper’s marginal-assignment question with a frontier problem over population allocations. The honest negative case is therefore strong against treating this paper’s result as a natural continuization target, but weak against the universal claim: the irrigator scenario remains plausible if the authors accept class-level welfare as their problem.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.