Answer: Polynomial-time solvable: the exact allocation function belongs to \(\mathrm{FP}\) for fixed \(d\).
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet G be a subgroup of Sn and Aπ be a probability distributioin on Sn constant on the right cosets {G · π}π, i.e. Aπ = Agπ for all g ∈G and π ∈Sn. Then P Aπ mπ is a G-symmetric quasi-value.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational positive type masses \(\mu\), a rational polynomial worth function \(V\) of fixed total degree with \(V(0)=0\), a finite group \(H\) permuting equal-mass types, and an \(H\)-invariant rational distribution \(\Pi\) over coordinatewise nondecreasing piecewise-linear paths from \(0\) to \(\mu\), compute exactly, for each type \(t\), \(\phi_t(V)=\mathbb{E}_{q\sim\Pi}\!\left[\int_0^1 \partial_t V(q(s))\,\dot q_t(s)\,ds\right]\).
A society is given by its support: a list of \(\tau\geq1\) types with positive binary rational masses \(\mu_t\). Here \(\tau\) is the support size, not the number of possible types; set \(m=\tau\), the number of coordinates. Masses need not sum to one.
The worth function \(V:[0,\mu]\to\mathbb R\) is specified by its rational monomial coefficients, with arbitrary signs, total degree at most a fixed constant \(d\), and \(V(0)=0\).
A group \(H\leq S_\tau\) is specified by \(r\) permutation generators preserving \(\mu\). Its coordinate action is \((hq)_t=q_{h^{-1}(t)}\).
The distribution \(\Pi\) is specified explicitly by \(K\) continuous, coordinatewise nondecreasing piecewise-linear paths \(q^{(j)}:[0,1]\to[0,\mu]\), each from \(0\) to \(\mu\), and positive binary rational probabilities \(p_j\) summing to one. Paths are specified by rational break times and rational vertices, with \(S\) segments in total. It is promised that \(q\) and \(hq\) have the same distribution for every \(h\in H\).
Compute the total allocation to each type, \(\phi_t(V)=\sum_{j=1}^{K}p_j\int_0^1\partial_tV(q^{(j)}(s))\dot q^{(j)}_t(s)\,ds\), as an exact rational number. Let \(L\) be the total binary input length; state running times in \(m,\tau,L,K,S,r\), with \(d\) fixed.
Is this exact allocation problem solvable in polynomial time, or is it NP-hard under polynomial-time Turing reductions?
For finite cooperative games, a probability distribution on arrival orders invariant under relabeling by a group yields an expected marginal allocation that is linear, efficient, null-player respecting, and equivariant under that group; this is an existence statement without a complexity classification. [Kubena–Franek](https://arxiv.org/abs/1207.4738)
For continuous path allocations, rational-threshold comparison is known to be decidable for rational worth functions and finite mixtures of rational piecewise-linear paths; that result does not classify the exact polynomial allocation problem above. [Baier–Funke–Majumdar](https://cdn.aaai.org/ojs/17395/17395-13-20889-1-2-20210518.pdf)
The exact allocation problem is polynomial-time solvable. For fixed \(d\), every allocation is rational, its binary encoding has polynomial length, and all allocations can be computed using polynomially many bit operations.
The algorithm uses the explicitly listed paths. The group-invariance promise does not require enumerating \(H\) or its orbits.
Write the polynomial as
\(V(x)=\sum_{\alpha\in A}c_\alpha x^\alpha\),
where \(\alpha\in\mathbb Z_{\geq0}^{m}\), \(x^\alpha=\prod_{i=1}^{m}x_i^{\alpha_i}\), and \(1\leq|\alpha|\leq d\). The constant coefficient vanishes because \(V(0)=0\). Let \(N=|A|\); then \(N\leq\binom{m+d}{d}-1\). If \(d=0\), the polynomial and all allocations are zero, so assume \(d\geq1\).
Consider a segment of path \(j\), with break times \(s_0<s_1\), initial vertex \(a\), and final vertex \(b\). Put \(\Delta=b-a\). With \(u=(s-s_0)/(s_1-s_0)\), the segment satisfies
\(q^{(j)}(s)=a+u\Delta\) and \(\dot q^{(j)}_t(s)=\Delta_t/(s_1-s_0)\).
Consequently its weighted contribution to type \(t\) is
\[
p_j\int_{s_0}^{s_1}\partial_tV(q^{(j)}(s))\dot q^{(j)}_t(s)\,ds
=
p_j\Delta_t\int_0^1\partial_tV(a+u\Delta)\,du.
\]
Here and below, the displayed identity means
\(p_j\int_{s_0}^{s_1}\partial_tV(q^{(j)}(s))\dot q^{(j)}_t(s)\,ds
=p_j\Delta_t\int_0^1\partial_tV(a+u\Delta)\,du\).
For a monomial indexed by \(\alpha\), there is no contribution when \(\alpha_t=0\). Otherwise set \(\beta=\alpha-e_t\). The binomial theorem gives
\(\prod_i(a_i+u\Delta_i)^{\beta_i}
=\sum_{0\leq k\leq\beta}
\left(\prod_i\binom{\beta_i}{k_i}a_i^{\beta_i-k_i}\Delta_i^{k_i}\right)u^{|k|}\),
where inequalities between multi-indices are coordinatewise. Since \(\int_0^1u^\ell\,du=1/(\ell+1)\), the exact contribution of this monomial is
\(p_jc_\alpha\alpha_t\Delta_t
\sum_{0\leq k\leq\beta}
\frac{\prod_i\binom{\beta_i}{k_i}a_i^{\beta_i-k_i}\Delta_i^{k_i}}{|k|+1}\).
All quantities in this formula are rational. Summing it over the segments, paths, and monomials computes precisely the requested \(\phi_t(V)\). Derivatives at the finitely many break times do not affect the integrals.
For each contributing pair \((\alpha,t)\), the number of expansion terms is
\(\prod_i(\beta_i+1)\leq2^{|\beta|}\leq2^{d-1}\):
the first inequality follows from \(b+1\leq2^b\) for every nonnegative integer \(b\). Moreover, each monomial involves at most \(d\) coordinates. Thus all segment–monomial contributions require \(O_d(SN)\) arithmetic operations.
An arithmetic-operation bound alone is insufficient; we must bound the integers manipulated.
Let \(D\) be the product of the positive denominators of all input rationals. Its binary length is \(O(L)\), because the sum of the denominator encoding lengths is at most \(L\). Every input rational has denominator dividing \(D\), and every coordinate difference \(\Delta_i=b_i-a_i\) can also be represented with denominator \(D\).
Consider an expansion term belonging to a monomial of degree \(n=|\alpha|\). Excluding its integer factors and the integration divisor, it contains:
Its denominator therefore divides \(D^{n+2}(|k|+1)\). Because
\(1\leq|k|+1\leq n\leq d\),
every such denominator divides the common denominator
\(Q=d!\,D^{d+2}\).
The algorithm can therefore accumulate each allocation as an integer numerator over \(Q\). For example, writing
\(p_j=P_j/D\), \(c_\alpha=C_\alpha/D\), \(a_i=A_i/D\), and \(\Delta_i=E_i/D\), the numerator contribution of an expansion term is exactly
\(\alpha_tP_jC_\alpha E_tD^{d-n}
\frac{d!}{|k|+1}
\prod_i\binom{\beta_i}{k_i}A_i^{\beta_i-k_i}E_i^{k_i}\).
This is an integer: both \(d-n\) and the quotient \(d!/(|k|+1)\) have the required integrality.
Every original rational has numerator magnitude at most \(2^L\), and \(D\leq2^L\). Hence the integers \(P_j,C_\alpha,A_i,E_i\) have \(O(L)\) bits. Each numerator contribution uses only a number of factors bounded in terms of fixed \(d\), so it has \(O_d(L)\) bits. There are at most \(O_d(SN)\) contributions. Since the paths and coefficients are explicitly encoded, \(S,N\leq O(L)\); summing the contributions increases the bit length by only \(O(\log L)\).
Thus \(Q\), every accumulated numerator, and every intermediate integer in this construction have \(O_d(L)\) bits. Reducing each final fraction by its greatest common divisor produces an exact rational output of \(O_d(L)\) bits per type.
Using schoolbook integer arithmetic, including division and greatest-common-divisor computation, a conservative bound is
\(O_d((L+SN+m)L^2)\)
bit operations. This includes constructing \(D\), converting input rationals to denominator \(D\), accumulating the contributions, and reducing all \(m\) outputs.
In the requested parameters, an explicitly expanded polynomial bound is
\(O_d\!\left(\left[L+rm+m(S+K)+K+S\binom{m+d}{d}\right]L^2\right)\),
with \(m=\tau\). Here \(rm\) accounts for reading the permutation generators, and \(m(S+K)\) accounts for reading the path vertices. These reading costs are already included in \(L\). There is no dependence on \(|H|\).
The derivation accommodates arbitrary coefficient signs and unnormalized positive masses. Coordinatewise monotonicity and distributional invariance are promises of the problem; the integration algorithm is valid even without them.
As a consistency check, the chain rule on every segment gives
\(\sum_{t=1}^{m}\partial_tV(q^{(j)}(s))\dot q^{(j)}_t(s)
=\frac{d}{ds}V(q^{(j)}(s))\).
Integrating, summing segments, and averaging paths therefore yields
\(\sum_{t=1}^{m}\phi_t(V)
=\sum_{j=1}^{K}p_j\bigl(V(\mu)-V(0)\bigr)=V(\mu)\),
using the common endpoints, \(V(0)=0\), and \(\sum_jp_j=1\).
The cited [Kubena–Franek paper](https://arxiv.org/abs/1207.4738) concerns group-symmetric quasi-values. The [Baier–Funke–Majumdar paper](https://cdn.aaai.org/ojs/17395/17395-13-20889-1-2-20210518.pdf) establishes threshold decidability for rational-function path attributions. Neither result is needed for this classification: the explicit polynomial representation permits the exact finite calculation proved above.
Accordingly, the function problem belongs to \(\mathrm{FP}\). If it were NP-hard under polynomial-time Turing reductions whose oracle queries satisfy the promises, replacing each oracle call with this algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The segment formula, common denominator, output-size bound, and polynomial bit-complexity bound all withstand verification. I found no major or minor mathematical issues requiring repair.
The argument uses the representation required by USER_TASK: explicit rational monomial coefficients and explicit rational piecewise-linear paths. It correctly sets \(m=\tau\), without introducing any dependence on the number of possible types.
With distinct monomials collected, the bound \(N\leq\binom{m+d}{d}-1\) correctly counts all nonconstant monomials of total degree at most \(d\). Omitting the constant term is justified by \(V(0)=0\).
The case \(d=0\) is handled correctly: the only possible polynomial is zero, so every allocation is zero.
For strictly increasing break times \(s_0<s_1\), the affine parameterization and derivative are correct:
\(q^{(j)}(s)=a+u\Delta\) and \(\dot q^{(j)}_t(s)=\Delta_t/(s_1-s_0)\).
The substitution \(u=(s-s_0)/(s_1-s_0)\) cancels the segment duration exactly. Thus the weighted segment contribution is indeed
\(p_j\Delta_t\int_0^1\partial_tV(a+u\Delta)\,du\).
This cancellation also justifies why the subsequent denominator bound does not need additional factors from break-time differences. A stationary coordinate, with \(\Delta_t=0\), contributes zero as required.
If \(\alpha_t=0\), the monomial’s partial derivative vanishes. Otherwise, setting \(\beta=\alpha-e_t\) gives the correct derivative \(c_\alpha\alpha_t x^\beta\).
The stated multivariate binomial expansion correctly indexes every choice \(0\leq k\leq\beta\), with coefficient
\(\prod_i\binom{\beta_i}{k_i}a_i^{\beta_i-k_i}\Delta_i^{k_i}\)
and power \(u^{|k|}\).
Integrating this power contributes exactly \(1/(|k|+1)\). Therefore the displayed monomial contribution has the correct coefficient, coordinate increment, and integration divisor.
All sums are finite, so summing monomial and segment contributions gives exactly the requested allocation. Polynomial partial derivatives are continuous, and the path derivative exists away from finitely many break times; its undefined values at those times do not affect the integral.
The bound
\(\prod_i(\beta_i+1)\leq2^{|\beta|}\leq2^{d-1}\)
is correct, including coordinates with \(\beta_i=0\).
Each monomial has at most \(d\) coordinates with positive exponent. Consequently, each segment–monomial pair contributes to at most \(d\) output coordinates, with a number of expansion terms bounded solely by \(d\).
The claimed \(O_d(SN)\) arithmetic-operation count for these contributions is therefore valid. Reading and preprocessing the input are separately included in the bit-complexity estimate.
The product \(D\) of all positive input denominators has binary length \(O(L)\). Every input denominator divides \(D\), and differences of input coordinates can also be represented over \(D\).
For a degree-\(n\) monomial, each expansion term contains \(n+2\) rational factors when multiplicities are counted: the probability, coefficient, coordinate increment, and \(n-1\) endpoint or increment factors. Its denominator therefore divides \(D^{n+2}(|k|+1)\).
Since \(1\leq|k|+1\leq n\leq d\), the integration divisor divides \(d!\). Hence the stated common denominator \(Q=d!D^{d+2}\) is valid for every contribution.
The proposed numerator formula agrees exactly with scaling the contribution to denominator \(Q\). In particular, the required power of \(D\) is \(D^{d-n}\), because the original rational product has denominator \(D^{n+2}\).
Both integrality assertions are correct: \(d-n\geq0\), and \(d!/(|k|+1)\) is an integer. Signs are preserved through the integer coefficient \(C_\alpha\); no positivity assumption on worth coefficients enters the calculation.
Converting an input rational to denominator \(D\) produces an integer of \(O(L)\) bits. Coordinate differences retain this bound.
Each numerator contribution multiplies only a number of factors bounded in terms of fixed \(d\), so its bit length is \(O_d(L)\). There are \(O_d(SN)\) contributions, and explicit encoding ensures \(S,N=O(L)\). Their accumulation therefore increases the bit length by only \(O(\log L)\), even when signs differ.
The common denominator, accumulated numerators, and intermediate integers consequently have \(O_d(L)\) bits. Reducing the fractions cannot increase their encoding lengths. The claimed \(O_d(L)\) output length per type is justified.
The conservative bound \(O_d((L+SN+m)L^2)\) is supported by the construction. There are \(O(L)\) input rational conversions and denominator-construction steps, \(O_d(SN)\) contribution operations, and \(m\) final reductions, all on integers of \(O_d(L)\) bits. Schoolbook arithmetic and classical greatest-common-divisor computation fit the stated bound.
The expanded bound
\(O_d((L+rm+m(S+K)+K+S\binom{m+d}{d})L^2)\)
is also valid. The explicit representation accounts for the generator and vertex reading costs within \(L\), and \(N\leq\binom{m+d}{d}-1\) justifies the substitution.
For fixed \(d\), this is polynomial in the requested parameters, with \(m=\tau\). No group enumeration is required.
The computation directly evaluates the supplied mixture. It does not need to verify the group-invariance promise or derive the mixture from generators. Thus ignoring group structure after reading the input is legitimate for this promised problem.
Arbitrary coefficient signs and unnormalized positive masses cause no difficulty. The chain-rule efficiency check is correct on each segment; continuity at the vertices permits telescoping, and the common endpoints and normalized probabilities give \(\sum_t\phi_t(V)=V(\mu)\).
The descriptions of the cited papers agree with their stated scope: [Kubena–Franek](https://arxiv.org/abs/1207.4738) studies group-symmetric quasi-values, and [Baier–Funke–Majumdar](https://cdn.aaai.org/ojs/17395/17395-13-20889-1-2-20210518.pdf) establishes threshold decidability for rational-function path attribution. Neither is used as a theorem in the algorithmic argument, so no external theorem application remains unverified.
The conclusion that the exact allocation function belongs to \(\mathrm{FP}\) follows. The final conditional statement about NP-hardness is also correct: polynomial-time Turing reductions making valid promised oracle queries could replace those queries by this algorithm, implying \(\mathrm{P}=\mathrm{NP}\). The prover appropriately does not claim an unconditional separation.
No additional clarification or mathematical 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.