Answer: Polynomial-time solvable in \(m,\tau,d,L\), with exact rational output, for both stated polynomial representations.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAssume that ϕ satisfies Additivity and the Strong Null-Player Axiom. If ϕ(v) can be calculated in time O(|N|) for every game v ∈Ψ(N), then ϕ can be calcu- lated in time O(|N|×|T |) for every set of PDT rules T . Fur- thermore, the externality-free, the McQuillin, the Macho- Stadler et al., and the Myerson values can all be calculated in time O(|N|×|T |) for every set of PDT rules T .
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(K\), a rational mass vector \(\mu\) with \(\sum_{j\in K}\mu_j=1\), and a rational polynomial \(f_\mu(x)\) in dense or unary-degree encoding with \(f_\mu(0)=0\), where \(f_\mu(x)\) is the worth of a coalition of type-mass \(x\) against its complement as one rival coalition, compute the exact continuous McQuillin allocation \(A_j=\mu_j a_j\), where \(a_j=\int_0^1\partial_j f_\mu(t\mu)\,dt\). Equivalently, compute the limit of the type allocations in replica games with \(q\mu_j\) identical agents of each type, as \(q\) ranges over multiples of the common denominator of \(\mu\).
A society is given by its support: a nonempty list \(K\) of \(\tau\) types with positive masses \(\mu_j\) encoded as binary rationals, with \(\sum_{j\in K}\mu_j=1\). Here \(\tau\) is the support size, not the number of possible types; the number of mass coordinates is \(m=\tau\).
The input also contains a polynomial \(f_\mu\in\mathbb{Q}[x_j:j\in K]\) of total degree \(d\), with \(f_\mu(0)=0\), represented either by a dense coefficient table or by an explicit monomial list with unary exponents. Coefficients are binary rationals of either sign; no monotonicity or nonnegativity is assumed. Let \(L\) be the total input bit length.
A coalition with type masses \(0\leq x_j\leq\mu_j\) has worth \(f_\mu(x)\) when its complement forms one rival coalition; at \(x=\mu\), the rival is absent. Its continuous McQuillin allocation is the vector of exact rationals \(A_j=\mu_j a_j\), where \(a_j=\int_0^1\partial_j f_\mu(t\mu)\,dt\).
For the replica interpretation, each of the \(q\mu_j\) agents of type \(j\) has mass \(1/q\), and the induced coalition worth is \(w_q(S)=f_\mu((|S\cap N_j|/q)_{j\in K})\). McQuillin payoffs are the ordinary Shapley payoffs of this induced worth function; type allocations sum the payoffs of all agents of that type.
Is computing the exact continuous McQuillin allocation solvable in polynomial time in \(m,\tau,d,L\), or is it \(\mathrm{NP}\)-hard?
For finite games represented by partition decision trees of total size \(B\), McQuillin values are computable in \(O(nB)\) time, where \(n\) is the number of agents. [Skibski et al.](https://ojs.aaai.org/index.php/AAAI/article/view/9306)
The continuous formula is the Aumann–Shapley allocation; for explicitly represented multilinear functions with \(s\) nonzero monomials, each coordinate is computable in \(O(\tau^2s)\) arithmetic operations. This restricted result does not cover arbitrary polynomial inputs as stated here. [Sun and Sundararajan](https://arxiv.org/html/1102.0989)
Computing the exact continuous McQuillin allocation is polynomial-time solvable in \(m,\tau,d,L\), for both input representations in the question. The algorithm handles arbitrary exponents and coefficients of either sign. Its running time is polynomial in the bit model, not merely in the number of arithmetic operations.
Index the support by \(K=\{1,\ldots,m\}\), where \(m=\tau\). Write the explicitly represented polynomial as
\( \displaystyle f_\mu(x)=\sum_{r=1}^{s}c_r x^{\alpha^{(r)}},\qquad x^\alpha=\prod_{i=1}^{m}x_i^{\alpha_i}. \)
Discard zero coefficients and constant terms. This preserves the polynomial because its total constant coefficient is zero by \(f_\mu(0)=0\). For every remaining term, let
\( \displaystyle k_r=|\alpha^{(r)}|=\sum_{i=1}^{m}\alpha_i^{(r)},\qquad 1\leq k_r\leq d. \)
Consider one monomial \(c_r x^{\alpha^{(r)}}\). If \(\alpha_j^{(r)}=0\), its contribution to \(A_j\) is zero. Otherwise, differentiation and substitution give
\( \displaystyle \mu_j\partial_j\!\left(c_r x^{\alpha^{(r)}}\right)\big|_{x=t\mu} =c_r\alpha_j^{(r)}t^{k_r-1}\prod_{i=1}^{m}\mu_i^{\alpha_i^{(r)}}. \)
Since \(k_r\geq1\), integrating \(t^{k_r-1}\) from zero to one gives \(1/k_r\). Differentiation and integration distribute over the finite monomial sum. Therefore
\( \displaystyle \boxed{A_j=\sum_{r=1}^{s}c_r\frac{\alpha_j^{(r)}}{k_r}\prod_{i=1}^{m}\mu_i^{\alpha_i^{(r)}}.} \)
This calculation does not require multilinearity, monotonicity, or nonnegative coefficients.
As a consistency check, summing over coordinates yields
\( \displaystyle \sum_{j=1}^{m}A_j =\sum_{r=1}^{s}c_r\left(\frac{\sum_j\alpha_j^{(r)}}{k_r}\right)\mu^{\alpha^{(r)}} =f_\mu(\mu). \)
If no nonzero terms remain, return the zero vector. Otherwise \(d\geq1\). Write the input rationals as
\( \displaystyle \mu_i=\frac{p_i}{q_i},\qquad c_r=\frac{u_r}{b_r}, \)
with positive denominators. Define the common denominator
\( \displaystyle T=\left(\prod_{r=1}^{s}b_r\right)d!\prod_{i=1}^{m}q_i^d. \)
For each monomial, compute the integers
\( \displaystyle P_r=\prod_i p_i^{\alpha_i^{(r)}},\qquad Q_r=\prod_i q_i^{\alpha_i^{(r)}},\qquad V_r=b_rk_rQ_r. \)
The integer \(V_r\) divides \(T\): \(b_r\) divides \(\prod_\ell b_\ell\), \(k_r\) divides \(d!\), and \(Q_r\) divides \(\prod_i q_i^d\) because every exponent is at most \(d\). Multiplying these three divisibilities establishes \(V_r\mid T\).
Initialize \(N_j=0\) for all coordinates. For each monomial, update
\( \displaystyle N_j\leftarrow N_j+u_r\alpha_j^{(r)}P_r(T/V_r). \)
The quotient \(T/V_r\) is exact. Furthermore,
\( \displaystyle \frac{u_r\alpha_j^{(r)}P_r(T/V_r)}{T} =c_r\frac{\alpha_j^{(r)}}{k_r}\mu^{\alpha^{(r)}}. \)
Thus the final answer is \(A_j=N_j/T\). Reduce each fraction using a greatest common divisor, with zero represented canonically.
Let \(\ell(z)\) denote the binary length of an integer, including a sign bit when needed. Because the rational data are part of the input,
\( \displaystyle \sum_r\ell(b_r)\leq O(L),\qquad \sum_i\ell(q_i)\leq O(L), \)
and each input numerator has length \(O(L)\). Consequently,
\( \displaystyle \ell(T)=O\!\left((d+1)L+d\log(d+1)\right). \)
Also, since \(\sum_i\alpha_i^{(r)}=k_r\leq d\),
\( \displaystyle \ell(P_r),\ell(Q_r)=O(dL). \)
Each integer summand added to \(N_j\) therefore has bit length at most
\( \displaystyle O\!\left((d+1)L+d\log(d+1)\right). \)
Summing at most \(s\) signed integers increases this bound by at most \(O(\log(s+1))\): the absolute value of a sum is bounded by the sum of the absolute values. Thus cancellation causes no difficulty, and all intermediate integers and final output fractions have polynomial bit length.
Using repeated multiplication, constructing \(T\) takes \(O(s+md+d)\) integer operations. Computing all monomial products and updating all coordinates takes \(O(s(m+d))\) additional integer operations. Integer addition, multiplication, exact division, and greatest common divisor computation all have polynomial running time in their operand bit lengths. Hence the entire algorithm runs in time polynomial in \(m,d,L,s\).
For an explicit monomial list, \(s\) is at most the number of listed entries and hence \(O(L)\). For a dense coefficient table, scanning its explicitly stored entries takes polynomial time in \(L\), and again \(s=O(L)\). Neither representation requires expanding a succinctly encoded polynomial.
This proves polynomial bit complexity in \(m,\tau,d,L\).
The cited [Sun–Sundararajan paper](https://arxiv.org/html/1102.0989) studies efficient attribution for explicitly represented multilinear functions. The calculation above directly covers the arbitrary polynomial inputs here: each monomial contributes according to its exponent vector divided by its total degree.
The finite-replica interpretation does not require constructing a replica game for this computation. The target allocation is given by the continuous integral, which the formula above evaluates exactly.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned continuous computation problem. The monomial formula is correct, the integer algorithm implements it exactly, and the bit bounds establish polynomial running time for both stated representations. No major or minor issues were found.
Setting \(m=\tau\) correctly uses the number of supported types as the number of variables.
Discarding zero coefficients is harmless. Discarding constant terms also preserves the polynomial under the stated condition \(f_\mu(0)=0\): their combined coefficient is zero. Every remaining monomial has positive total degree, so the subsequent division by its degree is defined.
The zero polynomial is handled explicitly by returning the zero vector before constructing a denominator involving the degree. Variables absent from every monomial also receive zero automatically.
For a monomial with \(\alpha_j>0\), the displayed differentiation and substitution are correct:
\[ \mu_j\partial_j(c x^\alpha)\big|_{x=t\mu} =c\alpha_j t^{|\alpha|-1}\prod_i\mu_i^{\alpha_i}. \]
The factor \(\mu_j\) restores the power removed by differentiation. The exponent of \(t\) is the total degree minus one.
If \(\alpha_j=0\), the derivative is identically zero; the separate treatment avoids expressions with negative exponents.
Because every retained total degree \(k_r\) is a positive integer, the integral used is valid and equals \(1/k_r\). Differentiation and integration distribute over the finite sum without requiring any convergence argument. Thus the claimed formula
\[ A_j=\sum_r c_r\frac{\alpha_j^{(r)}}{k_r} \prod_i\mu_i^{\alpha_i^{(r)}} \]
follows directly from the allocation definition.
No sign restriction or multilinearity assumption is used. Summing this formula over coordinates gives the displayed efficiency identity, since \(\sum_j\alpha_j^{(r)}=k_r\). This check is correct.
All input denominators are positive, so \(T\) is a positive integer.
The divisibility assertion \(V_r\mid T\) is valid. Each of the three factors in \(V_r=b_rk_rQ_r\) divides its corresponding factor in the displayed product defining \(T\). Multiplying these divisibilities is legitimate even when the factors share primes; coprimality is unnecessary.
In particular, every exponent is at most \(d\), and every positive integer \(k_r\leq d\) divides \(d!\).
The update identity is algebraically correct. Dividing each accumulated numerator by \(T\) therefore yields exactly the monomial sum already established. Negative coefficients produce signed integer updates and do not affect exact divisibility. Greatest common divisor reduction preserves each rational value, including the separately specified canonical representation of zero.
The denominator bound is correct. The coefficient-denominator product contributes \(O(L)\) bits, the mass-denominator powers contribute \(O(dL)\), and \(d!\) contributes \(O(d\log(d+1))\). Hence the stated bound on the bit length of \(T\) follows.
The bounds on \(P_r\) and \(Q_r\) are also valid: their exponents sum to at most \(d\), and input numerator and denominator lengths are bounded by the input length.
The summand bound includes all necessary factors: the coefficient numerator, the exponent, the mass-numerator product, and the exact quotient \(T/V_r\). Their combined bit length fits the stated asymptotic bound.
Accumulating at most \(s\) signed summands increases the worst-case length by at most \(O(\log(s+1))\). This bound applies to partial sums as well as final sums, so cancellation introduces no intermediate-size problem.
The operation counts for constructing \(T\), forming monomial products by repeated multiplication, and updating coordinates are consistent with the loops described. Polynomial-time integer arithmetic and greatest common divisor computation consequently give polynomial bit complexity, rather than only an arithmetic-operation bound.
For an explicit monomial list, the number of retained entries is \(O(L)\). Unary exponents permit their explicit processing within the claimed parameter bounds.
For a dense coefficient table, the algorithm scans explicitly stored coefficients. The number of entries is bounded by the input length; the argument does not assume that a potentially enormous dense table can be accessed without paying for its representation.
The description of the [Sun–Sundararajan paper](https://arxiv.org/html/1102.0989) as studying efficient attribution for multilinear functions is accurate. Its results are background, not an unverified theorem application supporting the algorithm.
The task defines the continuous allocation by the integral. Consequently, evaluating that integral suffices; proving convergence of finite replica allocations is not an outstanding obligation for this question.
The proof establishes exact polynomial-time computation in the requested parameters for both representations. No additional clarification or repair is needed.
⟨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.