| paper | d4-conf-atal-2010-0287 |
| 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: \(\mathrm{P}\): polynomial-time solvable, with exact bit complexity \(O\!\left(L+(1+mN+CN+C+\tau)L^2\right)\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given complete seller-state types \(h\) with rational masses \(\mu_h\) summing to \(1\), and each type’s resources, costs, agreements, incoming offers, and feasible integral configurations \(Z_h\), choose \(x_{hz}\geq 0\) with \(\sum_{z\in Z_h}x_{hz}=\mu_h\) to maximize \(\sum_{h\in H}\sum_{z\in Z_h}\pi_{hz}x_{hz}\), where \(\pi_{hz}\) is the seller utility of configuration \(z\). What is the complexity of finding an optimal mass allocation?
A finite support of complete seller-state types \(h\), rational masses \(\mu_h\), and per-type feasible integral configurations \(Z_h\); choose configuration shares \(x_{hz}\) summing to each type’s mass and maximize their aggregate seller utility.
Because offers are buyer-specific obligations, replicating an identical seller menu without shared buyer-side constraints models repeated local subproblems rather than the coupled marketplace.
fatal: False
The mirror covers Theorem 1’s seller contract-selection problem over repeated seller-state types. It leaves aside the buyer strategy, dynamic negotiation protocol, and the paper’s experimental welfare comparisons.
The strongest mirror is narrow: the seller’s contract-selection problem in Theorem 1, not the paper’s entire dynamic negotiation mechanism.
Theorem 1, proved in this paper by a reduction from 0–1 Knapsack, states that \(\mathrm{OPT}_s(RA_s,A_s,TA_s,O_s)\) is NP-complete. Given a seller’s running agreements, final agreements, tentative agreements, and incoming offers, it chooses which final agreements \(KA_s\) to keep, which tentative agreements \(KTA_s\) not to cancel, and which offers \(AO_s\) to accept. It maximizes revenue minus resource costs for the kept and accepted agreements, less penalties for decommitting from final agreements:
\[
\sum_{o\in KA_s\cup KTA_s\cup AO_s}
\bigl(pr(o)-cost(o)\bigr)
-
\sum_{o\in A_s-KA_s} pe(o).
\]
The choices must satisfy the seller’s resource-feasibility constraint; the theorem states this as being able to fulfill \(KA_s\) and \(TA_s\cup AO_s\). This is the paper’s exact computational anchor. The welfare comparisons later in the paper are simulation findings, not additional numbered complexity results.
A plausible high-multiplicity regime is a cloud marketplace processing recurring batches of leases. Many providers may have the same resource capacities, cost schedules, current commitment state, and menu of offers; many requests may reuse the same resource, time-window, price, and penalty templates. A type must include all of those details, since they affect the seller’s choices. In such a batch, there could be vastly more providers than distinct provider-state types—say, a few dozen or hundreds of recurring types across a much larger pool. This scenario is credible only when those negotiation states actually repeat; it is not a claim that every cloud market has a small type count.
I would call the mirror Continuous Seller Contract Selection. Its instance is a finite set \(H\) of complete seller types, each with rational mass \(\mu_h\), where \(\sum_{h\in H}\mu_h=1\). Each type records resource capacities and costs, running and existing agreements, and the finite menu of offers presented to that seller state, including prices, penalties, resource requirements, and any permitted schedule choices. Time can remain in discrete cells, and each provider’s contract and resource choices remain integral.
For each type \(h\), let \(Z_h\) be the feasible whole configurations of keeping or decommitting from final agreements, keeping or cancelling tentative agreements, and accepting offers, including feasible schedule choices. Let \(\pi_{hz}\) be the net seller utility of configuration \(z\), calculated by the theorem’s objective. The decision is to find masses \(x_{hz}\geq 0\) such that
\[
\sum_{z\in Z_h}x_{hz}=\mu_h
\quad\text{for every }h,
\]
maximizing
\[
\sum_{h\in H}\sum_{z\in Z_h}\pi_{hz}x_{hz}.
\]
A solution says what fraction of each seller type follows each feasible contract decision. Each unit of mass follows a complete, feasible provider decision; only the population-level shares are fractional. The question is which mass allocation of those provider decisions maximizes aggregate seller utility.
I expect hardness to transfer. Take one seller type of mass \(1\), with the agreements and offer menu of an instance of \(\mathrm{OPT}_s\). Every provider in that continuous type has the same local decision problem. A mixture of configurations cannot outperform the best configuration, so the continuous optimum is exactly the original seller optimum. Theorem 1’s hardness therefore survives even when the provider population is continuous: the combinatorics lie in choosing among offers and resource commitments, not in the number of individual providers. This is a Class B mirror, and a useful boundary case for the programme.
The authors should recognize this as their seller-side optimization problem: it preserves the agreements, offers, resource limits, penalties, and utility being optimized. Its scope is deliberately limited to that decision problem. It does not continuize the negotiation protocol’s time, the buyer’s strategy, or the paper’s measured welfare advantage. Follow-up questions include whether restrictions on resource types or time windows make the seller decision tractable, and whether useful approximation or parameterized algorithms exist when the offer menu or number of distinct types is small.
My weakest point is that the theorem is local, while the paper’s main story is a dynamic, distributed market. Also, complete negotiation states may differ so much that the number of types approaches the number of providers. The mirror is convincing for a recurring batch with genuinely repeated menus and states; it does not establish that the paper’s whole mechanism has a useful high-multiplicity regime.
Theorem 1 is the paper’s strongest computational anchor, and a repeated batch of identical seller states is plausible. But the proposed continuous mirror does not give the population a computational role. With the proponent’s variables, its objective separates by type:
\[
\max_x \sum_{h,z}\pi_{hz}x_{hz}
=\sum_h\mu_h\max_{z\in Z_h}\pi_{hz}.
\]
Each type sends all its mass to a best local configuration. A mass of one reproduces the original seller problem; more types give a weighted list of independent copies. The NP-hard choice among contracts was already inside one seller’s problem. This is a valid lifting of the theorem, but it reveals nothing about how a continuous population changes the problem or enables new methods.
The batch scenario does not resolve the main modelling gap. A seller’s offer menu consists of particular offers from buyers. Replicating a seller type with the same menu effectively replicates those offers too. In the marketplace, offers are obligations tied to buyer tasks, resource quantities, and time windows; accepting them can affect whether buyers assemble the bundles they need. The proposed formulation has no market-wide constraints conserving offer supply or coordinating those bundles. Add those constraints, together with seller capacities across schedules, and there may be an interesting continuous allocation problem. But that is a new market-wide model: Theorem 1 analyzes a seller’s local choice, while the paper’s mechanism handles distributed, dynamic negotiation and uses a greedy heuristic for that choice. The paper supplies no computational result about the coupled allocation problem.
I would therefore resist treating this as a green anchor. Its one-type hardness transfer is immediate, but it is only the replication of an already hard local primitive; a population-sensitive version requires adding the market coordination that the theorem leaves out. The negative case is not airtight: recurring batches with repeated seller states are conceivable, and the authors might recognize the repeated local optimization as their problem. The weakness is that the strongest mirror available from the theorem is computationally a direct product, while the more consequential population model would need a different 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.