| paper | d4-conf-ijcai-2015-0573 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
The mass-allocation LP is a coherent continuous version of welfare maximization, but its hardness anchor is unnumbered. Theorem 2 is a constructive computational result, yet the proposed LP does not mirror its cost-sharing stability guarantee; an atomless version needs a mass-coalition stability concept, which changes the theorem's single-consumer Nash question.
fails bit b-changes — the continuum limit changes the question
The proposed LP addresses welfare maximization under linear producer costs. It does not cover Theorems 1 or 2, the Shapley-like and similarity-based payment schemes, or the experiments.
The strict anchor check fails: this paper has no numbered computational-complexity result of the kind your brief requires. It does have two numbered theorems. Theorem 1 says that, under marginal-cost defection pricing, no cost-sharing scheme achieves a price of stability better than \(\infty\) when producer price functions may have capacity and ramp constraints; the paper proves this here. Theorem 2 says there is a cost-sharing scheme with price of stability \(1\) when price functions have only tracking layers and capacity constraints; the paper also proves this here. Those are stability results, not claims that an underlying problem is NP-hard, in P, or in another complexity class.
The closest complexity result is an unnumbered claim in Section 2: maximizing social welfare is NP-hard even with trivial producer price functions, by reduction to Lu and Boutilier’s matching model. The paper says that model is NP-hard via Knapsack. The authors also describe simulating it with a different time period for each agent. This is a useful lead, but it cannot serve as the required named anchor.
The strongest positive mirror I can make from that lead is a continuous version of social-welfare-maximizing producer matching. An instance has producers \(J\), \(q\) time periods, and a finite support \(T\) of complete consumer types. Each type \(t\) has rational mass \(\mu_t\), with \(\sum_t \mu_t=1\); a finite set of rational demand profiles \(\Pi_t\); a rational value \(V_t(\pi)\) for each profile; and an outside-option value \(\theta_t\). Let producer \(j\)’s cost be the linear function \(C_j(d)=a_j^\top d\), for rational \(a_j\ge 0\).
Choose masses \(x_{t,j,\pi}\ge 0\) assigned to each producer-profile pair, and \(x_{t,0}\ge 0\) assigned to the outside option, subject to
\[
x_{t,0}+\sum_{j\in J,\,\pi\in\Pi_t}x_{t,j,\pi}=\mu_t
\quad\text{for every }t.
\]
Producer \(j\)’s aggregate demand is \(d_j=\sum_{t,\pi}x_{t,j,\pi}\pi\). The question is to return an allocation maximizing
\[
\sum_t x_{t,0}\theta_t+
\sum_{t,j,\pi}x_{t,j,\pi}V_t(\pi)
-\sum_j C_j(d_j).
\]
The output is the optimal value and an allocation of mass. Each part of the population receives one listed producer-profile contract; only the mass of a type is divided among contracts.
I expect this version to be tractable: it is a linear program, with size polynomial in the explicitly listed types, profiles, producers, periods, and input bit length. This mirrors the paper’s welfare-maximization problem under its stated trivial-price hardness setting, while making the population the continuous object. It does not claim the original discrete hardness vanishes for every input: if the reduction requires each consumer to have distinct preferences or its own time period, then the number of complete types or periods can grow with the population. The continuous algorithm’s running time must account for those parameters.
A plausible regime is coordinated purchasing by a large housing cohort—say, tens of thousands of homes but a much smaller set of exact consumer types sharing demand-profile menus and valuations. The paper already aggregates demand by producer, and its allocation decision is whether each consumer takes a particular profile from a producer. Replacing counts by masses preserves that decision while making the type-level allocation divisible. It does not make electricity use or an individual contract fractional. This is a plausible extension of the authors’ problem, though exact identity of household preferences is a demanding assumption.
The proposed question covers only social-welfare maximization, not the paper’s stability theorems, Shapley payments, or similarity-based envy-free payments. Natural follow-ups are whether convex piecewise-linear generation costs still give an LP; what happens with ramp and shutdown features; and how to define and compute stable cost sharing for a nonatomic population.
My weakest point is both formal and substantive: the paper’s NP-hardness statement is unnumbered, so this does not satisfy your anchor requirement; and the real electricity features that motivate the paper include price functions beyond linear costs. The positive case is therefore a credible continuous mirror of one underlying problem, but not a compliant named-anchor case.
The strongest negative is a formal one: the paper has no numbered theorem, lemma, or corollary about the complexity of a computational problem. Theorem 1 and Theorem 2 concern prices of stability. The unnumbered claim that welfare maximization is NP-hard is a useful lead, but it is not the named computational result the analysts were asked to anchor on.
The proposed mass-allocation LP does not fix that gap. It is a coherent continuous version of welfare maximization, but it assumes linear producer costs and explicitly listed type menus. That strips away the ramp, shutdown, and other producer-cost features that motivate the paper’s model, and it says nothing about the paper’s cost-sharing and stability results. So it is a plausible new problem, but not a mirror anchored in a named result of this paper.
There is a stronger mirror one could propose: group consumers by complete type, retain their demand menus and valuations, scale supplies appropriately, and keep the paper’s producer cost functions. Then ask how to optimize welfare and compute cost shares or stability guarantees over the type masses. That is a sensible high-multiplicity regime. It also exposes a real modeling question: in a nonatomic society, a single consumer’s deviation has zero effect on aggregate demand, so the paper’s stability notions need an explicit mass-based or price-taking interpretation. But that is a modeling burden, not a decisive objection; a natural extension could preserve the authors’ problem.
So I would reject the proponent’s case as a compliant *named-anchor* case, but I cannot honestly conclude that no worthwhile continuous mirror exists. The proposed LP is too detached from the paper’s central cost and pricing features, yet a fuller type-based model remains plausible. The negative case is strongest on the lack of a qualifying anchor and weak against the broader universal claim.
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.