Answer: In \(\mathrm P\). Every valid input has a unique core vector, and exact algebraic charges are computable in time polynomial in \(\tau\) and \(L\). The proposed charges fail whenever \(b\leq u\).
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet (N, w, b) be a queueing problem with an endogenous number of machines, and (N, C) be the associated TU-game. (i) If b ≤wµ then y = (min (b + wi, 2wi))i∈N ∈Core(C); (ii) If b ≤w⌈2n+1 4 ⌉then Core(C) = (min (b + wi, 2wi))i∈N.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), waiting rates \(w_t>0\), and machine cost \(b\), let \(x_t\in[0,\mu_t]\) describe a coalition of mass \(\alpha=\sum_t x_t\). Sort its waiting rates in decreasing order as \(w_x(r)\), for \(r\in[0,\alpha]\), and define \(C(0)=0\) and \(C(x)=\min_{0<q\leq\alpha}\{bq+\int_0^\alpha (r/q)w_x(r)\,dr\}\). Decide whether there are type-level charges \(p_t\) with \(\sum_t\mu_t p_t=C(\mu)\) and \(\sum_t x_t p_t\leq C(x)\) for every coalition mass vector \(x\), and output such charges or certify that none exist. The direct analogue of Theorem 1(i) asks, in particular, whether \(p_t=\min(b+w_t,2w_t)\) is in the core when \(b\) is at most the upper weighted median waiting rate.
A society is given by its support: a nonempty list of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Waiting rates \(w_t>0\) and machine cost \(b\geq0\) are binary rationals; \(L\) is the total input bit length.
A coalition is any real vector \(x\) with \(0\leq x_t\leq\mu_t\), of mass \(\alpha=\sum_t x_t\). Its decreasing waiting-rate profile \(w_x\) assigns rate \(w_t\) to an interval of length \(x_t\); equal rates may be ordered arbitrarily.
Set \(C(0)=0\) and, for \(\alpha>0\), \(C(x)=\min_{q\in\mathbb R,\,0<q\leq\alpha}\{bq+\int_0^\alpha (r/q)w_x(r)\,dr\}\). Capacity \(q\) is divisible; there is no separate input machine count \(m\).
The type-level core consists of unrestricted real charges \(p_t\) satisfying \(\sum_t\mu_t p_t=C(\mu)\) and \(\sum_t x_t p_t\leq C(x)\) for every coalition \(x\). Define the upper weighted median by \(u=\max\{v\in\{w_t:t\in T\}:\sum_{t:w_t\geq v}\mu_t\geq1/2\}\).
Is deciding whether this core is nonempty in \(\mathrm P\), with running time polynomial in \(\tau\) and \(L\), or is it \(\mathrm{NP}\)-hard; in the polynomial case, can exact core charges also be computed?
Does \(b\leq u\) guarantee that \(p_t=\min\{b+w_t,2w_t\}\) belongs to this core?
For finite agents ordered by decreasing waiting rates, \(b\leq w_{\lceil n/2\rceil}\) guarantees the core allocation \(y_i=\min\{b+w_i,2w_i\}\), and \(b\leq w_{\lceil(2n+1)/4\rceil}\) guarantees its uniqueness. [Source](https://arxiv.org/pdf/2207.07190v3).
The published version additionally characterizes the finite-agent core whenever the optimal machine count is at least \(\lceil n/2\rceil\). [Source](https://ataatay.github.io/webpage/AT_2024_GEB.pdf). No result settling this precise mass model was located.
The decision problem is in \(\mathrm P\). In fact, every valid input has a unique type-level core vector, and that vector can be computed exactly in polynomial time using rational numbers and, when necessary, one positive square root.
The proposed charges \(\min\{b+w_t,2w_t\}\) fail whenever \(b\leq u\): their total charge strictly exceeds \(C(\mu)\).
Define the symmetric matrix \(M\) by \(M_{st}=\min\{w_s,w_t\}\), and define \(A(z)=\frac12 z^{\mathsf T}Mz\) for every real vector \(z\).
For a nonnegative vector \(x\), let \(F_x(v)=\sum_{t:w_t\geq v}x_t\). Since the waiting profile is decreasing, its superlevel set at height \(v\) is an initial interval of length \(F_x(v)\), up to endpoints. Integrating first over superlevel sets therefore gives
\(\displaystyle \int_0^\alpha r\,w_x(r)\,dr =\int_0^\infty\int_0^{F_x(v)}r\,dr\,dv =\frac12\int_0^\infty F_x(v)^2\,dv =\frac12\sum_{s,t}x_sx_t\min\{w_s,w_t\} =A(x). \)
This calculation also handles equal rates.
Moreover, for every real vector \(z\),
\(\displaystyle z^{\mathsf T}Mz =\int_0^\infty \left(\sum_{t:w_t\geq v}z_t\right)^2\,dv \geq0. \)
Thus \(M\) is positive semidefinite. For nonzero nonnegative \(x\), positivity of all waiting rates implies \(A(x)>0\).
Set
\(\displaystyle a=A(\mu)>0, \qquad h_t=(M\mu)_t=\sum_s\mu_s\min\{w_t,w_s\}. \)
In particular, \(\sum_t\mu_t h_t=2a\).
For a nonzero coalition of mass \(\alpha\),
\(\displaystyle C(x)=\min_{0<q\leq\alpha}\left(bq+\frac{A(x)}q\right).\)
When \(b=0\), this expression decreases with \(q\), so its minimum occurs at \(q=\alpha\). When \(b>0\), its derivative is \(b-A(x)/q^2\). Consequently,
\(\displaystyle C(x)= \begin{cases} b\alpha+A(x)/\alpha,& A(x)\geq b\alpha^2,\\ 2\sqrt{bA(x)},& A(x)<b\alpha^2. \end{cases} \)
Since the grand coalition has mass one, its optimal capacity and cost are
\(\displaystyle q_*= \begin{cases} 1,& b\leq a,\\ \sqrt{a/b},& b>a, \end{cases} \qquad C(\mu)= \begin{cases} b+a,& b\leq a,\\ 2\sqrt{ba},& b>a. \end{cases} \)
The unique core charges will be
\(\displaystyle p_t^*= \begin{cases} h_t+b-a,& b\leq a,\\ h_t\sqrt{b/a},& b>a. \end{cases} \)
Some coordinates can be negative, which the problem explicitly permits.
Define \(d=b-a/q_*^2\). By the definition of \(q_*\), either \(q_*=1\) and \(d=b-a\leq0\), or \(b>a\) and \(d=0\). In both cases,
\(\displaystyle p_t^*=\frac{h_t}{q_*}+d.\)
Let \(x\neq0\) be any coalition, with mass \(\alpha\), and let \(0<q\leq\alpha\). Positive semidefiniteness gives
\(\displaystyle 0\leq A\left(x-\frac q{q_*}\mu\right) =A(x)-\frac q{q_*}h^{\mathsf T}x+\frac{q^2}{q_*^2}a. \)
Dividing by \(q\) and adding \(bq\), we obtain
\(\displaystyle bq+\frac{A(x)}q \geq\frac{h^{\mathsf T}x}{q_*}+dq \geq\frac{h^{\mathsf T}x}{q_*}+d\alpha =(p^*)^{\mathsf T}x. \)
The second inequality uses \(d\leq0\) and \(q\leq\alpha\). Taking the minimum over feasible capacities proves every coalition constraint. The zero coalition satisfies its constraint with equality.
Efficiency follows directly:
Hence \(p^*\) belongs to the core.
Fix a type \(t\), and let \(e_t\) be its coordinate unit vector. For \(0<\varepsilon<\mu_t\), the vector \(x(\varepsilon)=\mu-\varepsilon e_t\) is a coalition. Its mass and quadratic waiting term satisfy
\(\displaystyle \alpha(\varepsilon)=1-\varepsilon, \qquad A(x(\varepsilon)) =a-\varepsilon h_t+\frac12w_t\varepsilon^2. \)
In the capacity-binding branch, substitution into the cost formula gives
\(\displaystyle b(1-\varepsilon)+\frac{A(x(\varepsilon))}{1-\varepsilon} =b+a-\varepsilon(h_t+b-a)+O(\varepsilon^2). \)
In the other branch, which requires \(b>0\),
\(\displaystyle 2\sqrt{bA(x(\varepsilon))} =2\sqrt{ba}-\varepsilon h_t\sqrt{b/a}+O(\varepsilon^2). \)
If \(b<a\) or \(b>a\), continuity ensures that the corresponding branch applies for sufficiently small \(\varepsilon\). At \(b=a\), both expansions have constant term \(2a\) and linear coefficient \(-h_t\), so the same conclusion holds regardless of which branch applies. Thus, in every case,
\(\displaystyle C(\mu-\varepsilon e_t) =C(\mu)-\varepsilon p_t^*+O(\varepsilon^2). \)
Now let \(p\) be any core vector. Efficiency and the constraint for this coalition imply
\(\displaystyle C(\mu)-\varepsilon p_t \leq C(\mu-\varepsilon e_t). \)
Using the expansion, dividing by \(\varepsilon\), and letting \(\varepsilon\) decrease to zero yields \(p_t\geq p_t^*\).
This holds for every type. Since both vectors are efficient,
\(\displaystyle \sum_t\mu_t(p_t-p_t^*)=0.\)
Each summand is nonnegative and each mass is positive. Therefore \(p_t=p_t^*\) for every type, proving uniqueness.
Compute all entries \(M_{st}\), then compute \(h=M\mu\) and \(a=\frac12\mu^{\mathsf T}h\). This requires \(O(\tau^2)\) rational arithmetic operations. Compare the rational numbers \(b\) and \(a\), and output the appropriate formula above.
All intermediate rational numbers have bit lengths polynomial in \(L\) and \(\tau\). For example, common denominators for these sums can be formed from products of input denominators, with multiplicity at most two; their bit lengths are polynomially bounded. Standard exact rational arithmetic therefore gives polynomial running time.
When \(b>a\), an exact output consists of the rational coefficients \(h_t\) and the common radical \(\sqrt{b/a}\), explicitly taken to be positive. This representation has polynomial length and requires no factorization.
Exact charges need not be rational: with one type, \(\mu_1=w_1=b=1\), the unique charge is \(\sqrt2\).
Write \(\widehat p_t=\min\{b+w_t,2w_t\}=w_t+\min\{b,w_t\}\), and let \(S=\sum_t\mu_t\widehat p_t\).
For the grand coalition, define \(F(v)=\sum_{t:w_t\geq v}\mu_t\). Then \(0\leq F(v)\leq1\), and
\(\displaystyle 2a=\int_0^\infty F(v)^2\,dv, \qquad S=2\int_0^bF(v)\,dv+\int_b^\infty F(v)\,dv. \)
Suppose first that \(0<b\leq u\). The definition of \(u\) implies \(F(v)\geq\frac12\) throughout \(0\leq v\leq b\). Capacity \(q=\frac12\) is feasible for the grand coalition, so \(C(\mu)\leq b/2+2a\). Moreover,
\(\displaystyle S-\left(\frac b2+2a\right) = \int_0^b\left(2F(v)-F(v)^2-\frac12\right)\,dv +\int_b^\infty F(v)(1-F(v))\,dv. \)
For \(F(v)\in[\frac12,1]\), the first integrand is at least \(\frac14\); the second integrand is nonnegative. Hence
\(\displaystyle S-C(\mu)\geq\frac b4>0.\)
If \(b=0\), let \(W=\sum_t\mu_t w_t=\int_0^\infty F(v)\,dv>0\). Then \(S=W\), \(C(\mu)=a\), and \(F(v)^2\leq F(v)\) implies \(2a\leq W\). Therefore
\(\displaystyle S-C(\mu)\geq\frac W2>0.\)
Thus the proposed vector is never efficient under \(b\leq u\).
This does not contradict the finite-agent result: the published model uses integer machine counts and discrete completion times, whereas the present task specifies divisible capacity and the integral waiting cost used above. See [the published paper, Section 2](https://ataatay.github.io/webpage/AT_2024_GEB.pdf).
⟨structured verdict parsed — rendered above⟩
The output resolves USER_TASK correctly: every valid input has a unique type-level core vector, exact charges have a polynomial-size algebraic representation computable in polynomial time, and the proposed median-based charges fail for every input satisfying \(b\leq u\). No major or minor mathematical issues were found.
The superlevel-set calculation is valid. For nonnegative \(x\), the decreasing profile has a superlevel set of length \(F_x(v)\), up to endpoints of measure zero. The integrands are nonnegative and bounded with finite support, so exchanging the integrals is justified.
Expanding \(F_x(v)^2\) gives the stated matrix entries \(\min\{w_s,w_t\}\). Equal waiting rates do not affect the calculation.
The integral identity for arbitrary real \(z\) also holds: it involves a finite sum whose expansion can be integrated term by term. It proves positive semidefiniteness without requiring distinct rates or invertibility.
For every nonzero nonnegative \(x\), positivity of the waiting rates indeed implies \(A(x)>0\). The definitions of \(a\) and \(h\), and the identity \(\mu^{\mathsf T}h=2a\), are correct.
Finding: Correct; no missing hypothesis.
For nonzero \(x\), the objective tends to infinity as \(q\) approaches zero because \(A(x)>0\). Thus the stated minimum exists despite the open lower endpoint.
The derivative and branch condition are correct. When \(b>0\), the unconstrained minimizer is feasible precisely when \(A(x)\leq b\alpha^2\). At equality, both displayed cost expressions coincide. When \(b=0\), the capacity-binding branch applies and the minimum occurs at \(q=\alpha\).
Substitution of \(\alpha=1\) gives the stated grand-coalition capacity and cost. All divisions and radicals in the candidate charges are defined because \(a>0\); the radical branch additionally has \(b>a>0\).
Finding: Correct, including \(b=0\) and \(b=a\).
The quadratic expansion has the correct cross term and constants:
\(A(x-(q/q_*)\mu)=A(x)-(q/q_*)h^{\mathsf T}x+(q^2/q_*^2)a\).
Dividing by positive \(q\) and adding \(bq\) gives the stated lower bound. The next inequality has the correct direction: \(d\leq0\) and \(q\leq\alpha\) imply \(dq\geq d\alpha\).
The resulting inequality holds for every feasible capacity, so taking the minimum proves the coalition constraint for every nonzero coalition. The zero coalition is explicitly covered.
Both efficiency calculations are correct. Negative coordinates cause no problem because USER_TASK permits unrestricted real charges.
Finding: The candidate is proved to belong to the core for every valid input.
The removal coalition is feasible for every type because \(\mu_t>0\) and \(0<\varepsilon<\mu_t\). Its mass and quadratic expansion are correct, including the coefficient \(M_{tt}/2=w_t/2\).
Both cost expansions have the stated constant and linear terms. For \(b<a\) or \(b>a\), continuity preserves the corresponding strict branch condition for sufficiently small \(\varepsilon\).
At \(b=a\), both branches have the same constant and linear terms. Each has a bounded quadratic remainder near zero, so possible branch changes do not invalidate the stated expansion.
Efficiency and the removal-coalition constraint give the correct inequality direction. Dividing by positive \(\varepsilon\) and taking the limit yields \(p_t\geq p_t^*\). Positive masses and equality of the weighted totals then force equality in every coordinate.
Finding: Uniqueness is rigorously established. Neither distinct rates nor strict positive definiteness is needed.
The \(O(\tau^2)\) rational-operation count is correct. The sums and products used to form \(h\) and \(a\) have polynomial bit length: products of input denominators provide polynomial-length common denominators, and summing polynomially many terms adds only polynomially many bits.
Exact rational comparison determines the branch. In the radical branch, rational coefficients together with a shared, explicitly positive square root give an exact representation of polynomial length. Computing this representation requires no integer factorization or numerical approximation.
The one-type example is correct: it has \(a=1/2\), so the stated charge is \(\sqrt{2}\). It demonstrates why exact output cannot always consist solely of rational numbers.
Finding: Polynomial-time decision and exact algebraic charge computation are established under the binary input model.
The expression for \(S\) follows correctly from the superlevel integrals for \(w_t\) and \(\min\{b,w_t\}\).
For \(0<b\leq u\), the definition of \(u\) and monotonicity of \(F\) imply \(F(v)\geq1/2\) throughout the relevant interval. Capacity \(1/2\) is feasible for the grand coalition, giving the stated upper bound on its cost.
The integral subtraction is correct. On \(F\in[1/2,1]\), the first integrand is at least \(1/4\); the second is nonnegative. Therefore the strict excess \(S-C(\mu)\geq b/4>0\) follows.
The separate \(b=0\) argument is also correct. Positivity gives \(W>0\), and \(F^2\leq F\) implies the stated strict excess.
Finding: The proposed charges fail efficiency for every eligible input, including \(b=0\).
The cited distinction is accurate. Section 2 specifies an integer machine count, integer starting times, and completion costs based on those discrete times. This supports the explanation that the continuous result does not contradict the finite-agent result. [Published paper, Section 2](https://ataatay.github.io/webpage/AT_2024_GEB.pdf)
None. The write-up establishes all requested conclusions and its additional uniqueness claim.
⟨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.