| paper | d4-journals-jair-2009-0007 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: Continuous welfare optimization is \(\mathrm{NP}\)-hard, and pricing is \(\mathrm{NP}\)-complete. Both hardness results hold already for \(\tau=1\) with deterministic success; pricing remains hard at zero prices. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 7
statement extracted from the paper’s text layer
Given a finite task catalogue \(D\), complete requester and performer types \(\mathcal Z\) with rational masses \(\mu_z\), and a fixed trust rule aggregating type-level EQOS reports over those masses, define feasible patterns \(a\) that assign one requester unit to a valuation and cover its tasks using performer units, each selecting at most one XOR cost bid. Let \(r(a)\) be the requester type, \(q_z(a)\) the number of performer units of type \(z\) used, and \(w_a\) the pattern's expected welfare under the trust rule. Find a rational mass assignment \(x_a\geq 0\) maximizing \(\sum_a w_a x_a\), subject to \(\sum_{a:r(a)=z}x_a\leq\mu_z\) and \(\sum_a q_z(a)x_a\leq\mu_z\) for each \(z\). Determine the complexity in the task catalogue size \(M\), support size \(\tau=|\mathcal Z|\), and rational input bit length \(L\), including whether the implicit pattern LP admits efficient pricing.
A high-multiplicity trust-based task exchange with finitely many complete requester and performer types, rational masses \(\mu\), type-level trust reports, and integral allocation patterns. The decision variables are masses \(x_a\) assigned to patterns; the objective is expected social welfare, with separate requester-mass and performer-mass capacities for each type.
The mirror assumes trust reports are shared across type classes; counterpart-specific reports in the paper may make the number of complete types grow with the population, restricting the mirror to a more anonymous trust regime.
fatal: False
The mirror covers the winner-determination problem in Proposition 7. It leaves aside the incentive-compatibility, individual-rationality, and payment results, whose continuous versions would need separate analysis.
My lead is the continuous GTBM winner-determination problem, mirroring Proposition 7 in Section 5.2.2. The proposition is proved in this paper, though its proof relies on the combinatorial-exchange hardness result of Sandholm et al. (2002). In the paper’s words, the GTBM task allocation problem is NP-complete and cannot be approximated to a ratio \(n^{1-\epsilon}\) in polynomial time unless \(P=ZPP\), where \(n\) is the total number of bids and valuations. The underlying problem is to choose the task allocation that maximizes expected social utility. The paper’s proof connects it to combinatorial-exchange winner determination: bids remain the same, while trust makes valuations depend on which performers receive the tasks.
A plausible high-multiplicity regime is a large cloud-services exchange. Many business units request jobs from a finite catalogue, while many provider instances offer to perform them. Units share types when they have the same task-set valuations, XOR offers, costs, and trust reports—for example, standardized service tiers with shared reliability assessments based on common audit data. There could be millions of units but only tens or hundreds of complete types. A type includes its entire relevant trust-report vector, so agents with different opinions or costs belong to different types. Mass is the fraction of the population of that type. This is a claim about that repeated marketplace regime, not about all task-allocation settings.
Here is the continuous problem I would hand to a prover. Let \(D=\{\tau_1,\ldots,\tau_M\}\) be the finite catalogue of task kinds, and let \(\mathcal Z\) be the support of complete types, with rational masses \(\mu_z\geq 0\) summing to \(1\). Each type has the paper’s XOR list of requester valuations over task bundles, its XOR list of performer costs, and its type-level EQOS reports. Fix the trust-aggregation rule; where it aggregates reports across agents, extend that sum to the population by weighting each type’s reports by its mass.
Let \(\mathcal A\) be the implicit set of feasible one-unit allocation patterns. A pattern assigns one requester unit to one of its valuation entries and covers that entry’s tasks using performer units, each choosing at most one of its XOR cost bids, as in the paper’s allocation model. For pattern \(a\), let \(r(a)\) be its requester type, \(q_z(a)\) the number of performer units of type \(z\) it uses, and \(w_a\) its expected welfare: the requester’s expected value for the completed-task subset under the trust model, minus the costs of the selected performer bids. Each individual unit in a pattern still receives an integral bundle; only the mass of identical units can be divided among patterns.
The question is to find a rational vector \(x_a\geq 0\) maximizing
\[ \max \sum_{a\in\mathcal A} w_a x_a \]
subject to
\[ \sum_{a:r(a)=z}x_a\leq \mu_z \quad\text{and}\quad \sum_{a\in\mathcal A}q_z(a)x_a\leq \mu_z \qquad\text{for every }z\in\mathcal Z. \]
The first constraint limits how much requester mass of each type is assigned; the second limits how much performer mass it supplies. They are separate role capacities, as in the paper’s model where an agent may both request and perform. A solution is an optimal mass assignment to feasible patterns and its expected-welfare value. The input gives the task catalogue and type data, not an explicit enumeration of \(\mathcal A\); complexity should be measured in \(M\), support size \(\tau=|\mathcal Z|\), and the bit length \(L\) of the rational data.
I expect hardness to persist, tentatively as Class B, because the paper’s hardness argument points to bundle and task-assignment combinatorics, which remain when the number of copies of a type becomes continuous. But Proposition 7 does not prove that transfer: its result concerns the discrete winner-determination problem, and fractional mass can remove integrality constraints. The key prover question is whether the implicit pattern LP has a polynomial-time separation or pricing algorithm in \((M,\tau,L)\). If it does, this mirror is tractable; if pricing remains hard, one must still establish whether the discrete hardness transfers or whether the continuous problem is hard for a distinct reason. Useful next questions include whether pricing is tractable under additive valuations or restricted trust functions, and how closely the continuous optimum approximates the discrete optimum when masses are multiples of \(1/N\).
This mirrors the paper’s central computational allocation problem, not its entire mechanism: a continuous version of incentive compatibility, individual rationality, and payments would need its own analysis. The soft spot is that exact trust reports can make the number of types grow almost as large as the number of agents; the proposed regime depends on many units sharing those reports. Also, the discrete hardness reduction may rely on indivisibility that this mass model relaxes. Those are real open issues, but they do not erase the mirror: in the stated regime, task bundles, uncertainty, trust, and expected-welfare maximization are all still present.
The only anchor the proponent raises is the winner-determination problem in Proposition 7. It is a real computational result, so the argument cannot start by saying the paper has nothing to continuize.
The strongest objection is that the proposed finite type support may fail to capture the paper’s distinctive trust model. An agent’s EQOS vector records its assessments of other agents across task sets. Two agents can be grouped only if their relevant reports, costs, and valuations match; for reports about named counterparts, that means their trust relationships must match too. With trust based on personal interactions, those report profiles could be nearly unique, making the support grow with the population. The proponent’s standardized audits and shared assessments address this by replacing individual relationships with a finite set of common trust profiles. That is plausible, but it narrows the mirror to a more anonymous trust regime.
That objection does not defeat the better mirror. If reports are naturally shared within a finite set of requester and provider classes, the class-to-class trust values can be fixed from the given population distribution. The proposed mass assignment over integral allocation patterns then gives a coherent continuous winner-determination problem: the mass of each requester and provider type is limited, while each unit still receives a discrete bundle. Its implicit pattern set makes pricing the key computational question. Whether pricing is easy, hard, or equivalent to a known exchange problem cannot itself count against the mirror.
Nor does the possible degeneration of individual incentives dispose of this anchor. In a continuum, one agent’s report may have zero influence on aggregate trust, and individual externality payments may need a separate formulation. But Proposition 7 concerns winner determination, and its continuous counterpart can be asked without claiming to preserve the paper’s payment or incentive properties.
So the negative case is weak. It can question how often realistic trust markets have a small number of complete, shared report profiles, but it cannot show that no plausible regime does. The proponent’s finite-profile marketplace is a narrower model than the paper’s most individualized setting, yet it still preserves enough of the allocation problem to leave a worthwhile mirror.
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.