d4-conf-ecai-2010-0234 (d4-conf-ecai-2010-0234)

Given a finite type set \(\mathcal T\), rational masses \(\mu_t>0\) summing to \(1\), and an explicitly encoded rational polynomial \(F\) of degree \(D\), define each admissible finite population of size \(q\) to have \(q\mu_t\) agents of type \(t\) and coalition worth \(qF(x(S))\), where \(x_t(S)=|S\cap A_t|/q\). Compute, for each type \(t\), the limit of the paper’s Pham Do–Norde value for a type-\(t\) agent as \(q\) grows through admissible sizes.

A society is given by its support \(\mathcal T\): the list of its \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types.
The input also gives \(F\in\mathbb Q[x_t:t\in\mathcal T]\) explicitly as \(m\) monomials with binary-rational coefficients and unary nonnegative integer exponents, of total degree at most \(D\). Coefficients and coalition worths may have either sign; \(L\) is the total input bit length.
An admissible population size is an integer \(q\geq1\) with \(q\mu_t\in\mathbb Z\) for every \(t\). Its agent set \(A^{(q)}\) contains \(q\mu_t\) agents of type \(t\), forming a set \(A_t^{(q)}\). For \(S\subseteq A^{(q)}\), put \(x_t(S)=|S\cap A_t^{(q)}|/q\).
For every nonempty coalition \(S\) in every partition \(\pi\) containing it, define \(w_q(S,\pi)=qF(x(S))\). Define its externality-free characteristic function by \(v_q(S)=w_q(S,\{S\}\cup\{\{a\}:a\notin S\})\) for nonempty \(S\), and \(v_q(\varnothing)=qF(0)\).
The Pham Do–Norde value of an agent is its standard Shapley value in \(v_q\); write \(\phi_t^{(q)}\) for this value for any type-\(t\) agent. The quantities to compute are \(\ell_t=\lim_{q\to\infty,\ q\text{ admissible}}\phi_t^{(q)}\), for all supported types.

Is exact computation of the type limits \((\ell_t)_{t\in\mathcal T}\) polynomial-time solvable in \(m,\tau,D,L\), or is it NP-hard?

For finite games represented by weighted MC-nets with conjunctions of literals, the Pham Do–Norde values are polynomial-time computable by conversion to simple marginal-contribution rules ([Michalak et al., 2010](https://doi.org/10.3233/978-1-60750-606-5-197)).
Existence of asymptotic values for games generated by polynomials of nonatomic measures is established in [Monderer and Neyman, 1988](https://doi.org/10.1017/CBO9780511528446.016); no complexity classification for the exact encoded problem above was verified.

Result. Exact computation of all type limits is polynomial-time solvable in the stated encoding. In fact, writing
\( F(x)=\sum_{j=1}^{m}c_j\prod_{s\in\mathcal T}x_s^{\alpha_{js}} \)
and \( d_j=\sum_{s\in\mathcal T}\alpha_{js}, \)
the answer is
\( \displaystyle \ell_t= \sum_{\substack{1\leq j\leq m\\\alpha_{jt}>0}} \frac{c_j\alpha_{jt}}{d_j} \prod_{s\in\mathcal T}\mu_s^{\alpha_{js}-\mathbf 1_{\{s=t\}}}. \)
Every exponent appearing in this formula is nonnegative.

1. Reduction to random marginal contributions. Let \( \mu=(\mu_s)_{s\in\mathcal T} \), and fix a supported type \( t \). Rationality of the masses ensures infinitely many admissible population sizes: every positive multiple of the least common multiple of their denominators is admissible.

For an admissible \( q \), choose an agent \( i \) of type \( t \). Such an agent exists because \( q\mu_t \) is a positive integer. Agents of the same type have equal Shapley values, since exchanging them preserves every coalition worth.

Assign independent uniform priorities on \( [0,1] \) to all agents, and order them by increasing priority. Ties have probability zero, and each permutation has probability \( 1/q! \). Thus this procedure generates the uniform permutation used in the Shapley formula.

Let \( U \) be the priority of \( i \), and let \( X_s \) be the number of type-\( s \) predecessors of \( i \), divided by \( q \). The marginal contribution of \( i \) is
\( q\bigl(F(X+e_t/q)-F(X)\bigr), \)
where \( e_t \) is the coordinate unit vector. This identity also holds when there are no predecessors, precisely because the specified empty-coalition worth is \( qF(0) \). Consequently,
\( \displaystyle \phi_t^{(q)} = \int_0^1 \mathbb E\!\left[ q\bigl(F(X+e_t/q)-F(X)\bigr) \mid U=u \right]\,du. \)

A nonzero empty-coalition worth causes no ambiguity: subtracting \( qF(0) \) from every coalition worth leaves every marginal contribution unchanged.

2. Proof of the limit formula. Conditional on \( U=u \), every other agent independently precedes \( i \) with probability \( u \). Therefore
\( qX_s\mid U=u \sim \operatorname{Bin}\bigl(q\mu_s-\mathbf 1_{\{s=t\}},u\bigr). \)
In particular,
\( \displaystyle \mathbb E[X_s\mid U=u] = u\mu_s-\frac{u}{q}\mathbf 1_{\{s=t\}}, \qquad \operatorname{Var}(X_s\mid U=u) \leq \frac{\mu_s}{4q}. \)

Define the compact box \( B=\prod_{s\in\mathcal T}[0,\mu_s] \), and set
\( \displaystyle H_t= \max_{s\in\mathcal T}\max_{y\in B} |\partial_s\partial_tF(y)|. \)
This number is finite because \( F \) is a polynomial. Integrating the derivative of \( \partial_tF \) along the segment between two points of the convex box \( B \) gives
\( |\partial_tF(y)-\partial_tF(y')| \leq H_t\|y-y'\|_1. \)

For every \( z\in[0,1] \), the point \( X+ze_t/q \) lies in \( B \): the distinguished agent was excluded from the predecessor counts. The fundamental theorem of calculus gives
\( \displaystyle q\bigl(F(X+e_t/q)-F(X)\bigr) = \int_0^1\partial_tF(X+ze_t/q)\,dz. \)

The conditional variance bound and Cauchy–Schwarz imply
\( \displaystyle \mathbb E\!\left[ \|X-\mathbb E[X\mid U=u]\|_1 \mid U=u \right] \leq \frac{\sum_s\sqrt{\mu_s}}{2\sqrt q} \leq \frac{\sqrt{\tau}}{2\sqrt q}, \)
where the last inequality uses \( \sum_s\mu_s=1 \). Moreover,
\( \mathbb E[X\mid U=u]+ze_t/q-u\mu=(z-u)e_t/q. \)
Hence, uniformly in \( u,z\in[0,1] \),
\( \displaystyle \mathbb E[\|X+ze_t/q-u\mu\|_1\mid U=u] \leq \frac{\sqrt{\tau}}{2\sqrt q}+\frac1q. \)

Combining these inequalities and integrating yields the explicit error bound
\( \displaystyle \left| \phi_t^{(q)} - \int_0^1\partial_tF(u\mu)\,du \right| \leq H_t\left(\frac{\sqrt{\tau}}{2\sqrt q}+\frac1q\right). \)
All integrands are bounded on the relevant compact sets, so the expectations and integrals used here are well-defined.

The right-hand side tends to zero along admissible population sizes. Thus the limit exists and equals
\( \displaystyle \ell_t=\int_0^1\partial_tF(u\mu)\,du. \)
This proof allows arbitrary coefficient signs.

3. Exact evaluation for the polynomial encoding. A monomial with \( \alpha_{jt}=0 \) contributes zero. Otherwise, \( d_j\geq1 \), and differentiation gives
\( \displaystyle \partial_t\left(c_j\prod_s x_s^{\alpha_{js}}\right)\Big|_{x=u\mu} = c_j\alpha_{jt}u^{d_j-1} \prod_s\mu_s^{\alpha_{js}-\mathbf 1_{\{s=t\}}}. \)
Since \( \int_0^1u^{d_j-1}\,du=1/d_j \), integrating this expression proves the formula stated at the beginning. Constant monomials contribute nothing.

An exact algorithm can process each monomial once:

• Compute \( d_j \) and \( P_j=\prod_s\mu_s^{\alpha_{js}} \).
• If \( d_j>0 \), add \( c_j\alpha_{jt}P_j/(d_j\mu_t) \) to each output with \( \alpha_{jt}>0 \).

Division by \( \mu_t \) is permitted because every supported mass is positive. Computing the powers by repeated multiplication uses at most \( d_j\leq D \) multiplications per monomial. Including coordinate scans and output updates, the algorithm uses \( O(m(D+\tau)+\tau) \) rational arithmetic operations.

4. Bit complexity and conclusion. Rational arithmetic must also remain polynomial in bit length. Write the input coefficients and masses as integer numerator-denominator pairs with positive denominators.

Each summand in the displayed answer involves one coefficient, at most \( D-1 \) mass factors counted with multiplicity, and the integers \( \alpha_{jt} \) and \( d_j \). Its numerator and denominator can therefore be represented using
\( B_0=O((D+1)L+\log(D+1)) \)
bits each. The intermediate products in the algorithm satisfy the same asymptotic bound.

Each output sums at most \( m \) such fractions. Using the product of their denominators as a common denominator gives numerator and denominator bit lengths
\( O(mB_0+\log(m+1)). \)
Reducing fractions cannot increase these bounds. Thus all intermediate and output bit lengths are polynomial in \( m,\tau,D,L \). Integer arithmetic and fraction reduction on integers of these sizes take polynomial time, proving the claimed bit-complexity bound.

As a consistency check, the formula also satisfies
\( \displaystyle \sum_t\mu_t\ell_t = \int_0^1\sum_t\mu_t\partial_tF(u\mu)\,du = F(\mu)-F(0), \)
by the chain rule and the fundamental theorem of calculus.

The weighted logical representation considered by [Michalak et al. (2010)](https://spiral.imperial.ac.uk/entities/publication/bf9e3297-6c89-468b-a681-9d598979883e) provides related computational context. The proof here establishes polynomial-time exact computation directly for the polynomial encoding in the question, without requiring a conversion to that representation.

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned problem. The limit argument is valid, the stated formula is correct, and the algorithm has polynomial bit complexity in the specified encoding. No major or minor issues were found.

• Admissible populations and type symmetry.

The denominators of the rational masses have a finite least common multiple, and every positive multiple of it is admissible. Thus admissible population sizes are unbounded.

For each supported type \(t\), the number \(q\mu_t\) is a positive integer, so the distinguished agent exists. Exchanging agents of the same type preserves the vector of coalition counts and therefore every coalition worth. Their Shapley values consequently coincide.

• Random-permutation representation.

Independent continuous uniform priorities generate each permutation with probability \(1/q!\). The predecessor vector \(X\) therefore gives the standard Shapley marginal contribution.

The displayed marginal
\[ q\bigl(F(X+e_t/q)-F(X)\bigr) \]
is correct for both nonempty and empty predecessor coalitions. In the latter case, the specified value \(v_q(\varnothing)=qF(0)\) is essential and is used correctly.

Subtracting \(qF(0)\) from every coalition worth preserves every marginal contribution, as asserted. There is no hidden normalization assumption.

• Conditional distribution and fluctuation bounds.

Conditional on the distinguished agent’s priority \(U=u\), each other agent independently precedes it with probability \(u\). Excluding the distinguished agent gives exactly
\[ qX_s\mid U=u\sim \operatorname{Bin}\bigl(q\mu_s-\mathbf 1_{\{s=t\}},u\bigr). \]

The conditional mean is correct. The conditional variance satisfies
\[ \operatorname{Var}(X_s\mid U=u) = \frac{(q\mu_s-\mathbf 1_{\{s=t\}})u(1-u)}{q^2} \leq \frac{\mu_s}{4q}. \]
This also covers the case where the binomial has zero trials.

Applying Cauchy–Schwarz to each centered coordinate and then summing gives the stated expected distance bound. The further inequality
\[ \sum_s\sqrt{\mu_s}\leq\sqrt{\tau} \]
follows from \(\sum_s\mu_s=1\). Both constants and their dependence on \(q\) are correct.

• Derivative estimate and convergence.

The box \(B\) is compact and convex. Every second derivative of the polynomial is continuous, so \(H_t\) is finite. The derivative estimate using \(H_t\) and the coordinate sum norm follows from integration along the segment inside \(B\).

The point \(X+ze_t/q\) lies in \(B\) for every \(z\in[0,1]\): the distinguished agent’s exclusion leaves room for the added coordinate increment. The comparison point \(u\mu\) also lies in \(B\).

The fundamental theorem of calculus gives the displayed integral representation of the marginal contribution with the correct scaling. The identity
\[ \mathbb E[X\mid U=u]+ze_t/q-u\mu=(z-u)e_t/q \]
is correct and bounds the deterministic displacement by \(1/q\).

Combining these facts yields exactly the stated error bound
\[ \left| \phi_t^{(q)}-\int_0^1\partial_tF(u\mu)\,du \right| \leq H_t\left(\frac{\sqrt{\tau}}{2\sqrt q}+\frac1q\right). \]
Boundedness on the compact box justifies the expectations and integral interchanges. The bound tends to zero along every admissible sequence tending to infinity, establishing the required limit. No sign restriction on coefficients is used.

• Exact formula and algorithm.

If \(\alpha_{jt}=0\), the corresponding derivative vanishes. Otherwise \(d_j\geq1\), the differentiated mass exponents are nonnegative, and integration of \(u^{d_j-1}\) gives \(1/d_j\). Thus the stated formula follows from the established integral expression.

Constant monomials contribute zero. Division by \(\mu_t\) in the algorithm is legitimate because the support contains only positive masses. The algorithm’s update is algebraically identical to the formula.

Repeated multiplication uses at most \(D\) power multiplications per monomial. Coordinate scans, product assembly, and output updates fit the claimed
\[ O(m(D+\tau)+\tau) \]
rational-operation bound. The constant-polynomial case, including \(D=0\), is covered.

• Bit complexity.

Each formula summand contains one input coefficient, at most \(D-1\) mass factors, and the integer factors \(\alpha_{jt}\) and \(d_j\). The stated bound
\[ B_0=O((D+1)L+\log(D+1)) \]
therefore bounds numerator and denominator lengths. The algorithm’s intermediate products and divisions also satisfy this asymptotic bound.

For an output containing at most \(m\) summands, the product of denominators gives the asserted bound
\[ O(mB_0+\log(m+1)) \]
on numerator and denominator lengths. Fraction reduction cannot increase them. Standard integer arithmetic and greatest-common-divisor computation take polynomial time at these lengths, so the arithmetic-operation bound yields a polynomial bit-time algorithm.

• Consistency and scope.

The final weighted-sum identity follows correctly from the chain rule and the fundamental theorem of calculus. It is consistent with the explicitly specified empty-coalition worth.

The cited literature provides context only; the proof does not rely on an unstated external theorem or on conversion to MC-nets. The complexity conclusion applies directly to the explicit monomial representation and unary exponents required by the task.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩