d4-conf-ijcai-1999-0167

Theorem 2 bounds the value of an equilibrium that is already assumed to exist; it neither computes that equilibrium nor gives an algorithmic guarantee for SAMP-SB. The mass-weighted inequality is a sensible extension, but the proposed equilibrium-finding problem is new, so the anchor lacks the required computational character.

The objection that survived

Theorem 2 applies only after an equilibrium is found; the proposed mass-market equilibrium computation is a new problem the theorem does not address.

What the mirror covers

The proposal extends Theorem 2's equilibrium-to-welfare bound to type masses; it does not cover Theorem 3's protocol characterization or the experimental efficiency results.

Open questions for a prover

The case FOR (proponent)

The paper has no named \(P\), NP-hardness, or parameterized-complexity result. Its strongest named result for this case is Theorem 2, proved by Walsh and Wellman here (with the IJCAI version giving a proof sketch and pointing to an extended proof). It says that a \((\lambda,\delta)\)-competitive-equilibrium allocation is feasible, has nonnegative value, and is within \(\sum_{\pi\in\Pi}(N_\pi\lambda_\pi+\delta)+|C|\delta\) of an efficient allocation. Here \(N_\pi\) counts producer \(\pi\)’s input requirements. This is a welfare guarantee for the equilibrium outcomes the paper studies, not a runtime theorem. [Theorem 2 in the IJCAI paper](https://www.ijcai.org/Proceedings/99-1/Papers/075.pdf)

My lead mirror is Mass Task-Allocation Equilibrium. Consider a large market for recurring jobs with supply chains: many consumers request standard tasks, producers perform standard recipes of subtasks, and suppliers provide inputs. A type specifies the full relevant description: consumer values and desired goods; a producer’s output and required inputs; or a supplier’s capacities and costs. For instance, the market might have millions of participants but only hundreds or thousands of distinct role, recipe, and value-cost types. Members of a type are interchangeable for the market’s purposes, as required by high multiplicity. The paper itself notes that price-taking is more plausible when many agents trade in each good, which makes this regime a natural fit for its market model. [Walsh and Wellman](https://www.ijcai.org/Proceedings/99-1/Papers/075.pdf)

Precisely, an instance has a finite set of goods \(G\), a task-dependency DAG, and a finite support \(T\) of types with rational masses \(\mu_t\) summing to \(1\), plus binary-rational values, costs, capacities, and recipes. A consumer type \(t\) may receive at most one unit of a desired good; let \(x_{tg}\) be the mass served with good \(g\). Let \(z_t\) be the active mass of producer type \(t\), whose members each consume their specified integral input recipe and produce one unit of output. Let \(q_{tg}\) be supplier mass of type \(t\)’s supply of good \(g\). Each variable is bounded by its type’s mass and per-member capacities. Goods must balance: for every \(g\), supplier mass plus producer output equals consumer demand plus producer input use. The per-capita value is
\[ W(x,z,q)=\sum_{t\in C,g}v_{tg}x_{tg}-\sum_{t\in S,g}c_{tg}q_{tg}. \]

The problem is: given this instance and the paper’s tolerances \(\lambda,\delta\), find nonnegative prices \(p_g\) and a feasible mass allocation satisfying the paper’s \((\lambda,\delta)\)-competitive-equilibrium conditions, or report that none exists. Each positive-mass local action must be within the relevant tolerance of that type’s best response at prices \(p\): consumers have error at most \(\delta\), producers at most \(d_t\lambda_t+\delta\), where \(d_t\) is the number of required input units for that producer type, and suppliers maximize surplus as in the paper. Members still receive whole individual bundles; mass allows a type’s members to divide among different bundles. A returned allocation should obey the mass analogue of Theorem 2’s welfare guarantee:
\[ W_\mu^*-W_\mu \le \sum_{t\in\Pi}\mu_t(d_t\lambda_t+\delta)+ \sum_{t\in C}\mu_t\delta, \]
where values are normalized per unit of population. This is the theorem’s agentwise error bound aggregated by type mass.

I expect this problem to be tractable, Class A, for the stated anonymous market model. The mass welfare problem has linear activity and balance constraints: producer complementarity remains for each individual, while a fraction of a type can be assigned the complete active recipe and the rest left inactive. A primal-dual formulation is the natural route to an allocation and supporting prices. A key proof obligation is that the resulting prices satisfy the paper’s nonnegative-price and local-surplus conditions. The next questions are whether that price support holds for every allowed task DAG, how the finite high-multiplicity instance approximates the mass solution, and whether the SAMP-SB protocol itself has a meaningful mass-market convergence result.

This mirror covers Theorem 2’s static equilibrium-to-welfare guarantee, not the paper’s full protocol analysis. Its weakest point is that the paper’s distinctive difficulty includes discrete contracts and protocol dynamics; aggregating identical agents can convexify the production choices and make equilibrium computation simpler. The case survives only when the market genuinely has many interchangeable participants and agents’ relevant actions are fully captured by their types. The integral recipe and resource contention remain in the model; the continuous step is assigning a share of each type to each whole-bundle action.

The case AGAINST (opponent, writing after the proponent)

The strongest negative is that Theorem 2 is not a computational result. It assumes an allocation is already a \((\lambda,\delta)\)-competitive equilibrium and bounds how far its value can fall below the efficient value. It gives no algorithm for finding that allocation, deciding whether one exists, or computing its prices. The proposed mass welfare bound is a legitimate continuous analogue, but it follows by weighting the same agentwise inequalities by type mass. That mirrors the theorem’s proof, not a computational problem the theorem addresses.

The proponent’s best version is to ask whether a mass equilibrium can be computed in recurring task markets with many agents sharing complete consumer, producer, and supplier types. That is a plausible high-multiplicity setting, and the paper’s own point about price-taking in thick markets supports it. But computing such an equilibrium is a new question. Once type members can split among whole-bundle actions, aggregate production and resource balance become a convexified economy; studying its prices and equilibrium computation may be worthwhile, but it does not extend a complexity result from this paper. Theorem 2 supplies a welfare guarantee *after* an equilibrium is found.

The other named result does not rescue the anchor: Theorem 3 characterizes when the protocol’s quiescent outcome is a competitive equilibrium by checking for inactive producers holding positive-price inputs. An aggregate study of SAMP-SB-D could be interesting, but that would be a new analysis of protocol dynamics, not a continuous mirror of a complexity theorem. The paper’s simulation results likewise do not state a computational-complexity claim.

This is a narrow case against treating the paper as a ChoCo complexity-mirroring target, not a convincing case that no useful continuous question exists. Repeated markets with many participants of the same task-allocation types are sensible, identity-independent societies, and Theorem 2 has a sound mass-weighted analogue. I cannot honestly rule out a worthwhile continuous market-computation study; the negative case is strongest only on the ground that the paper itself gives no computational result for that study to 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.