| paper | d4-conf-aaai-2005-0222 |
| 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→P discrete result → its continuous mirror
Answer: The problem is in \(\mathrm P\): every valid instance has answer NO, because every admissible split preserves total payoff exactly. Decision takes \(O(1)\) time on promised valid inputs, or \(O(L)\) time if the full input is consumed. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given a finite skill set \(K\), a rational characteristic function \(v:2^K\to\mathbb{Q}\), supported skill portfolios \(a_t\in\{0,1\}^K\) with rational masses \(\mu_t\ge 0\) summing to \(1\), and a target type \(t^\star\), set \(x=\sum_t\mu_t a_t\) and let \(F:[0,1]^K\to\mathbb{R}\) be the multilinear extension of \(v\). Under the payment rule \(\pi_x(z)=z\cdot\int_0^1\nabla F(\lambda x)\,d\lambda\), determine whether there are a finite \(q\) and rational portfolios \(z_1,\ldots,z_q\ge 0\) with \(\sum_j z_j=a_{t^\star}\) such that \(\sum_j\pi_x(z_j)>\pi_x(a_{t^\star})\).
Types are recurring skill portfolios \(a_t\) with masses \(\mu_t\); aggregate per-capita capacity \(x\) sets Aumann–Shapley marginal prices through \(F\). A focal participant chooses a finite split of its portfolio, and the question is whether the aliases’ total payment exceeds the truthful payment.
No specified sequence shows that Shapley values in finite games with repeated skill categories converge to the chosen Aumann–Shapley rule, so the proposed model is not established as a limit of this exact theorem.
fatal: False
The mirror addresses only Theorem 8’s false-name gain question. It leaves the paper’s other results on solution concepts, collusion, skill hiding, axiomatic characterization, and the least anonymity-proof core untouched.
The strongest anchor is Theorem 8, proved in this paper: when value is divided by the Shapley value over agents, deciding whether an agent can benefit by submitting false names is NP-complete. The paper says its proof reduces from satisfiability, though it omits the details. This is the paper’s clearest computational result about manipulation, and a useful mirror would ask whether that hardness survives when the population and its skill resources become continuous.
Consider a platform coordinating many small firms or contractors. There may be millions of participants but only a modest number of recurring skill profiles; each profile includes all relevant capabilities, prices, and other attributes. Let \(K\) be a finite set of skill categories, and let each type \(t\) have a portfolio \(a_t\in\{0,1\}^{K}\). The society is a rational distribution \(\mu\) over the \(\tau\) supported types, with \(\sum_t\mu_t=1\) and \(N\gg\tau\). Treat skills as divisible capacity—such as skill-hours—so several participants can supply the same category. That is a plausible co-modification of the paper’s skill model, which explicitly allows skills to represent resources.
My lead is Continuous False-Name Gain under Aumann–Shapley. An instance consists of \(K\), a rational characteristic function \(v:2^K\to\mathbb{Q}\) with \(v(\varnothing)=0\), the supported portfolios and masses \((a_t,\mu_t)\), and a target type \(t^\star\) with positive mass. Let \(F:[0,1]^K\to\mathbb{R}\) be the multilinear extension of \(v\), and let \(x=\sum_t\mu_t a_t\) be the society’s aggregate skill capacity. Define the continuous Shapley analogue’s payment for portfolio \(z\) by
\[
\pi_x(z)=z\cdot\int_0^1\nabla F(\lambda x)\,d\lambda.
\]
The question is whether some participant of type \(t^\star\) can submit \(q\) aliases carrying rational portfolios \(z_1,\ldots,z_q\geq 0\), with \(\sum_{j=1}^q z_j=a_{t^\star}\), so that the aliases’ combined payment \(\sum_j\pi_x(z_j)\) exceeds the truthful payment \(\pi_x(a_{t^\star})\). The same comparison applies to any positive mass of identical participants making that split.
This problem is immediately tractable: \(\pi_x\) is linear in the submitted portfolio, so \(\sum_j\pi_x(z_j)=\pi_x(a_{t^\star})\). No false-name split can produce a gain under this continuous allocation rule. That is a meaningful Class A boundary result: the finite Shapley manipulation hardness in Theorem 8 does not survive this divisible-resource, continuous-Shapley model. It also generates a useful next question: how quickly does the finite Shapley false-name gain disappear as the population grows and resource granularity shrinks?
The soft spot is substantial. Theorem 8 studies Shapley payments to discrete agents with individually owned skills; this mirror uses Aumann–Shapley payments for divisible skill capacity. Divisibility and the continuous allocation rule are precisely what make splitting invariant. The paper’s authors may accept this as a limit question about their false-name manipulation problem, especially in a capacity-based coalition setting, but they could reasonably reject it as a mirror of Theorem 8’s exact payoff rule. The case rests on preserving the same skill-splitting manipulation and incentive comparison while making the continuum assumptions explicit.
Theorem 8 is the paper’s one serious computational anchor: deciding whether an agent can gain by splitting its skills among false names is NP-complete. The difficulty comes from a particular discrete operation: repartitioning one agent’s finite set of skills into named players, then recomputing Shapley shares over player orderings.
That structure is awkward to carry into a population distribution. In the paper, skills are unique and agents’ skill sets are disjoint. A type that preserves every distinction the game uses must therefore retain the agent’s particular skill inventory; grouping agents by broad capability can lose information relevant to \(v\) and to the possible partitions. Allowing many copies of the same skill profile is a sensible co-modification, especially given the paper’s resource interpretation, but it changes the game from a set function over unique skills to one over divisible capacities.
The proponent’s Aumann–Shapley model is a clear version of that change. For fixed \(x\), its payment satisfies
\[
\sum_j \pi_x(z_j)=\pi_x\!\left(\sum_j z_j\right).
\]
So splitting a portfolio cannot change its total payment. That identity is mathematically clean, but the proposed model has not established that this rule is the limit of the paper’s Shapley game under a specified high-multiplicity sequence. Its answer follows from the additivity built into the chosen continuous rule; the finite partition search from Theorem 8 is no longer the computational task.
The strongest alternative would keep one target agent atomic inside a continuous background of other agent types. That preserves the false-name decision, but the target’s finite skill partition remains the source of the combinatorics; the background distribution does not itself relax it. Making the target a positive mass of divisible capacity instead brings back the Aumann–Shapley invariance. A precise convergence or approximation theorem between these models could be a worthwhile project, but it would need to supply the missing bridge.
So the case against the *proposed* mirror is that it either retains the atomic manipulation problem or replaces it with a capacity model whose split invariance is built in. The case against any worthwhile mirror is weak: Theorem 8 is a genuine computational result, and a finite-to-continuum approximation question may survive. I would reject this formulation as an established continuous complexity mirror, while leaving that approximation direction open.
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.