Answer: \(\mathrm P\): polynomial-time solvable in \(m,\tau,L\); the minimum subsidy can also be computed exactly.
Proposition 3, item 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any superadditive TU game G: 1. If T ={S∈2N: |S|≤k}, then RCoS(G|T )≤min{k,√n}. Also, for k=2 a stable superimputation with cost 2 can be found using a greedy algorithm. 2. If T is restricted to subsets of a partition P, then RCoS(G|T ) ≤maxC∈P |C|. 3.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), a rational distribution \(\mu\), total mass \(M>2\), and type masses \(a_t=M\mu_t\), let \(V\) be a rational, nonnegative, monotone, superadditive value function on \(\prod_{t\in T}[0,a_t]\), represented by an explicit rational piecewise-affine subdivision. What is the minimum \(\Delta\ge 0\) for which there are per-unit type payoffs \(p_t\) satisfying \(\sum_t p_ta_t=V(a)+\Delta\) and \(\sum_t p_tq_t\ge V(q)\) for every \(q\le a\) with \(\sum_tq_t\le 2\)?
A society is given by its support: the list of \(\tau=|T|\) types with positive binary-rational masses \(a_t\). Here \(a_t=M\mu_t\), where \(M>2\) is rational and \(\mu_t>0\), \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
The input specifies \(V:\prod_t[0,a_t]\to\mathbb R_{\ge0}\) by \(m\) closed rational polytopes covering its domain, each given by rational linear inequalities and an affine formula with rational coefficients; formulas agree on overlaps. Let \(L\) be the total binary input length.
It is promised that \(V(0)=0\), that \(V\) is coordinatewise monotone, and that \(V(q+r)\ge V(q)+V(r)\) whenever \(q,r\ge0\) and \(q+r\le a\).
A coalition is any real mass vector \(0\le q\le a\); it may deviate precisely when \(\sum_tq_t\le2\). A subsidy \(\Delta\ge0\) stabilizes the society if there are per-unit payoffs \(p_t\in\mathbb R_{\ge0}\) with \(\sum_tp_ta_t=V(a)+\Delta\) and \(\sum_tp_tq_t\ge V(q)\) for every allowed coalition. Write \(\Delta^*\) for the minimum such subsidy.
Given a binary-rational threshold \(B\ge0\), is deciding whether \(\Delta^*\le B\) in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For discrete nonnegative monotone superadditive TU games allowing deviations by singletons and pairs, a greedy algorithm constructs stable payoffs totaling at most \(2v(N)\). [Meir, Rosenschein, and Malizia](https://www.ijcai.org/Proceedings/11/Papers/060.pdf)
No result settling this exact continuous formulation was located in the literature search.
The decision problem is in \(\mathrm P\). In fact, \(\Delta^*\) can be computed exactly in time polynomial in \(m,\tau,L\).
The key is that each affine piece contributes a family of linear payoff constraints indexed by a rational polytope. Linear programming duality replaces that entire family by a polynomial-size system of linear constraints.
Identify the support with \(\{1,\ldots,\tau\}\), and write the input pieces as
\[ P_i=\{q:A_iq\le b_i\}, \qquad V(q)=c_i^{\mathsf T}q+d_i\quad(q\in P_i), \qquad i=1,\ldots,m. \]
Define
\[ Q_i=P_i\cap\{q:0\le q\le a,\ \mathbf 1^{\mathsf T}q\le2\}. \]
By appending the displayed inequalities to the description of \(P_i\), obtain a rational description
\[ Q_i=\{q:H_iq\le h_i\}. \]
Test each \(Q_i\) for feasibility by rational linear programming and discard empty ones. Let \(I\) denote the retained indices. Every retained \(Q_i\) is nonempty and compact, because it is closed and contained in the bounded box \([0,a]\). Lower-dimensional pieces are retained.
The covering promise implies
\[ \bigcup_{i\in I}Q_i = \{q:0\le q\le a,\ \mathbf1^{\mathsf T}q\le2\}. \]
Consequently, a nonnegative payoff vector \(p\) satisfies all deviation constraints exactly when, for every \(i\in I\),
\[ (c_i-p)^{\mathsf T}q+d_i\le0 \quad\text{for all }q\in Q_i. \]
Also compute \(v_a=V(a)\): find a piece containing \(a\) by checking its inequalities, and evaluate its affine formula. Coverage guarantees such a piece; agreement on overlaps guarantees a unique value.
Fix \(i\in I\) and a payoff vector \(p\). Consider the linear program
\[ \max\{(c_i-p)^{\mathsf T}q:H_iq\le h_i\}. \]
Here \(q\) is treated as unrestricted in sign when deriving the dual: its nonnegativity constraints are already rows of \(H_iq\le h_i\). The dual is therefore
\[ \min\{h_i^{\mathsf T}y_i: H_i^{\mathsf T}y_i=c_i-p,\ y_i\ge0\}. \]
The primal is feasible and has a finite attained optimum, since \(Q_i\) is nonempty and compact. Strong LP duality therefore guarantees an attained dual optimum with the same value. This theorem applies without a full-dimensionality assumption. See the strong-duality and general-dual formulations in [MIT’s linear programming notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2005/d974aef980258f2a796171e96717d646_n11_lp.pdf).
It follows that the constraints on piece \(i\) are equivalent to the existence of \(y_i\) satisfying
\[ y_i\ge0, \qquad H_i^{\mathsf T}y_i=c_i-p, \qquad h_i^{\mathsf T}y_i+d_i\le0. \]
For completeness, both implications are explicit:
\[ (c_i-p)^{\mathsf T}q+d_i =y_i^{\mathsf T}H_iq+d_i \le y_i^{\mathsf T}h_i+d_i \le0. \]
Crucially, these are linear constraints jointly in \(p\) and \(y_i\).
We first prove that some finite subsidy stabilizes the society.
Let
\[ C=\max_{1\le i\le m,\ 1\le t\le\tau}|c_{i,t}|. \]
We claim that, throughout the box,
\[ V(q)\le C\sum_tq_t. \]
Fix \(q\in[0,a]\) and parameterize the segment from \(0\) to \(q\) by \(\lambda q\), where \(0\le\lambda\le1\). For each piece, the set
\[ J_i=\{\lambda\in[0,1]:\lambda q\in P_i\} \]
is empty or a closed interval, possibly a singleton. These intervals cover \([0,1]\).
Partition \([0,1]\) at all endpoints of the nonempty intervals. Each resulting subinterval of positive length is contained in some \(J_i\): choose an interior point and a covering interval; since no interval endpoint lies inside that subinterval, the covering interval contains its entirety, including the endpoints.
On such a subinterval \([\alpha,\beta]\), agreement with the affine formula gives
\[ V(\beta q)-V(\alpha q) =(\beta-\alpha)c_i^{\mathsf T}q \le(\beta-\alpha)C\sum_tq_t, \]
using \(q_t\ge0\). Summing over the partition and using \(V(0)=0\) proves the claim.
Thus the uniform payoff \(p_t=C\) dominates \(V(q)\) for every coalition in the entire box. Moreover,
\[ a^{\mathsf T}p=CM\ge V(a), \]
so it yields a valid subsidy \(\Delta_0=CM-v_a\ge0\).
The set of nonnegative payoff vectors satisfying all deviation constraints is closed, being an intersection of closed half-spaces. Restrict it further by
\[ v_a\le a^{\mathsf T}p\le CM. \]
This set is nonempty by the uniform-payoff construction. It is compact: every coordinate satisfies \(0\le p_t\le CM/a_t\), and \(a_t>0\). The continuous function \(a^{\mathsf T}p-v_a\) attains a minimum there. Any payoff outside this restriction with total exceeding \(CM\) has subsidy exceeding \(\Delta_0\), so this is also the global minimum \(\Delta^*\).
Consider the following LP, with variables \(p,\Delta\), and one vector \(y_i\) for each \(i\in I\):
\[ \begin{aligned} \text{minimize}\quad &\Delta\\ \text{subject to}\quad &p\ge0,\qquad \Delta\ge0,\\ &a^{\mathsf T}p=v_a+\Delta,\\ &y_i\ge0 &&(i\in I),\\ &H_i^{\mathsf T}y_i=c_i-p &&(i\in I),\\ &h_i^{\mathsf T}y_i+d_i\le0 &&(i\in I). \end{aligned} \]
By Section 2 and the covering property, a pair \((p,\Delta)\) extends to a feasible solution of this LP exactly when \(\Delta\) stabilizes the society using \(p\). Hence its optimal value is precisely \(\Delta^*\).
For the decision problem, simply add the constraint \(\Delta\le B\) and test feasibility. Section 3 ensures that the minimum is attained, so this test answers exactly whether \(\Delta^*\le B\).
Let \(r_i\) be the number of inequalities describing input piece \(P_i\), and let \(R=\sum_i r_i\). Each \(H_i\) has \(r_i+2\tau+1\) rows. Therefore the total number of multiplier variables is at most
\[ R+m(2\tau+1). \]
The final LP has \(\tau+1\) additional variables, at most \(m\tau\) dual equalities, at most \(m\) dual objective inequalities, and the budget and nonnegativity constraints. Its dimensions are polynomial in \(m,\tau,L\).
Its coefficients are input rationals, constants from the appended box and mass inequalities, and the computed rational \(v_a\). Evaluating \(v_a=c_i^{\mathsf T}a+d_i\) uses polynomially many rational arithmetic operations and produces polynomial binary length. Even a dense encoding of the constructed LP has polynomial total length.
Rational LP feasibility and optimization admit algorithms polynomial in binary encoding length; this is the relevant, weakly polynomial guarantee. See [MIT’s notes, Section 5.3](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2005/d974aef980258f2a796171e96717d646_n11_lp.pdf). Thus the preprocessing and final feasibility test run in time polynomial in \(m,\tau,L\). Exact optimization also computes \(\Delta^*\) and optimal rational payoffs in polynomial time.
The proof uses the explicit polyhedral affine representation, agreement on overlaps, \(V(0)=0\), and positive support masses. Monotonicity and superadditivity are unnecessary for this algorithm. The stated promised class is therefore fully covered.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument resolves the stated continuous problem in polynomial time under the supplied representation. I found no mathematical gaps or incorrect steps.
The appended inequalities define precisely the intersection of each input piece with the allowed coalition set. Every retained \(Q_i\) is closed, bounded, and nonempty, so it is compact. Discarding empty intersections loses no constraints, and retaining lower-dimensional intersections correctly preserves boundary coalitions.
Coverage gives the stated union identity. On each retained piece, the inequality
\((c_i-p)^{\mathsf T}q+d_i\le0\) is exactly the original deviation constraint. No restriction to rational coalitions or to vertices is introduced.
Computing \(v_a\) by testing membership of \(a\) in the input pieces is valid. Coverage ensures a containing piece, and overlap agreement makes the evaluated value independent of that choice.
For fixed \(p\), the primal treats \(q\) as unrestricted because its coordinate bounds are already included in \(H_iq\le h_i\). Its dual therefore has nonnegative multipliers and the equality
\(H_i^{\mathsf T}y_i=c_i-p\). Both the multiplier sign and the equality direction are correct.
The invoked strong-duality statement is applicable: a feasible linear program with finite optimal value has an attained dual optimum with the same value. Here feasibility and finiteness follow from the nonempty compact feasible set. Neither full dimensionality nor an interior feasible point is required. The cited notes contain strong duality and the general dual rules in Sections 3 and 3.1. [MIT linear programming notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2005/d974aef980258f2a796171e96717d646_n11_lp.pdf)
The forward implication correctly uses \(y_i\ge0\) to multiply the componentwise inequalities. The converse correctly translates the deviation bound into a primal optimum at most \(-d_i\), then uses an optimal dual multiplier. The resulting constraints are linear jointly in \(p\) and \(y_i\).
The quantifiers are preserved: each fixed feasible payoff vector admits a multiplier for each retained piece. Since there are finitely many pieces, these multipliers can be included simultaneously in the constructed LP.
The constant \(C\) is finite and nonnegative. For every fixed \(q\), each segment preimage \(J_i\) is an empty set or a closed interval, including possible singletons, because the input pieces are closed and convex.
The endpoint partition argument is valid. A covering interval containing an interior point of a partition cell cannot terminate inside that cell; closedness includes the cell endpoints. Thus each positive-length cell lies in a single piece.
The affine increment formula is correct, and its bound follows from \(q_t\ge0\) and \(c_{i,t}\le C\). Summing the increments telescopes, with \(V(0)=0\), giving the claimed bound throughout the box.
Consequently, the uniform payoff dominates every coalition. The identity \(\sum_t a_t=M\) follows from the task’s mass normalization, so its total is \(CM\), and its subsidy is nonnegative.
The feasible payoff set is closed as an intersection of closed half-spaces. The additional total-payoff bounds preserve closedness and give a nonempty set containing the uniform payoff.
Positivity of every support mass justifies the coordinate bounds \(p_t\le CM/a_t\), hence compactness. The objective is continuous and therefore attains its minimum.
Among admissible stabilizing payoffs, those excluded by the upper bound have strictly larger subsidy than the displayed feasible subsidy. Totals below \(v_a\) are already excluded by the requirement \(\Delta\ge0\). Thus the restricted minimum is the global minimum. The argument also covers \(C=0\).
The LP includes payoff nonnegativity, subsidy nonnegativity, the required total-payoff equality, and the exact dual representations of every deviation constraint. Its feasible solutions therefore project onto precisely the stabilizing pairs \((p,\Delta)\).
Adding \(\Delta\le B\) answers the threshold question exactly, including equality at the optimum, because minimum attainment has been proved.
The multiplier count \(R+m(2\tau+1)\) and the stated equality and inequality counts are correct upper bounds. All dimensions are polynomial in the supplied input parameters.
The coefficients are rational, and evaluating \(v_a\) produces polynomial binary length. A dense encoding of the resulting LP remains polynomial in size.
The invoked algorithmic theorem is that rational LP feasibility and exact optimization are polynomial in binary encoding length. Its hypotheses hold for both preprocessing and the final LP; feasibility and a finite attained optimum have been established for optimization. The cited notes discuss polynomial-time solvability and polynomial-size rational solutions. [MIT linear programming notes, Section 5.3](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2005/d974aef980258f2a796171e96717d646_n11_lp.pdf)
The proof addresses the intended real-coalition formulation and the explicit input representation. Its observation that monotonicity and superadditivity are unnecessary is correct. No repair or additional clarification 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.