| paper | d4-conf-atal-2015-0316 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable exactly in \((m+\tau+s+L)^{O(1)}\) bit operations. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
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)\).
A rational LP over offer-choice masses \(a_{tq}\) and signed feeder flows \(f_e\). Each unit of mass takes one of the paper’s integral offers, while a type’s mass may be divided across offers; aggregate flows obey nodal balance and per-capita edge capacities.
The mirror covers the acyclic EAP and Theorem 1’s message computation as used by RadPro. It leaves aside the arbitrary-topology MIP, the empirical solver comparisons, and the payment-rule discussion.
The strongest anchor is Theorem 1, the paper’s result on computing RadPro’s messages for the Energy Allocation Problem on an acyclic network. It is the authors’ result; the proceedings paper states it and defers the proofs to their extended technical report [1]. The theorem gives the messages explicitly. If \(p_j\) is an in-neighbor of prosumer \(j\), the message is the aggregation of \(j\)’s offer valuation with the messages from its out-neighbors and its other in-neighbors, restricted to the capacity of the link to \(p_j\). If \(p_j\) is an out-neighbor, it uses the complemented offer valuation, the messages from its other out-neighbors and all its in-neighbors, and the corresponding complemented capacity range. In the paper’s notation, these are
\[ \mu_{j\to p_j} = \left( o_j \cdot \prod_{k\in\operatorname{out}(j)}\mu_{j\to k} \cdot \prod_{i\in\operatorname{in}(j)\setminus\{p_j\}}\mu_{i\to j} \right)[D_{p_jj}] \]
for an in-neighbor parent, and
\[ \mu_{j\to p_j} = \left( \bar{o}_j \cdot \prod_{k\in\operatorname{out}(j)\setminus\{p_j\}}\mu_{j\to k} \cdot \prod_{i\in\operatorname{in}(j)}\mu_{i\to j} \right)[-D_{jp_j}] \]
for an out-neighbor parent. Here \(\cdot\) is the paper’s valuation aggregation operation, \(\bar{o}_j\) is the complemented offer, and restriction to \(D\) discards quantities outside that domain. Theorem 1 says each message can be assessed in time \(O(N_j C_j n_{o_j}+N_j^2C_j^2)\), where \(N_j\) is the number of neighbors, \(C_j\) is the largest incident-link capacity, and \(n_{o_j}\) is the number of finite offers. Section 5.3 uses this result in RadPro to solve acyclic EAP instances in polynomial time in the network size, degrees, capacities, and offer-table sizes. The stated bound is in the numerical capacities; it is not a bit-length bound. The paper has no comparable numbered hardness result to anchor here.
Here is the continuous problem I would hand to a prover. Consider a radial feeder represented by a tree \(H=(V,E)\). At each location \(v\), let \(T_v\) be the set of prosumer types attached there. A type \(t\) specifies the location, the full finite offer menu \(Q_t\subseteq\mathbb Z\), and the utility \(u_t(q)\in\mathbb Q\) for each offered net quantity \(q\). Positive \(q\) means buying and negative \(q\) means selling, as in the paper. The society is given by rational masses \(\mu_t\geq 0\), with \(\sum_t\mu_t=1\). Each edge \(e\) has a rational capacity \(\kappa_e\) per unit of normalized population.
Continuous EAP on a radial feeder. Choose \(a_{tq}\geq 0\), the mass of type \(t\) taking offer \(q\), and a signed aggregate flow \(f_e\in\mathbb R\) on each oriented edge. Maximize
\[ \sum_{t}\sum_{q\in Q_t} a_{tq}u_t(q) \]
subject to
\[ \sum_{q\in Q_t}a_{tq}=\mu_t \qquad\text{for every }t, \]
\[ \sum_{\substack{e\text{ enters }v}} f_e - \sum_{\substack{e\text{ leaves }v}} f_e = \sum_{t\in T_v}\sum_{q\in Q_t} q\,a_{tq} \qquad\text{for every }v, \]
and
\[ -\kappa_e\leq f_e\leq\kappa_e \qquad\text{for every }e. \]
A solution is the offer-choice mass \(a\) and the feasible edge flows \(f\). Each individual still takes exactly one integral offer \(q\); \(a_{tq}\) records how much of the continuum takes it. The resulting average quantities and aggregate flows can be fractional. The capacity convention means that physical feeder capacity scales with the size of the population represented by the normalized mass.
A plausible regime is a large housing district trading through a radial distribution network: many thousands of premises, with types determined by feeder location and a shared complete offer schedule—for example, a particular load and storage package with the same buy and sell options and values. If many premises share those schedules, the number of agents can greatly exceed the number of distinct types. Location belongs in the type because it determines the network constraints; idiosyncratic offers or connection conditions create distinct types. This is a scenario claim, not an assumption that every energy market has high multiplicity.
This is recognizably the paper’s EAP: agents choose mutually exclusive buy or sell offers; the network must carry the resulting trades within capacity; the objective is the sum of prosumers’ offer values. Continuization changes how many identical participants take each offer, while preserving the offer menu and network-constrained allocation question. It does require aggregating prosumers by feeder location and scaling line capacity with population, both natural co-modifications for a large feeder cohort. The generic formulation above is a linear program with a number of variables and constraints polynomial in the offer support, type support, and feeder size. I expect this mirror to be Class A, tractable, by rational linear programming. A more specific question, closer to the paper’s contribution, is whether one can derive a RadPro-style message algorithm whose running time is polynomial in the support and binary input length.
The mirror covers the paper’s acyclic EAP result, especially Theorem 1 and its use in RadPro. It does not claim to continuize the paper’s mechanism-design discussion, empirical comparison, or arbitrary-topology MIP results. Natural follow-up questions include whether the continuous message functions admit a compact representation; how the optimum relates to finite EAP when type masses are multiples of \(1/N\); and whether that relation gives additive approximation guarantees as \(N\) grows.
The weak point is that Theorem 1 studies finite, individually represented prosumers and bounds message computation using numerical capacities. It does not itself establish a continuous algorithm polynomial in \(\tau\) and input bit length. The tractability claim for the stated mirror comes from the cohort LP, so a referee could reasonably ask whether this is the paper’s problem or a convexified variant. I think the case survives because the convexification comes from population mass, not from letting a prosumer take a fractional offer: every unit of mass still receives one of the paper’s original offers. That is the high-multiplicity change the programme is meant to examine.
The strongest case against the anchor is that a prosumer’s type has to include its position in the trading network, because that position determines which trades are feasible. Sharing an offer schedule is not enough. In an ordinary feeder, most prosumers have distinct connections and capacities, so including the network role may leave nearly one type per prosumer. The proposed mirror becomes useful only in a more structured regime: repeated symmetric branches, or many otherwise identical prosumers attached to the same bus, with their individual edge constraints aggregated into a capacity that scales with the cohort. That is plausible, but it is a narrower scenario than “large energy market” alone suggests.
That objection does not defeat the mirror. Repeated identical leaves on a radial network are a legitimate high-multiplicity regime: their offers and constraints are interchangeable, and each individual can still take one of the paper’s discrete offers. Aggregating the cohort’s choices into masses and its edge flows into aggregate capacity is a natural model co-modification. The resulting LP asks a recognizable EAP question. Since one sound scenario is enough, I cannot honestly argue that Theorem 1 has no worthwhile continuous mirror.
There is adjacent work by the same authors that calls its model the continuous energy allocation problem and uses piecewise-linear utilities. But it makes each finite prosumer’s traded quantity continuous; it does not make the population continuous, so it is not a novelty collision under this programme’s definition. It does, however, support the claim that authors in this area would recognize continuous market clearing as a sensible question. [Defining and solving the energy allocation problem with continuous prosumers](https://www.iiia.csic.es/media/filer_public/6c/71/6c710c40-168e-4b2c-a9c8-cc9784d7f61d/5499.pdf)
The negative case is therefore limited to scope: the mirror fits repeated network structure better than a generic heterogeneous grid, and a cohort LP may shift attention away from RadPro’s message computation on individually represented prosumers. Those are reasons to qualify the anchor, not grounds to reject it. The honest assessment is that the case against is weak here; the continuous-population EAP survives.
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.