Answer: The problem is in \(\mathrm P\). Decision and construction of a rational realizing vector take \(O(m^2(\tau+\log(m+1))L^3)\) bit operations. Whenever feasible, a vector with at most one coordinate in \((0,1)\) exists and can be computed.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateWhen the relation graph 𝐺 is a clique, the problem of checking the existence of PSNE in BNPG game with egalitarianism can be solved in 𝑂(|𝑉|2) time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite behavioural types \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), rational \(a\in(0,1)\), costs \(c_t\), and rational piecewise-linear nondecreasing benefit functions \(g_t:[0,1]\to\mathbb{Q}_{\ge 0}\), let \(T_+=\{t:\mu_t>0\}\), \(F_t(q)=g_t(q)+a\min_{s\in T_+}g_s(q)\), and \(q=\sum_t\mu_tz_t\). Decide whether there exists \(z\in[0,1]^T\), realizable by a measurable pure assignment, such that \(z_t=0\Rightarrow D^+F_t(q)\le c_t\), \(z_t=1\Rightarrow D^-F_t(q)\ge c_t\), and \(0<z_t<1\Rightarrow D^-F_t(q)\ge c_t\ge D^+F_t(q)\), where \(D^-\) and \(D^+\) are one-sided derivatives; output \(z\) if it exists.
A society is given by its support: a nonempty list \(T\) of \(\tau\) behavioural types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not possible types.
Input also includes binary rational \(a\in(0,1)\), costs \(c_t\ge0\), and continuous nondecreasing piecewise-linear functions \(g_t:[0,1]\to\mathbb R_{\ge0}\), explicitly encoded by rational breakpoints and values. Let \(m\) be the total number of encoded linear pieces and \(L\) the total input bit length; state running times in \(m,\tau,L\).
Realize the society as disjoint atomless intervals \(I_t\) of lengths \(\mu_t\). A measurable pure assignment \(x:\bigsqcup_t I_t\to\{0,1\}\) realizes \(z\in[0,1]^T\) when \(\int_{I_t}x=\mu_tz_t\).
Define \(q=\sum_t\mu_tz_t\) and \(F_t(q)=g_t(q)+a\min_{s\in T}g_s(q)\); the minimum includes every supported type, irrespective of its assigned action.
Call \(z\) feasible when it is realizable and, for every \(t\), \(z_t=0\Rightarrow D^+F_t(q)\le c_t\), \(z_t=1\Rightarrow D^-F_t(q)\ge c_t\), and \(0<z_t<1\Rightarrow D^-F_t(q)\ge c_t\ge D^+F_t(q)\).
Here \(D^-\) and \(D^+\) are left and right derivatives; at \(q=0\) only the right condition applies, and at \(q=1\) only the left condition applies. Equalities are permitted.
Is deciding whether a feasible assignment exists in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? In the polynomial-time case, can a realizing vector \(z\) also be computed in polynomial time?
Discrete egalitarian binary networked public goods games admit an \(O(n^2)\) equilibrium-existence algorithm on clique relation graphs; on general relation graphs existence is NP-complete, even when the prosocial graph equals the relation graph. [Li et al. (2023)](https://www.ifaamas.org/Proceedings/aamas2023/pdfs/p609.pdf)
No result settling this exact continuous derivative-feasibility problem was located in the literature search.
The decision problem is in \(\mathrm P\). Whenever a feasible assignment exists, a rational realizing vector \(z\) can also be computed in polynomial time. Moreover, such a vector can be chosen with at most one coordinate strictly between \(0\) and \(1\).
A conservative bound for both decision and construction is
\(\displaystyle O\!\left(m^2\bigl(\tau+\log(m+1)\bigr)L^3\right)\)
bit operations. The proof directly handles the stated derivative conditions, including corners and equalities.
Every vector \(z\in[0,1]^T\) is realizable.
Indeed, write each interval as \(I_t=[d_t,d_t+\mu_t)\), ignoring endpoints of measure zero. Set \(x=1\) on \([d_t,d_t+\mu_tz_t)\) and \(x=0\) on the rest of \(I_t\). This assignment is measurable and satisfies
\(\displaystyle \int_{I_t}x=\mu_tz_t.\)
Thus it suffices to find a vector satisfying the derivative conditions and the aggregate equation \(q=\sum_t\mu_tz_t\).
Fix \(q\in(0,1)\), and write
\(\displaystyle \lambda_t(q)=D^-F_t(q),\qquad \rho_t(q)=D^+F_t(q).\)
Define two statements for each type:
\(\displaystyle A_t(q):\ \lambda_t(q)\ge c_t,\qquad B_t(q):\ \rho_t(q)\le c_t.\)
The admissible values of \(z_t\) are exactly as follows.
| \(A_t(q)\) | \(B_t(q)\) | Admissible values |
|---|---|---|
| true | true | \([0,1]\) |
| true | false | \(\{1\}\) |
| false | true | \(\{0\}\) |
| false | false | \(\varnothing\) |
To verify the table, the value \(z_t=0\) requires precisely \(B_t(q)\), the value \(z_t=1\) requires precisely \(A_t(q)\), and a value strictly between them requires both statements.
If any admissible set is empty, this \(q\) is infeasible. Otherwise, partition the types into \(T_1(q)\), forced to one; \(T_0(q)\), forced to zero; and \(T_f(q)\), allowed any value in \([0,1]\). Put
\(\displaystyle \ell(q)=\sum_{t\in T_1(q)}\mu_t,\qquad u(q)=\ell(q)+\sum_{t\in T_f(q)}\mu_t.\)
Fixed-aggregate criterion. A feasible vector with aggregate \(q\) exists exactly when no admissible set is empty and
\(\displaystyle \ell(q)\le q\le u(q).\)
Necessity follows because the forced-one types contribute \(\ell(q)\), while the free types contribute between zero and their total mass.
For sufficiency, let \(r=q-\ell(q)\). Then
\(\displaystyle 0\le r\le\sum_{t\in T_f(q)}\mu_t.\)
Set the forced coordinates to their required values. Process the free types in any order, assigning
\(\displaystyle y_t=\min\{\mu_t,r\},\qquad z_t=\frac{y_t}{\mu_t},\)
and replacing \(r\) by \(r-y_t\). The total available capacity ensures that the final residual is zero. Hence the resulting aggregate is exactly \(q\), and every coordinate is admissible.
This construction has at most one fractional coordinate: every free type before the possible partially filled type is assigned one, and every type after it is assigned zero.
At the endpoints, positivity of every mass gives simpler tests:
These tests use precisely the specified endpoint conventions.
Write
\(\displaystyle h(q)=\min_{s\in T}g_s(q),\qquad F_t(q)=g_t(q)+ah(q).\)
We construct rational points
\(\displaystyle 0=b_0<b_1<\cdots<b_N=1\)
such that every \(g_t\), and also \(h\), is affine on each open interval \((b_i,b_{i+1})\).
Begin with all encoded breakpoints and the endpoints \(0,1\). Each of the \(m\) encoded pieces has an affine expression on its domain. For every pair of pieces whose affine expressions have different slopes, compute their unique intersection coordinate. Include that coordinate if it belongs to both piece domains. Parallel or identical expressions require no additional point.
There are at most \(\binom m2\) intersection candidates and at most \(m+\tau\) encoded endpoints. Sorting and removing duplicates therefore gives \(O(m^2)\) partition points.
To prove the required property, fix an open partition interval \(J=(b_i,b_{i+1})\). Since every original breakpoint is included, each \(g_t\) has one affine expression on \(J\).
Two such expressions with different slopes cannot cross inside \(J\): their intersection would have been included in the partition. Expressions with equal slopes are either identical or have a constant strict ordering. Consequently, choose a type minimizing \(g_t\) at the midpoint of \(J\). Its affine expression remains minimal throughout \(J\). Thus \(h\) is affine on \(J\).
This reasoning includes all supported types in the minimum, independently of their eventual actions.
Let \(p_{t,i}\) denote the slope of \(g_t\) on \(J\), and let \(v_i\) denote the slope of \(h\) there. The slope of \(F_t\) on \(J\) is
\(\displaystyle d_{t,i}=p_{t,i}+av_i.\)
All these quantities are rational and computable exactly.
For \(q\in(b_i,b_{i+1})\), both one-sided derivatives equal \(d_{t,i}\). Hence the classification is constant throughout this interval:
Let \(\ell_i,u_i\) be the corresponding bounds from Section 2. Some aggregate in this open interval is feasible exactly when
\(\displaystyle [\ell_i,u_i]\cap(b_i,b_{i+1})\ne\varnothing.\)
Because \(\ell_i\le u_i\), this is equivalent to the two strict inequalities
\(\displaystyle u_i>b_i,\qquad \ell_i<b_{i+1}.\)
When they hold, define
\(\displaystyle \alpha=\max\{\ell_i,b_i\},\qquad \beta=\min\{u_i,b_{i+1}\},\qquad q=\frac{\alpha+\beta}{2}.\)
Here \(\alpha\le\beta\), \(\beta>b_i\), and \(\alpha<b_{i+1}\). Therefore the chosen \(q\) lies in both \([\ell_i,u_i]\) and \((b_i,b_{i+1})\), including when \(\alpha=\beta\). Section 2 then constructs the vector.
Every \(g_t\) is continuous, and the minimum of finitely many continuous functions is continuous. Thus every \(F_t\) is continuous.
At an interior partition point \(b_i\), continuity and affinity on the adjacent intervals give
\(\displaystyle D^-F_t(b_i)=d_{t,i-1},\qquad D^+F_t(b_i)=d_{t,i}.\)
Indeed, on either adjacent interval the affine expression extends continuously to \(b_i\), so its difference quotient at that endpoint equals its slope.
Apply the complete four-case table from Section 2 using these two derivatives. Reject this point if any type has an empty admissible set; otherwise accept precisely when
\(\displaystyle \ell(b_i)\le b_i\le u(b_i).\)
If accepted, construct the vector with \(q=b_i\).
At \(0\), use the slopes from the first interval and the right-derivative endpoint test. At \(1\), use the slopes from the last interval and the left-derivative endpoint test.
Every \(q\in[0,1]\) is either a partition point or belongs to one of the open partition intervals. Each test is necessary and sufficient on its respective part of the domain. Therefore the algorithm accepts exactly the instances admitting a feasible assignment.
Constructing the affine expressions takes \(O(m)\) rational arithmetic operations. Enumerating pairwise intersections takes \(O(m^2)\), and sorting the candidates takes \(O(m^2\log(m+1))\) rational comparisons.
Scan the partition intervals from left to right, maintaining each type’s current encoded piece. These pointers advance at most \(m\) times in total. On each interval, evaluating all \(\tau\) current affine expressions at its midpoint identifies the minimum and its slope in \(O(\tau)\) arithmetic operations.
Computing the derivative slopes, testing an interval, and testing an adjacent partition point likewise each take \(O(\tau)\) operations. Only the slope vectors for the two adjacent intervals are needed. The total is consequently
\(\displaystyle O\!\left(m^2\bigl(\tau+\log(m+1)\bigr)\right)\)
exact rational operations and comparisons. Witness construction takes another \(O(\tau)\).
All rational operands can be kept to \(O(L)\) bits:
Using reduced fractions and elementary integer algorithms, \(O(L^3)\) bit operations per rational operation is a conservative bound. Including input reading yields the claimed bound
\(\displaystyle O\!\left(m^2\bigl(\tau+\log(m+1)\bigr)L^3\right).\)
The output vector has \(O(\tau L)\) bits. A measurable realizing assignment is then specified by the initial subinterval of length \(\mu_tz_t\) in each \(I_t\).
The algorithm is needed even for two types. Consider
\(\displaystyle \mu_1=\mu_2=\frac12,\qquad a=\frac12,\qquad c_1=c_2=\frac32,\)
with
\(\displaystyle g_1(q)=2\min\left\{q,\frac12\right\},\qquad g_2(q)=2+2\max\left\{q-\frac12,0\right\}.\)
These functions satisfy all stated hypotheses. Since \(g_1(q)\le1<2\le g_2(q)\), their minimum is always \(g_1\).
For \(q<\frac12\), the slopes of \(F_1,F_2\) are \(3,1\). The derivative conditions force \(z_1=1,z_2=0\), giving aggregate \(\frac12\), a contradiction.
For \(q>\frac12\), the slopes are \(0,2\). They force \(z_1=0,z_2=1\), again giving aggregate \(\frac12\). These arguments also exclude the respective endpoints.
At \(q=\frac12\), type \(2\) has
\(\displaystyle D^-F_2\left(\frac12\right)=1<\frac32<2=D^+F_2\left(\frac12\right).\)
Neither action, nor a fractional coordinate, is admissible for that type. Thus this instance has no feasible assignment, demonstrating why partition points must be checked separately.
⟨structured verdict parsed — rendered above⟩
The argument correctly establishes a polynomial-time decision algorithm and polynomial-time construction of a rational realizing vector, under the natural convention that the costs are encoded as binary rationals. The witness can have at most one fractional coordinate.
There is one minor clarification concerning the cost encoding. No mathematical error, missing substantive lemma, or incorrect computation was found.
The construction in Section 1 is valid. For each type, the indicated initial subinterval has length \(\mu_tz_t\), and its indicator is measurable. Endpoints have measure zero and do not affect the integral.
Consequently, every vector in \([0,1]^T\) is realizable. Reducing the problem to the derivative conditions and aggregate equation loses no constraint.
For an interior aggregate, the four-case table correctly translates the stated implications:
These possibilities exhaust \([0,1]\). In particular, when both statements fail, neither a pure nor a fractional coordinate is possible.
The bounds \(\ell(q)\) and \(u(q)\) correctly give the minimum and maximum aggregate contributions from the admissible coordinates. The necessity of \(\ell(q)\le q\le u(q)\) follows directly.
The greedy construction establishes sufficiency as written: the residual is initially nonnegative, never becomes negative, and must reach zero because the available free mass is at least the initial residual. Division by \(\mu_t\) is valid because every supported mass is positive. The construction also justifies the claim of at most one fractional coordinate.
The endpoint tests are correct. Positivity of the masses forces all coordinates to zero at aggregate zero and all coordinates to one at aggregate one. The proof then applies exactly the derivative condition specified at each endpoint.
The proposed partition contains every original breakpoint and every intersection of distinct-slope piece expressions within their common domains. Thus, inside an open partition interval, each type has a fixed affine expression, and distinct expressions cannot change their ordering.
Choosing a midpoint minimizer therefore identifies an expression attaining the minimum throughout that interval. Identical expressions cause no ambiguity in the minimum’s slope. Parallel distinct expressions retain a strict ordering.
This establishes that \(h\), and hence every \(F_t\), is affine on each open partition interval. The slope formula \(d_{t,i}=p_{t,i}+av_i\) is correct.
The size bound is also valid: there are at most quadratically many pairwise intersections. Every supported function requires at least one encoded piece, so \(\tau\le m\); consequently, the stated \(O(m+\tau)\) endpoint count is compatible with the overall \(O(m^2)\) partition bound.
No theorem about lower-envelope complexity is being assumed without proof.
On an open partition interval, both derivatives equal \(d_{t,i}\). The three stated classifications correctly follow from the fixed-aggregate table, including equality.
The intersection criterion is correct:
\[
[\ell_i,u_i]\cap(b_i,b_{i+1})\ne\varnothing
\]
is equivalent to \(u_i>b_i\) and \(\ell_i<b_{i+1}\), given \(\ell_i\le u_i\).
The proposed midpoint selection is valid even when \(\alpha=\beta\). In that case, the two strict inequalities ensure that the common value lies strictly inside the partition interval. Thus no boundary point is incorrectly accepted as an interior witness.
Continuity of each \(g_t\), and of the finite minimum \(h\), establishes continuity of every \(F_t\). The affine expressions on adjacent intervals consequently give the stated left and right derivatives at each interior partition point.
Applying the full four-case table there correctly handles upward corners, downward corners, ties, and forced coordinates. The aggregate test remains necessary and sufficient.
The endpoint derivative computations use the appropriate first or last interval slope. Finally, the partition points and open intervals exhaust \([0,1]\), so the collection of tests establishes both soundness and completeness.
The rational-operation count is supported by the described implementation:
The bit-size argument is sound under rational cost encoding. Piece coefficients, intersections, midpoint evaluations, and derivative slopes involve only a bounded number of operations on input rationals. Mass sums and residuals have the denominator control stated in the proof; division by an input mass preserves an \(O(L)\) bit bound.
Using reduced fractions and elementary integer arithmetic, the conservative \(O(L^3)\) cost per rational operation is sufficient. The claimed total running time and \(O(\tau L)\) witness size follow.
Minor issue — cost encoding. The task explicitly calls \(a\) binary rational but does not explicitly specify the encoding of \(c_t\). The proof assumes rational costs when it uses exact rational comparisons and bounds operand lengths by \(O(L)\). This is the natural intended finite-input interpretation, but it should be stated.
Minimum clarification: State that the costs \(c_t\) are binary rationals whose encoding lengths are included in \(L\).
The example satisfies the required positivity, normalization, continuity, nonnegativity, and monotonicity conditions.
Its minimum is indeed always \(g_1\). The slopes of \((F_1,F_2)\) are \((3,1)\) below \(1/2\) and \((0,2)\) above \(1/2\). Comparing them with the costs \(3/2\) gives exactly the forced vectors and aggregate contradictions stated.
At the corner, type \(2\) has left derivative \(1\) and right derivative \(2\). Both admissibility statements fail. The endpoint exclusions also agree with the stipulated one-sided conditions.
The example is correct and supports the need to test partition points separately.
⟨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.