| paper | d4-conf-ijcai-2017-0107 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\) by rational linear-programming feasibility. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 7
statement extracted from the paper’s text layer
Given a finite type set \(T\) with rational masses \(\mu_t\) summing to one, a finite menu \(J\) of fixed contracts with per-consumer reductions \(\ell_j\), rational costs \(b_{tj}\), a required per-consumer reduction \(\rho\), and a per-consumer cost bound \(z\), decide whether there are rational allocations \(x_{tj}\ge 0\) satisfying \(\sum_j x_{tj}\le\mu_t\) for every \(t\), \(\sum_{t,j}\ell_jx_{tj}\ge\rho\), and \(\sum_{t,j}b_{tj}x_{tj}\le z\).
Consumers are grouped into complete types with mass \(\mu_t\); each type's cost vector \(b_{tj}\) records its cost for each fixed contract. The variable \(x_{tj}\) is the population mass of type \(t\) assigned contract \(j\). Minimize total cost \(\sum_{t,j}b_{tj}x_{tj}\) subject to the type-mass limits and the required total reduction.
The resulting LP is a standard fractional allocation problem and offers little demand-response-specific algorithmic insight; this limits the mirror's novelty, but not its validity.
fatal: False
The mirror covers Proposition 7's fixed-contract selection problem. It leaves the VCG truthfulness and pricing results, reliability bounds, and simulations unmodeled.
My lead is a continuous fixed-contract selection problem, mirroring Proposition 7, proved in Appendix B of this paper. Proposition 7 says that deciding whether \(\mathrm{SB}^*(N,J)\le Z\) is NP-hard, even when \(J\) contains only fixed contracts. The authors prove this here by reduction from Knapsack: the grid must select contracts whose declared reductions meet the target while keeping the sum of bids within the budget.
A natural high-multiplicity setting is demand response from a large fleet of similar controllable loads: for example, many homes with the same device and control setup, or many facilities with the same operating and reliability profile. The grid offers a finite menu of fixed contracts, and each profile has the same cost for each contract. There may be many consumers but only a modest number \(\tau\) of distinct profiles. A type records the full information relevant to this allocation problem: its effort and reliability characteristics, which induce a cost for every contract. Equivalently, for the selection stage, those costs can be supplied as the type’s vector \(b_{tj}\). This is the setting in which grouping agents by type is meaningful; a fleet of unique industrial participants may not have that structure.
Here is the mirror, Continuous Fixed-Contract Selection. The input is a finite set of types \(T\), rational masses \(\mu_t\) summing to one, a finite menu \(J\) of fixed contracts with per-consumer reductions \(\ell_j\), nonnegative rational costs \(b_{tj}\), a required per-consumer reduction \(\rho\), and a per-consumer budget \(z\). Decide whether there is a rational allocation \(x_{tj}\ge 0\), where \(x_{tj}\) is the fraction of the whole population of type \(t\) assigned contract \(j\), satisfying \(\sum_j x_{tj}\le \mu_t\) for each \(t\), \(\sum_{t,j}\ell_jx_{tj}\ge\rho\), and \(\sum_{t,j}b_{tj}x_{tj}\le z\). A solution is that allocation matrix. The first constraint preserves the paper’s rule that each consumer receives at most one contract; mass means that a subset of a large cohort is assigned, not that an individual receives a fractional contract.
This is the direct relaxation of the underlying selection question: for \(n\) consumers with type counts \(n_t\), take \(\mu_t=n_t/n\) and \(\rho=M/n\). The discrete allocation restricts each \(x_{tj}\) to multiples of \(1/n\); the continuous version drops that granularity. Its feasibility question is a linear program with \(\tau |J|\) allocation variables, so it is tractable in time polynomial in the explicit rational input length. I expect this mirror to fall in Class A: the integral selection combinatorics in Proposition 7’s finite instance become linear allocation of type mass.
The authors should recognize the question: it keeps their fixed contract menu, their declared-reduction target, their bid-cost objective, and the one-contract-per-consumer constraint. Only the population representation and the allocation granularity change. This mirror covers Proposition 7’s contract-selection computation; it does not claim to continuize the VCG truthfulness result, the reliability bounds, or the paper’s simulations.
The main limitation is also the main challenge for the opposing case. The Knapsack reduction uses item-specific agents and contracts, so its hardness witness does not itself exhibit high multiplicity; if nearly every consumer has a distinct cost profile, then \(\tau\) may approach the population size and the aggregation buys little. The mirror is strongest for fleets with genuinely repeated profiles and a shared menu. Further questions include how accurately a continuous allocation can be rounded for a finite fleet, how the gap depends on \(\tau\) and the menu size, and whether costs induced by complex effort distributions can be computed efficiently. The LP addresses selection once the type-level costs are given; it does not solve that separate cost-computation problem.
The paper has a real computational anchor: Theorem 1 gives an algorithm for computing the contract set and VCG prices, and Proposition 7 proves NP-hardness for the general fixed-contract selection problem. So the case against cannot rest on a lack of computational results.
The proposed mirror is mathematically clean. For a fleet with \(\tau\) repeated consumer types and a shared finite contract menu, it assigns type mass to contracts by solving an LP. The strongest objection is about its research value: once the type-by-contract costs and reductions are explicit, the optimization is a standard fractional allocation problem. Its polynomial solvability follows directly from the formulation, without a demand-response-specific algorithm or pricing insight. That makes it a thin result for a programme seeking a complexity landscape, even if it is a valid continuous-population model.
The paper’s distinctive mechanism also uses individual bids and Clarke pivot payments. A type-level allocation records how much mass receives each contract; it does not by itself specify the effect of removing one selected consumer. A normalized atomless model assigns an individual zero mass, so a faithful treatment of those payments needs to retain finite population scale or derive an appropriate marginal-price variant. That could become a worthwhile question, but it is a larger mechanism redesign than the selection LP. The paper’s reliability analysis raises a related modeling choice: a distribution of individual types alone does not specify correlations between consumers’ failures.
The richer contract menu in Appendix A does not clearly rescue the negative case. With an explicit finite menu, the same LP applies. With a continuum of contracts or costs derived from effort distributions, the computational work depends on how those functions are represented and on the resulting optimization problem; the population continuum alone does not settle it.
This makes the negative case a value objection, not a demonstration that no useful mirror exists. Large fleets of similar controllable loads are plausible, and their mass allocation is a sensible object. The proposed LP is a genuine, narrow mirror of Proposition 7. I cannot honestly argue that every continuous-population version is unworthwhile; the case against is weakest precisely at that anchor.
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.