| paper | d4-conf-atal-2014-0073 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper’s named results concern core nonexistence and bounds on Shapley-value manipulation, not whether a computational problem can be solved or how hard it is. Its simulation uses an externally cited approximation without stating a guarantee as a result of this paper. The proposed population welfare optimization is coherent, but it has no qualifying named result to anchor the mirror.
fails bit a — no named computational result to mirror
The core and Shapley manipulation results do not yield a qualifying computational anchor; the paper’s simulation reports empirical welfare and revenue comparisons without a stated guarantee.
There is no qualifying anchor in this paper: it has no numbered theorem, lemma, corollary, or proposition that classifies a computational problem as hard, tractable, FPT, or similar. The closest named results are Lemma 1, which shows that the SAG core may be empty, and Theorems 1–3, which bound how a buyer’s Shapley value can change under a split or bluff. Those are game-theoretic statements, not computational-complexity results. The paper’s mention of the multidimensional knapsack problem being NP-hard is not a numbered result of this paper; it is background for the simulation.
A plausible population regime is cloud allocation with many clients running tasks from a modest set of demand-and-value types, and many servers from a modest set of capacity types. One could let \(\mu_t\) be the mass of clients of type \(t=(d_t,w_t)\), \(\rho_s\) the mass of servers of capacity type \(s\), and \(x_{t,s}\) the mass of type-\(t\) clients assigned to type-\(s\) servers. The underlying welfare question would maximize \(\sum_{t,s}w_t x_{t,s}\), subject to client-mass and resource-capacity constraints. That is a recognizable continuous-population analogue of the paper’s assignment problem.
But it is not anchored by a qualifying named result, so I cannot present it as the requested continuous problem per anchor. Extending Theorems 1–3 would also require defining a suitable continuum version of the Shapley value; their claims depend on finite agent permutations and on quantities such as \(|N|\). That is the positive case’s weakest point, and it prevents this paper from supporting the requested complexity-focused mirror on its own.
The strongest case against a ChoCo mirror is that the paper gives no computational result to mirror. Lemma 1 concerns core nonexistence; Theorems 1–3 bound Shapley values and manipulation gains. None classifies an algorithmic problem’s complexity. The multidimensional knapsack hardness is cited as background, and the paper uses an approximation in its simulation; it does not establish a complexity result of its own.
The Shapley results do not yield an obvious continuous version. They average marginal contributions over permutations of a finite set of agents, and their deviations are by individual buyers. In an atomless population, a single buyer has zero mass and the ordinary individual contribution vanishes. Keeping the permutation model means retaining atomic agents; replacing it with a type-level or Aumann–Shapley value requires a new allocation rule. Likewise, treating a positive mass of buyers as one manipulator changes the paper’s individual split and bluff questions into cohort deviations. These are possible research questions, but they do not directly continue the stated results.
The best version of the proposed welfare mirror is more convincing than a simple assignment LP. Each seller has its own multidimensional packing constraint, so aggregate capacity constraints alone can admit infeasible assignments. A configuration LP could instead represent the mass of each seller type running each feasible bundle of tasks, with a pricing problem for finding those bundles. This is a coherent continuous-population optimization problem, and repeated client and server types are plausible in cloud settings.
That candidate is also the negative case’s main weakness: it is recognizable as an extension of the paper’s explicit allocation question, even though the paper proves no complexity result about that question. I would count it as an adjacent computational project, not as a mirror of a named result. I would not argue that high multiplicity is implausible or that no continuum model can be built; the narrower and stronger objection is that the paper’s actual results concern finite-agent solution concepts and strategic deviations, while its most promising continuous model opens a new welfare-optimization line of work. If the programme accepts a central question without a corresponding computational result as an anchor, the case against this paper is weak, and I cannot honestly sustain the universal claim that no worthwhile mirror exists in any scenario.
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.