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.
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateWhen the Shapley value over agents is used to distribute the value, it is NP-complete to determine whether an agent can benefit by submitting false names. The proof is by reduction from satisfiability. We omit the details due to limited space. Conclusions We demonstrated that traditional solution concepts of coali- tional games—namely the Shapley value, core, least core, and nucleolus—are vulnerable to various kinds of manip- ulations in open anonymous environments such as the In- ternet.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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})\).
Let \(K\) be a finite skill set with \(m=|K|\ge 1\), and let \(v:2^K\to\mathbb Q\) be supplied as its complete table; values may have either sign, and no monotonicity is assumed.
A society is given by its support: the list of its \(\tau\) distinct nonzero portfolios \(a_t\in\{0,1\}^K\), each with positive binary rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; portfolios of different types may overlap.
The input specifies a supported target type \(t^\star\). Set \(x=\sum_t\mu_t a_t\), let \(F\) be the multilinear extension of \(v\), and define \(\pi_x(z)=z\cdot\int_0^1\nabla F(\lambda x)\,d\lambda\).
A false-name split consists of a finite integer \(q\ge 2\) and nonzero portfolios \(z_j\in\mathbb Q_{\ge 0}^K\) satisfying \(\sum_{j=1}^q z_j=a_{t^\star}\). All resulting identities use the same aggregate \(x\); splitting conserves every skill coordinate and does not hide skills.
The decision problem asks whether such a split satisfies \(\sum_{j=1}^q\pi_x(z_j)>\pi_x(a_{t^\star})\). Let \(L\) be the total binary input length, including the complete value table; state running times in \(m,\tau,L\).
Is this continuous false-name manipulation decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite agents with disjoint skill sets, deciding whether false-name splitting increases an agent's Shapley payoff is stated to be \(\mathrm{NP}\)-complete. [Source](https://cdn.aaai.org/AAAI/2005/AAAI05-080.pdf)
No complexity classification for exactly the continuous decision problem above was located in the literature search.
The decision problem is in \(\mathrm P\): every valid instance has answer NO. Every admissible split preserves the target’s total payoff exactly. This holds for arbitrary signed values and overlapping portfolios.
The multilinear extension is the polynomial
\(F(y)=\sum_{S\subseteq K}v(S)\prod_{k\in S}y_k\prod_{k\in K\setminus S}(1-y_k).\)
For each coordinate, \(x_k=\sum_{t=1}^{\tau}\mu_t a_{t,k}\) belongs to \([0,1]\), because the masses are positive and sum to one and each \(a_{t,k}\) belongs to \(\{0,1\}\). Consequently, the path \(\lambda x\), for \(\lambda\in[0,1]\), lies in \([0,1]^K\).
Since \(F\) is a polynomial, its gradient is continuous. Thus the vector
\(g(x):=\int_0^1\nabla F(\lambda x)\,d\lambda\)
exists, with integration performed coordinatewise. The stipulated payoff is therefore
\(\pi_x(z)=z\cdot g(x).\)
Crucially, \(g(x)\) is the same vector for the original identity and every resulting identity: the task expressly fixes the aggregate \(x\) throughout the split.
Let \(q\ge 2\) and nonzero rational portfolios \(z_1,\ldots,z_q\) be any admissible split. By coordinate conservation, \(\sum_{j=1}^{q}z_j=a_{t^\star}\). Distributivity of the dot product over a finite sum gives
\(\sum_{j=1}^{q}\pi_x(z_j)=\sum_{j=1}^{q}z_j\cdot g(x)=\left(\sum_{j=1}^{q}z_j\right)\cdot g(x)=a_{t^\star}\cdot g(x)=\pi_x(a_{t^\star}).\)
Hence the required strict inequality never holds.
This is not caused by an absence of admissible splits. Since the supported target portfolio is nonzero, \(q=2\) with \(z_1=z_2=\tfrac12a_{t^\star}\) is always admissible. The equality above covers this split and every other admissible split, for every finite \(q\).
The algorithm returns NO.
On the promised valid inputs, its running time is \(O(1)\), independent of \(m,\tau,L\), with \(O(1)\) auxiliary space. If the implementation consumes the entire input before returning, its running time is \(O(L)\). Neither implementation needs to compute \(x\), the integral, or any payoff.
If malformed encodings are also assigned answer NO, the resulting language is empty. It cannot be \(\mathrm{NP}\)-hard under polynomial-time many-one reductions: a nonempty language in \(\mathrm{NP}\), such as satisfiability, has a YES instance, which no such reduction could map to a YES instance of the empty language.
The cited paper’s Theorem 8 states \(\mathrm{NP}\)-completeness for manipulation when the Shapley value over agents is used. Its Definition 6 averages marginal contributions over orderings of the agent set, which changes when false identities are introduced. ([Yokoo et al., Definitions 4 and 6, Theorem 8](https://cdn.aaai.org/AAAI/2005/AAAI05-080.pdf))
Here, the given payoff formula instead assigns every identity the same coordinate coefficients \(g(x)\). Conserving the sum of portfolios therefore conserves the sum of payoffs. The proof settles the full continuous problem as stated, including overlapping types and nonmonotone, signed value tables.
⟨structured verdict parsed — rendered above⟩
The prover fully resolves the task. The payoff invariance argument is correct, covers every admissible split, and establishes a constant-time decision algorithm on valid inputs. No major or minor mathematical issues were found.
\[
\sum_{j=1}^{q}\pi_x(z_j)
=\left(\sum_{j=1}^{q}z_j\right)\cdot g(x)
=a_{t^\star}\cdot g(x)
=\pi_x(a_{t^\star}).
\]
The calculation applies to every finite integer \(q\ge 2\) and every admissible rational split. Neither nonnegativity of the payoff coefficients nor disjointness of supported portfolios is assumed.
No repair or additional clarification is required. The claimed classification and universal payoff equality are established as written.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.