Answer: The mass Weak Sequential Core is necessarily nonempty, and exact search is polynomial-time solvable in \(m,\tau,L\), with running time \(O(m\tau\,\operatorname{poly}(L))\). A rational schedule suffices.
Theorem 5.3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet the TUU-game Γ be such that Γs is convex for all s ∈S. Then WSC(Γ) ̸= ∅.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\), finitely many states, rational piecewise-linear worth functions \(V_s(q)\) for coalition masses \(q\in[0,\mu]\), and type-specific increasing state-separable utilities, find a state-contingent per-capita payoff schedule in the mass analogue of the Weak Sequential Core. Define that analogue by the paper's characterization: each state's allocation is in the full-population core, and no positive-mass coalition \(q\) can improve every participating type's utility using allocations in the cores of its restricted games in every state. Require each \(V_s\) to have increasing differences, meaning \(V_s(q+\delta)-V_s(q)\le V_s(r+\delta)-V_s(r)\) whenever \(q\le r\) and \(r+\delta\le\mu\).
A society is given by its support: the list of \(\tau\ge1\) types with positive masses \(\mu_t\), each a binary rational; \(\tau\) is the support size, not the number of possible types. Write \(\mu=(\mu_t)_t\); total mass need not equal one. There are \(m\ge1\) states.
For each state, the input gives a continuous rational piecewise-linear worth function \(V_s:[0,\mu]\to\mathbb R\), with \(V_s(0)=0\), by an explicit rational polyhedral subdivision and affine formulas. Assume \(V_s(q+\delta)-V_s(q)\le V_s(r+\delta)-V_s(r)\) whenever \(0\le q\le r\), \(\delta\ge0\), and \(r+\delta\le\mu\), with vector inequalities interpreted coordinatewise.
Type \(t\) has utility \(u_t(z)=\sum_{s=1}^m u_{ts}(z_s)\), where each \(u_{ts}:\mathbb R\to\mathbb R\) is continuous, strictly increasing, and rational piecewise-linear, given by breakpoints and affine formulas. Worths and payoffs may be negative; state weights are absorbed into these utilities.
A coalition is any real mass vector \(0\ne q\in[0,\mu]\). Its state-\(s\) restricted core is \(C_s(q)=\{y\in\mathbb R^\tau:\sum_t q_ty_t=V_s(q),\ \sum_t r_ty_t\ge V_s(r)\text{ for every }0\le r\le q\}\); coordinates with \(q_t=0\) are irrelevant. Payoffs are per capita and constant within each participating type.
The mass Weak Sequential Core consists of schedules \(x=(x_{st})\) with \(x_s\in C_s(\mu)\) in every state, for which there is no coalition \(q\) and schedule \(y\) satisfying \(y_s\in C_s(q)\) in every state and \(u_t((y_{st})_s)>u_t((x_{st})_s)\) for every \(t\) with \(q_t>0\). Coalitions include the full society.
Exact search means finding such a schedule, represented by real algebraic coordinates, or reporting that none exists. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is the mass Weak Sequential Core necessarily nonempty under these assumptions? Is its exact search problem polynomial-time solvable in \(m,\tau,L\), or NP-hard?
For finite-player TU games with uncertainty, convexity of every state game guarantees a nonempty Weak Sequential Core for continuous increasing state-separable utilities. [Habis and Herings](https://cris.maastrichtuniversity.nl/ws/files/64776031/Herings_2011_transferable_utility_games_with_uncertainty.pdf)
No result settling this exact mass problem was identified in the literature search.
The mass Weak Sequential Core is necessarily nonempty, and exact search is polynomial-time solvable. In fact, a suitable schedule has rational coordinates and can be computed using only \(m\tau\) worth-function evaluations.
The construction adapts the common-order marginal allocation in Theorem 5.3 of [Habis and Herings](https://cris.maastrichtuniversity.nl/ws/files/64776031/Herings_2011_transferable_utility_games_with_uncertainty.pdf). The additional argument needed for real mass coalitions is an average-marginal bound, proved below.
Fix a state and write its worth function as \(V\). Let \(e_t\) be the unit vector for type \(t\).
Lemma. Suppose \(0\le a\le b\), \(0<h\le H\), and \(b+He_t\le\mu\). Then
\( \displaystyle \frac{V(a+he_t)-V(a)}{h} \le \frac{V(b+He_t)-V(b)}{H}. \)
Proof. First, the assumed increasing-marginal-worth condition, applied with increment \(he_t\), gives
\( V(a+he_t)-V(a)\le V(b+he_t)-V(b). \)
It remains to compare average increments of different lengths at the same base \(b\).
Define \(f(z)=V(b+ze_t)\) for \(0\le z\le H\). For any \(0\le\alpha<\gamma\le H\), put \(d=(\gamma-\alpha)/2\). Applying the assumption at the ordered base vectors \(b+\alpha e_t\) and \(b+(\alpha+d)e_t\), with increment \(de_t\), yields
\( f(\alpha+d)-f(\alpha)\le f(\gamma)-f(\alpha+d). \)
Consequently,
\( \displaystyle f\!\left(\frac{\alpha+\gamma}{2}\right) \le \frac{f(\alpha)+f(\gamma)}2. \)
Thus \(f\) is midpoint convex. Iterating this inequality proves the convexity inequality for dyadic interpolation parameters; continuity of \(f\) extends it to every interpolation parameter. In particular,
\( \displaystyle f(h)\le \left(1-\frac hH\right)f(0)+\frac hH f(H). \)
Rearranging gives
\( \displaystyle \frac{V(b+he_t)-V(b)}h \le \frac{V(b+He_t)-V(b)}H. \)
Combining the two inequalities proves the lemma. No sign restriction on the worths or increments was used.
Fix any ordering of the support types, and label them \(1,\ldots,\tau\) in that order. Define the prefix mass vectors
\( P_0=0,\qquad P_i=\sum_{j=1}^{i}\mu_j e_j \quad (1\le i\le\tau). \)
Use this same order in every state. Define the per-capita schedule by
\( \displaystyle x_{si}=\frac{V_s(P_i)-V_s(P_{i-1})}{\mu_i} \quad (1\le s\le m,\ 1\le i\le\tau). \)
The divisions are valid because every listed type has positive mass.
Proposition. For every state \(s\), the vector \(x_s\) belongs to \(C_s(\mu)\).
Proof. Efficiency follows by telescoping:
\( \displaystyle \sum_{i=1}^{\tau}\mu_i x_{si} = \sum_{i=1}^{\tau}\bigl(V_s(P_i)-V_s(P_{i-1})\bigr) = V_s(\mu), \)
where \(V_s(0)=0\).
Now fix an arbitrary real vector \(r\) with \(0\le r\le\mu\). Define its prefixes by
\( R_0=0,\qquad R_i=\sum_{j=1}^{i}r_j e_j. \)
For an index \(i\) with \(r_i>0\), apply the lemma with
\( a=R_{i-1},\qquad b=P_{i-1},\qquad h=r_i,\qquad H=\mu_i. \)
Its hypotheses hold: \(R_{i-1}\le P_{i-1}\), \(r_i\le\mu_i\), and \(P_{i-1}+\mu_i e_i=P_i\le\mu\). Therefore,
\( V_s(R_i)-V_s(R_{i-1}) \le r_i\frac{V_s(P_i)-V_s(P_{i-1})}{\mu_i} = r_i x_{si}. \)
If \(r_i=0\), the same inequality holds because both sides are zero. Summing over all indices gives
\( \displaystyle V_s(r) = \sum_{i=1}^{\tau}\bigl(V_s(R_i)-V_s(R_{i-1})\bigr) \le \sum_{i=1}^{\tau}r_i x_{si}. \)
This proves every inequality required by \(C_s(\mu)\), including those for fractional mass vectors.
Proposition. The constructed schedule belongs to the mass Weak Sequential Core.
Proof. Consider any nonzero coalition \(q\in[0,\mu]\) and any schedule \(y\) with \(y_s\in C_s(q)\) in every state. We show that at least one participating type cannot strictly improve.
Let
\( k=\max\{i:q_i>0\}, \qquad a=q-q_k e_k. \)
Because no type after \(k\) participates, \(a\le P_{k-1}\).
Fix a state \(s\). Coalition efficiency and the restricted-core inequality for the subcoalition \(a\le q\) give, respectively,
\( \displaystyle \sum_i q_i y_{si}=V_s(q), \qquad \sum_i a_i y_{si}\ge V_s(a). \)
Subtracting yields
\( q_k y_{sk}\le V_s(q)-V_s(a). \)
Apply the lemma with base vectors \(a,P_{k-1}\) and lengths \(q_k,\mu_k\). Since \(q=a+q_k e_k\), it follows that
\( \displaystyle y_{sk} \le \frac{V_s(a+q_k e_k)-V_s(a)}{q_k} \le \frac{V_s(P_k)-V_s(P_{k-1})}{\mu_k} = x_{sk}. \)
This inequality holds in every state, for the same participating type \(k\). Since each \(u_{ks}\) is increasing,
\( \displaystyle u_k((y_{sk})_{s=1}^{m}) = \sum_{s=1}^{m}u_{ks}(y_{sk}) \le \sum_{s=1}^{m}u_{ks}(x_{sk}) = u_k((x_{sk})_{s=1}^{m}). \)
Thus type \(k\) does not strictly improve. The coalition cannot block.
The argument applies to every real mass coalition, including the full society. Together with state-core feasibility, it establishes the proposition.
The algorithm is:
Each prefix is rational. A continuous rational piecewise-linear function given by an explicit polyhedral subdivision can be evaluated at a rational point by finding a containing cell and evaluating its affine formula. On a shared boundary, continuity ensures that the incident formulas agree.
For cells described by rational inequalities, scanning the explicit descriptions uses polynomially many exact rational operations. If cells are given by rational vertex descriptions instead, membership can be tested by rational linear programming: the point must be a convex combination of the listed vertices. These membership problems also have size polynomial in \(L\).
The rational values \(V_s(P_i)\), and hence the output coordinates, have bit lengths polynomial in \(L\): each evaluation substitutes input rational masses into an input rational affine formula, and the construction then uses subtraction and division by an input positive rational.
Consequently, the running time is
\( O\!\left(m\tau\,\operatorname{poly}(L)\right) \)
bit operations, with polynomial output length. Rational coordinates are already a permitted special case of real algebraic coordinates.
The algorithm always returns a valid schedule, so on the promised input class the “none exists” outcome is unnecessary. This settles both nonemptiness and polynomial-time exact search.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes nonemptiness and polynomial-time exact search under the stated promises. I found no mathematical errors, missing hypotheses, or substantive gaps.
The lemma’s domain conditions are sufficient. From \(0\le a\le b\), \(0<h\le H\), and \(b+He_t\le\mu\), every point at which \(V\) is evaluated lies in its domain.
The first application of increasing marginal worth is valid: the bases \(a,b\) are ordered, the increment \(he_t\) is nonnegative, and \(b+he_t\le\mu\). Dividing its conclusion by the positive number \(h\) preserves the inequality.
The midpoint-convexity calculation is correct. With \(d=(\gamma-\alpha)/2\), the two bases are ordered and the larger base plus the increment equals \(b+\gamma e_t\le\mu\). Rearranging the resulting inequality gives precisely the stated midpoint inequality.
The passage from midpoint convexity to convexity is adequately justified: the output states the dyadic iteration and invokes the assumed continuity to pass to arbitrary interpolation parameters. Applying this at parameter \(h/H\) and rearranging produces the required comparison of average increments. The endpoint \(h=H\) is included.
No positivity assumption on worths or increments is used. The lemma is proved.
The construction uses only listed support types, whose masses are strictly positive. Every division by \(\mu_i\) is therefore valid.
Efficiency follows from the displayed telescoping sum, using \(P_\tau=\mu\) and \(V_s(0)=0\).
For each arbitrary real \(r\in[0,\mu]\), the proposed lemma application has all its hypotheses:
Multiplication by \(r_i>0\) gives the displayed increment bound with the correct inequality direction. When \(r_i=0\), both sides are zero, so the separately handled case is valid.
Summation telescopes to \(V_s(r)\), establishing the core inequality for every real \(r\le\mu\). This is not restricted to rational coalitions or subdivision vertices. The argument includes \(r=0\) and \(r=\mu\).
Membership in every grand-coalition state core is proved.
For every nonzero coalition \(q\), the index \(k=\max\{i:q_i>0\}\) exists because the support is finite. It satisfies \(q_k>0\).
The vector \(a=q-q_ke_k\) is a permitted subcoalition, and \(a\le P_{k-1}\): all coordinates after \(k\) vanish, coordinate \(k\) has been removed, and earlier coordinates are bounded by their society masses.
Subtracting the restricted-core inequality for \(a\) from coalition efficiency gives
\(q_ky_{sk}\le V_s(q)-V_s(a)\).
The direction is correct. Dividing by \(q_k>0\) is legitimate.
The second lemma application is also valid, with bases \(a,P_{k-1}\) and lengths \(q_k,\mu_k\). It yields \(y_{sk}\le x_{sk}\).
Crucially, the chosen participating type \(k\) depends only on the coalition and the common ordering, so the inequality holds for the same type in every state. Monotonicity of each utility component then gives the stated weak utility inequality. That suffices to negate the requirement that every participating type strictly improve.
Singleton participation causes no exception: then \(a=0\), whose core inequality is included in the definition and reads \(0\ge V_s(0)=0\). The full society is likewise covered.
The construction satisfies the specified mass Weak Sequential Core definition.
There are exactly \(m\tau\) required worth evaluations; the values at \(P_0=0\) are supplied by the promise.
For an explicit subdivision described by rational inequalities, scanning cells and testing containment requires polynomially many rational comparisons. Coverage guarantees a containing cell, and continuity guarantees agreement between formulas at shared boundaries.
For cells represented by listed rational vertices, the stated convex-combination membership test is a rational linear-programming feasibility problem of polynomial encoding size. Since subdivision cells lie in the bounded box, their boundedness introduces no missing ray representation.
The bit-length claim is sound. Prefix coordinates are input masses or zero; affine evaluation uses polynomially many operations on input rationals. The subsequent subtraction and division by an input positive rational preserve polynomial encoding length. A very small positive mass can enlarge the numerical magnitude without making its binary representation superpolynomial.
Thus the stated bound \(O(m\tau\,\operatorname{poly}(L))\) is a valid polynomial bit-complexity bound. Rational output coordinates meet the requested real-algebraic representation requirement. The algorithm need not validate the promised increasing-marginal condition.
The attribution to the common-order marginal construction in [Habis and Herings, Theorem 5.3](https://cris.maastrichtuniversity.nl/ws/files/64776031/Herings_2011_transferable_utility_games_with_uncertainty.pdf) is accurate. The output supplies its own mass-coalition argument rather than assuming that the finite-player theorem applies unchanged.
No repair or additional mathematical clarification is required. Both assigned questions are resolved.
⟨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.