Answer: Polynomial-time solvable (\(\mathrm P\)) for \(m=1\) and fixed \(k\), with bit running time \(O_k(\tau(L+\log_2(W+1)+1)^3)\).
Theorem 5.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAn instance of Int-LeastCore given by a dynamic weighted voting game G(·) = ⟨N, w(·), q(·), t0, t1⟩, and a pair of points L, U ∈Q, L < U, can be solved in time poly(nk, W k, ||L||, ||U||, ||t0||, ||t1||).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), binary-rational masses \(\mu_t \geq 0\) summing to \(1\), nonnegative per-member weight polynomials \(a_t(s)\), a nonnegative quota polynomial \(q(s) \leq \sum_{t \in T}\mu_t a_t(s)\), rational endpoints \(s_0 \leq s_1\), and rational bounds \(L < U\), decide whether the continuous least-core value lies in \([L,U]\) for every \(s \in [s_0,s_1]\). For each \(s\), define \(\varepsilon^*(s)\) as the minimum \(\varepsilon\) over \(p_t \geq 0\) satisfying \(\sum_t \mu_t p_t = 1\) and \(\sum_t z_t p_t \geq 1-\varepsilon\) for every \(z \in [0,\mu]\) with \(\sum_t z_t a_t(s) \geq q(s)\). Use the paper’s unary-coefficient convention and fixed polynomial degree.
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a per-member weight polynomial \(a_t(s)\); the quota is a polynomial \(q(s)\). All polynomials have signed integer coefficients encoded in unary and degree at most a fixed constant \(k\). The binary-rational endpoints satisfy \(0\leq s_0\leq s_1\); throughout this interval require \(a_t(s)\geq0\) and \(0<q(s)\leq\sum_t\mu_t a_t(s)\).
A coalition is any real mass vector \(z\) satisfying \(0\leq z_t\leq\mu_t\); it wins exactly when \(\sum_t z_t a_t(s)\geq q(s)\). Payoffs are constant per member within each type and may be chosen independently at each time.
Define \(\varepsilon^*(s)\) as the minimum over \(\varepsilon\in\mathbb R\) and \(p\in\mathbb R_{\geq0}^{T}\) satisfying \(\sum_t\mu_t p_t=1\) and \(\sum_t z_t p_t\geq1-\varepsilon\) for every winning coalition \(z\), including the grand coalition.
The input also contains binary-rational bounds \(\ell<u\). Let \(L\) be the total input bit length and \(W\) the largest absolute polynomial coefficient, including constant terms; there is one weight coordinate, \(m=1\). State running times in \(m,\tau,L,W\), with \(k\) fixed.
Is deciding whether \(\varepsilon^*(s)\in[\ell,u]\) for every real \(s\in[s_0,s_1]\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite agent lists, interval least-core verification is polynomial-time for fixed polynomial degree and unary integer coefficients ([Elkind, Pasechnik and Zick, 2013](https://people.cs.umass.edu/~yzick/papers/dynamic.aamas13.pdf)). No result settling this exact mass-based interval problem was located.
The decision problem is in \(\mathrm P\) for \(m=1\) and fixed \(k\). The key fact is the exact formula
\(\displaystyle \varepsilon^*(s)=1-\frac{q(s)}{\sum_{t\in T}\mu_t a_t(s)}.\)
Consequently, interval verification reduces to testing nonnegativity of two univariate polynomials of degree at most \(k\).
Fix \(s\in[s_0,s_1]\), and abbreviate \(a_t=a_t(s)\), \(q=q(s)\), and \(B=\sum_{t\in T}\mu_t a_t\). The promised assumptions give \(0<q\leq B\).
Lower bound. Consider the coalition defined by
\(\displaystyle z_t=\frac{q}{B}\mu_t\qquad(t\in T).\)
Because \(0<q/B\leq1\), this is an admissible real mass vector. Its total weight is exactly
\(\displaystyle \sum_t z_ta_t=\frac{q}{B}\sum_t\mu_ta_t=q,\)
so it wins. For every normalized payoff vector \(p\), its payoff is
\(\displaystyle \sum_tz_tp_t=\frac{q}{B}\sum_t\mu_tp_t=\frac{q}{B}.\)
Thus every feasible pair \((\varepsilon,p)\) satisfies \(q/B\geq1-\varepsilon\), yielding
\(\displaystyle \varepsilon\geq1-\frac{q}{B}.\)
Attainment. Define \(p_t=a_t/B\). These payoffs are nonnegative and satisfy
\(\displaystyle \sum_t\mu_tp_t=\frac{1}{B}\sum_t\mu_ta_t=1.\)
Every winning coalition \(z\) then receives
\(\displaystyle \sum_tz_tp_t=\frac{\sum_tz_ta_t}{B}\geq\frac{q}{B}.\)
Therefore \((1-q/B,p)\) is feasible and attains the lower bound. This proves the formula, including the case \(q=B\) and types whose weight is zero.
Let \(B(s)=\sum_t\mu_ta_t(s)\). This is a rational-coefficient polynomial of degree at most \(k\), and the hypotheses ensure \(B(s)>0\) throughout the interval.
Using the formula above and multiplying inequalities by this positive denominator, we obtain
\(\displaystyle \varepsilon^*(s)\geq\ell\ \Longleftrightarrow\ (1-\ell)B(s)-q(s)\geq0,\)
and
\(\displaystyle \varepsilon^*(s)\leq u\ \Longleftrightarrow\ q(s)-(1-u)B(s)\geq0.\)
Define
\(\displaystyle f_\ell(s)=(1-\ell)B(s)-q(s),\qquad f_u(s)=q(s)-(1-u)B(s).\)
The required answer is therefore yes exactly when both polynomials are nonnegative everywhere on \([s_0,s_1]\). Multiplying each by a positive common denominator produces integer-coefficient polynomials without changing their signs.
For completeness, the following procedure uses only exact rational arithmetic.
Let \(f\) be one of the resulting polynomials, and write \(a=s_0\), \(b=s_1\).
If \(a=b\), evaluate \(f(a)\). If \(f\) is identically zero, it is nonnegative. Hence assume \(a<b\) and \(f\) is nonzero.
Let \(r\) be the smallest nonnegative integer for which \(f^{(r)}(a)\neq0\). Such an \(r\) exists because \(f\) is nonzero. Taylor expansion gives
\(\displaystyle f(a+h)=\frac{f^{(r)}(a)}{r!}h^r+O(h^{r+1}).\)
Thus, for sufficiently small positive \(h\), the sign of \(f(a+h)\) is the sign of \(f^{(r)}(a)\). If this sign is negative, reject.
If this sign is positive, the precise remaining criterion is:
Claim. The polynomial \(f\) is nonnegative on \([a,b]\) if and only if it has no root of odd multiplicity in \((a,b)\).
Proof. At a real root \(\alpha\) of multiplicity \(j\), write \(f(s)=(s-\alpha)^jv(s)\), where \(v(\alpha)\neq0\). Continuity implies that \(v\) has constant nonzero sign sufficiently near \(\alpha\). Therefore \(f\) changes sign across \(\alpha\) exactly when \(j\) is odd.
Starting with positive sign immediately to the right of \(a\), any first odd-multiplicity root in \((a,b)\) produces a negative interval immediately after that root. Conversely, if every interior root has even multiplicity, the sign remains positive between all successive roots. At roots the value is zero, and continuity gives nonnegative values at both endpoints. This proves the claim.
This count requires no factorization into irreducible polynomials.
Let \(d=\deg f\). The constant case is immediate. For \(d>0\), define monic polynomials
\(\displaystyle G_0=\frac{f}{\operatorname{lc}(f)},\qquad G_j=\gcd(G_{j-1},f^{(j)})\quad(1\leq j\leq d).\)
A root of \(f\) of multiplicity \(r\) has multiplicity \(\max(r-j,0)\) in \(G_j\): differentiating \(j\) times reduces its multiplicity to \(r-j\) when \(j\leq r\), and the \(r\)-th derivative is nonzero at that root. In particular, \(G_d=1\).
Set
\(\displaystyle H_j=G_{j-1}/G_j\quad(1\leq j\leq d),\qquad H_{d+1}=1.\)
A root belongs to \(H_j\), with multiplicity one, exactly when its multiplicity in \(f\) is at least \(j\). Hence the quotients \(K_j=H_j/H_{j+1}\) are polynomials, and \(K_j\) contains exactly the roots of multiplicity \(j\), each once. Consequently,
\(\displaystyle h=\prod_{\substack{1\leq j\leq d\\j\text{ odd}}}K_j\)
is squarefree and has precisely the odd-multiplicity roots of \(f\).
If \(h\) is constant, the count is zero. Otherwise form its Sturm sequence:
\(\displaystyle S_0=h,\qquad S_1=h',\qquad S_{i+1}=-\operatorname{rem}(S_{i-1},S_i).\)
Because \(h\) is squarefree, this sequence ends with a nonzero constant. Sturm’s theorem gives the number of roots in the open interval as
\(\displaystyle V(a^+)-V(b^-),\)
where \(V\) counts sign variations in the sequence.
The one-sided signs are computable exactly even when an endpoint is a root of a sequence member. For a nonzero polynomial \(S_i\), let \(j\) be its first nonvanishing derivative order at the endpoint \(x\). Its right-hand sign is the sign of \(S_i^{(j)}(x)\); its left-hand sign is the sign of \((-1)^jS_i^{(j)}(x)\). All these evaluations are rational.
Thus the procedure decides nonnegativity exactly, including roots at either endpoint and roots of arbitrary multiplicity.
Let \(N=L+\lceil\log_2(W+1)\rceil+1\).
To construct \(B\), take the product \(D\) of the mass denominators. Its bit length is at most \(L\). For each coefficient position, the corresponding integer coefficient of \(DB\) is a sum of \(\tau\) explicitly computable terms. Since the masses are positive and sum to one, each coefficient of \(B\) has absolute value at most \(W\). Thus the coefficients of \(DB\) have bit length \(O(N)\).
Including the denominators and numerators of \(\ell,u\), and clearing denominators in \(f_\ell,f_u\), preserves the bound \(O(N)\) on coefficient bit length.
For fixed \(k\), the nonnegativity procedure performs a number of rational arithmetic operations bounded solely by \(k\). Every intermediate rational number has bit length \(O_k(N)\): polynomial division, gcd computation, differentiation, and endpoint evaluation each involve only a bounded number of operations on such numbers. Using elementary integer arithmetic and a conservative cubic bound for rational operations gives the bit-running-time bound
\(\displaystyle m=1:\qquad O_k\!\left(\tau\bigl(L+\log_2(W+1)+1\bigr)^3\right).\)
With unary coefficient encoding, \(\log_2(W+1)=O(L)\), so this is \(O_k(\tau L^3)\), hence polynomial in total input length. There is no enumeration of possible types or discrete coalitions.
The supplied validity conditions can also be checked within the same bound: test \(a_t(s)\geq0\) and \(B(s)-q(s)\geq0\) by the procedure above; test strict positivity of \(q\) by positive endpoint values together with absence of roots in the open interval.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem correctly: the decision problem is in \(\mathrm P\) for \(m=1\) and fixed \(k\). The exact value formula, interval reduction, root-counting procedure, and stated bit-complexity bound are valid. No repairs or additional clarifications are needed.
The promised inequalities \(0<q\leq B\) ensure that every division by \(B\) is valid.
The proposed coalition \(z_t=(q/B)\mu_t\) satisfies every coordinate constraint because \(0<q/B\leq1\). Its weight equals \(q\), so it wins under the task’s inclusive winning condition. Its payoff equals \(q/B\) for every normalized payoff vector. Thus the claimed lower bound applies to every feasible pair.
The proposed payoff vector \(p_t=a_t/B\) is nonnegative and normalized. Every winning coalition receives at least \(q/B\), so it attains that lower bound. Consequently,
\[
\varepsilon^*(s)=1-\frac{q(s)}{B(s)}.
\]
This verifies the minimum itself, rather than merely an infimum. The argument also covers zero-weight types and \(q=B\). The grand coalition satisfies the resulting constraint because its payoff is \(1\) and \(q/B\leq1\).
Finding: Correct and complete.
The polynomial \(B(s)\) has rational coefficients and degree at most \(k\). Its strict positivity throughout the interval follows from \(B(s)\geq q(s)>0\).
Both inequality transformations have the correct signs:
\[
1-\frac qB\geq\ell
\quad\Longleftrightarrow\quad
(1-\ell)B-q\geq0,
\]
\[
1-\frac qB\leq u
\quad\Longleftrightarrow\quad
q-(1-u)B\geq0.
\]
These equivalences hold pointwise throughout the interval, so testing both resulting polynomials everywhere is exactly the requested universal decision problem. Clearing denominators using a positive multiplier preserves signs and degree.
Finding: Correct and complete.
The singleton interval and identically zero polynomial are explicitly handled.
For a nonzero polynomial, the first nonvanishing derivative at \(a\) exists and correctly determines the sign immediately to its right. A negative sign forces failure inside the interval because \(a<b\).
Conditional on a positive initial sign, the stated odd-multiplicity criterion is correct. An interior odd-multiplicity root creates a negative interval after the first such root; even-multiplicity roots preserve the sign. Continuity handles both endpoints, including endpoint roots.
The recursive gcd construction is valid. For a root with multiplicity \(r\), its multiplicity in \(G_j\) is \(\max(r-j,0)\). Once the multiplicity disappears from a preceding gcd, later derivatives cannot reintroduce it.
Consequently:
These statements also justify that all displayed quotients are polynomials.
The application satisfies the stated theorem’s hypotheses: \(h\) is a nonconstant squarefree polynomial with rational coefficients, and its signed remainder sequence terminates at a nonzero constant.
The expression \(V(a^+)-V(b^-)\) counts roots strictly inside the interval, excluding endpoint roots as required. The derivative-based one-sided sign formulas are correct, including the factor \((-1)^j\) on the left. They allow exact rational computation of every required sign.
Finding: Correct and complete.
The product of the mass denominators has bit length at most the total encoding length, up to harmless encoding conventions. Each coefficient of \(B\) is a weighted average of coefficients bounded in absolute value by \(W\), so its absolute value is at most \(W\). The coefficient-size estimate after multiplying by \(D\) follows.
Introducing the encoded bounds \(\ell,u\) and clearing their denominators adds only \(O(L)\) bits, preserving the stated \(O(N)\) coefficient bound.
For fixed \(k\), polynomial division, gcd computation, differentiation, Sturm construction, and endpoint evaluation require only a number of rational operations bounded in terms of \(k\). Endpoint numerators and denominators are included in \(L\). A bounded number of rational operations therefore produces intermediate bit lengths \(O_k(N)\).
Construction requires \(O_k(\tau)\) arithmetic operations. The claimed conservative bound
\[
O_k\!\left(\tau\bigl(L+\log_2(W+1)+1\bigr)^3\right)
\]
is sufficient. Unary coefficient encoding implies the stated simplification to \(O_k(\tau L^3)\). The dependence on \(m\) is appropriately restricted to the assigned case \(m=1\).
The optional polynomial-validity checks are also correct. Positive endpoint values and absence of interior roots characterize strict positivity of \(q\) on a nondegenerate closed interval; for a singleton interval, direct evaluation suffices.
Finding: Correct and complete.
No corrective feedback is necessary. The argument establishes the claimed classification and running time under the task’s stated promises.
⟨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.