Answer: Yes: a \((2\beta,2\beta)\)-solution can be computed using polynomially many value queries and bit operations in \((m,\tau,L)\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven any α-approximate solution to the LP optimum, we can construct a (2α, 2α)- Core Stable Solution in polynomial time as long as the projects have subadditive valuations. For general subadditive functions, the only known poly-time constant-factor approxima- tion is the rather intricate randomized LP rounding scheme proposed in [20]. Using this 2- approximation, we get the following corollary.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many projects \(P\), complete agent types \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), and monotone positively homogeneous subadditive valuations \(V_k:\mathbb{R}_{\ge 0}^{\tau}\to\mathbb{R}_{\ge 0}\), choose assignment masses \(x_{k,t}\) satisfying \(\sum_k x_{k,t}=\mu_t\) and reward densities \(p_{k,t}\). For every project \(k\), every feasible deviating mass \(y_{\ell k t}\le x_{\ell,t}\) from projects \(\ell\ne k\) must satisfy \(V_k(x_k+y_k)\le \rho\left(\sum_t p_{k,t}x_{k,t}+\sum_{\ell\ne k,t}p_{\ell,t}y_{\ell k t}\right)\). Compute a welfare-maximizing approximate-core solution, in particular a \((2\beta,2\beta)\)-solution from a supplied \(\beta\)-approximate typed welfare allocation and dual certificate.
A society is given by its support: the list of \(\tau\ge1\) complete types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. There are \(m\ge1\) fixed projects; identical types are interchangeable for every project.
Each project has a finite-valued monotone, positively homogeneous, subadditive valuation \(V_k:\mathbb R_{\ge0}^{\tau}\to\mathbb R_{\ge0}\), with \(V_k(0)=0\). Access is through exact value oracles on rational vectors, returning rational values of bit length polynomial in \(L+b\) for queries of bit length \(b\); no demand oracle is supplied.
An allocation has \(x_{k,t}\ge0\) and \(\sum_kx_{k,t}=\mu_t\). Write \(W(x)=\sum_kV_k(x_k)\) and \(\mathrm{OPT}=\max_xW(x)\) over these allocations.
Reward densities \(p_{k,t}\ge0\) are constant within each project–type cell. Full budget balance requires \(\sum_{k,t}p_{k,t}x_{k,t}=W(x)\).
For every project \(k\), deviations retain all its incumbents and may take arbitrary real masses \(0\le y_{\ell kt}\le x_{\ell,t}\) from each \(\ell\ne k\); put \(y_{k,t}=\sum_{\ell\ne k}y_{\ell kt}\). Stability with factor \(\rho\ge1\) requires \(V_k(x_k+y_k)\le\rho(\sum_tp_{k,t}x_{k,t}+\sum_{\ell\ne k,t}p_{\ell,t}y_{\ell kt})\), including zero deviations and empty destination projects.
A \((\rho,c)\)-solution is fully budget-balanced, satisfies this stability condition, and has \(W(x)\ge\mathrm{OPT}/c\).
Define the configuration-dual bound \(D=\min\{a\cdot\mu+\sum_kz_k:a\ge0,\ z\ge0,\ a\cdot q+z_k\ge V_k(q)\text{ for every }k\text{ and every }0\le q\le\mu\}\).
Input additionally includes a rational \(\beta\ge1\), a rational allocation \(A\) satisfying \(W(A)\ge D/\beta\), and rational optimal dual variables attaining \(D\), all supplied under promise. Let \(L\) be the total binary input length.
Can a \((2\beta,2\beta)\)-solution be computed from these inputs using polynomially many value queries and bit operations in \(m,\tau,L\)?
For indivisible agents with monotone subadditive project valuations, an allocation within factor \(\beta\) of the configuration-LP optimum and optimal dual variables yield a \((2\beta,2\beta)\)-solution in polynomial time. [Anshelevich–Sekar](https://arxiv.org/pdf/1508.06781)
For regular cooperative cost games, subadditivity and degree-one homogeneity imply total balancedness; this concerns cost allocation, not the fixed-project reward problem above. [Anily–Haviv](https://pubsonline.informs.org/doi/abs/10.1287/opre.2014.1283)
No result settling this precise mass-allocation construction was identified in the search.
Yes. A \((2\beta,2\beta)\)-solution can be computed with polynomially many value queries and bit operations in \((m,\tau,L)\).
The key is that the hypotheses imply convexity. Consequently, whole types can be treated as indivisible agents: the supplied allocation can be rounded without losing welfare, the configuration dual is preserved exactly, and stability against whole-type deviations extends to arbitrary real-mass deviations.
For each project \(k\), subadditivity and positive homogeneity give, for \(u,v\in\mathbb R_{\ge0}^{\tau}\) and \(\lambda\in[0,1]\),
\(V_k(\lambda u+(1-\lambda)v)\le V_k(\lambda u)+V_k((1-\lambda)v)=\lambda V_k(u)+(1-\lambda)V_k(v).\)
Thus every \(V_k\) is convex, and so is the welfare function \(W\).
Let \(N=\{1,\ldots,\tau\}\). For \(S\subseteq N\), define its mass vector \(q^S\) by \(q^S_t=\mu_t\) when \(t\in S\), and \(q^S_t=0\) otherwise. Define a finite project valuation by
\(v_k(S)=V_k(q^S).\)
These valuations are normalized and monotone. They are also subadditive: because \(q^{S\cup T}\le q^S+q^T\) coordinatewise,
\(v_k(S\cup T)\le V_k(q^S+q^T)\le V_k(q^S)+V_k(q^T)=v_k(S)+v_k(T).\)
A value query to \(v_k\) requires exactly one query to \(V_k\), at a rational vector whose coordinates are either \(0\) or the supplied masses.
Call an allocation pure if, for every type \(t\), its entire mass \(\mu_t\) is assigned to one project.
Start with \(X=A\), and process the types one at a time. For the current type \(t\), let \(X^{(j)}\) be the allocation obtained by assigning its entire mass to project \(j\), leaving all other types unchanged. Set
\(\lambda_j=X_{j,t}/\mu_t.\)
The allocation constraints and positivity of \(\mu_t\) imply \(\lambda_j\ge0\), \(\sum_j\lambda_j=1\), and
\(X=\sum_{j=1}^{m}\lambda_jX^{(j)}.\)
By convexity,
\(W(X)\le\sum_{j=1}^{m}\lambda_jW(X^{(j)})\le\max_jW(X^{(j)}).\)
Query the candidate welfares and replace \(X\) by a maximizing candidate. Previously processed types remain pure, and welfare does not decrease.
After processing all types, we obtain a partition \(B=(B_1,\ldots,B_m)\) satisfying
\(\sum_kv_k(B_k)\ge W(A)\ge D/\beta.\)
Evaluating all candidates directly uses at most \(m^2\tau\) value queries. Every queried coordinate is an original coordinate of \(A\), a supplied mass, or zero; thus query lengths remain polynomial in \(L\).
The finite instance has configuration dual
\(\widehat D=\min\left\{\sum_td_t+\sum_kz_k:\ d,z\ge0,\ \sum_{t\in S}d_t+z_k\ge v_k(S)\text{ for every }k,S\subseteq N\right\}.\)
We prove that the change of variables \(d_t=a_t\mu_t\) bijectively identifies its feasible solutions with those of the mass configuration dual. Positivity of every \(\mu_t\) makes this change invertible.
If \((a,z)\) is feasible for the mass dual, applying its constraints at \(q^S\) gives
\(\sum_{t\in S}a_t\mu_t+z_k\ge V_k(q^S)=v_k(S).\)
Hence \((d,z)\) is feasible for the finite dual, with the same objective.
Conversely, suppose \((d,z)\) is feasible for the finite dual, and put \(a_t=d_t/\mu_t\). Take any real vector \(0\le q\le\mu\), and write \(\theta_t=q_t/\mu_t\). Define, for each \(S\subseteq N\),
\(\lambda_S=\prod_{t\in S}\theta_t\prod_{t\notin S}(1-\theta_t).\)
These weights are nonnegative, sum to one, and satisfy \(\sum_{S\ni t}\lambda_S=\theta_t\). Consequently,
\(q=\sum_{S\subseteq N}\lambda_Sq^S.\)
Convexity and finite-dual feasibility imply
\(V_k(q)\le\sum_S\lambda_SV_k(q^S)\le\sum_S\lambda_S\left(\sum_{t\in S}d_t+z_k\right)=\sum_td_t\theta_t+z_k=a\cdot q+z_k.\)
Thus \((a,z)\) is feasible for the mass dual. This argument covers irrational \(q\) as well; it requires no oracle calls.
It follows that \(\widehat D=D\), and the supplied optimal dual variables yield optimal finite-dual variables \(d_t=a_t\mu_t\).
For completeness, this finite dual is the dual of the usual configuration LP, with capacity one for each agent and each project. Its primal is feasible and bounded, so finite-dimensional LP strong duality identifies its optimum with \(D\).
Also, directly from mass-dual feasibility, every allocation \(x\) satisfies
\(W(x)\le\sum_k(a\cdot x_k+z_k)=a\cdot\mu+\sum_kz_k=D.\)
Therefore \(\mathrm{OPT}\le D\).
We use the following form of the construction underlying [Anshelevich–Sekar, Theorem 2](https://arxiv.org/pdf/1508.06781): given normalized monotone subadditive finite project valuations, a partition \(B\), and optimal configuration-dual variables of value \(D\), it computes a partition \(S=(S_1,\ldots,S_m)\) and nonnegative payments \(h_t\) satisfying
\(v_k(S_k\cup T)\le\sum_{t\in S_k\cup T}h_t\quad\text{for every }k,T\subseteq N,\)
\(\sum_th_t\le D,\)
and
\(\sum_kv_k(S_k)\ge\frac12\sum_kv_k(B_k).\)
Its construction uses polynomially many value queries and requires no demand oracle when the partition and optimal dual are supplied.
Every hypothesis has been verified above. Write
\(H=\sum_th_t,\qquad w=\sum_kv_k(S_k).\)
Then
\(w\ge W(A)/2\ge D/(2\beta).\)
Taking zero deviations in the finite stability inequalities and summing over projects gives \(w\le H\). Hence, when \(D>0\),
\(0<w\le H\le D\le2\beta w.\)
Return to the mass model using the pure allocation \(x_k=q^{S_k}\).
Fix a destination project \(k\) and any allowed real deviation. A type belonging to \(S_k\) has no mass outside that project, so its incoming mass is zero. Every type \(t\notin S_k\) has a unique donor project and may contribute any amount \(y_{k,t}\in[0,\mu_t]\).
Put \(\theta_t=y_{k,t}/\mu_t\) for \(t\notin S_k\). Let \(T\subseteq N\setminus S_k\) be a random subset including each such type independently with probability \(\theta_t\). This is a finite probability distribution, used only in the proof. It satisfies
\(x_k+y_k=\mathbb E[q^{S_k\cup T}].\)
Convexity and the finite stability inequalities give
\(V_k(x_k+y_k)\le\mathbb E[v_k(S_k\cup T)]\le\sum_{t\in S_k}h_t+\sum_{t\notin S_k}\theta_th_t.\)
Therefore the unscaled density \(h_t/\mu_t\) on each occupied cell stabilizes every allowed real deviation.
Now define the output reward densities by
\(p_{k,t}=(w/H)(h_t/\mu_t)\quad\text{when }t\in S_k,\)
and set \(p_{k,t}=0\) on unoccupied cells. Their total payment is exactly
\(\sum_{k,t}p_{k,t}x_{k,t}=(w/H)\sum_th_t=w=W(x).\)
For the chosen deviation, let its total incumbent and incoming payment be \(C\). The preceding unscaled bound yields
\(V_k(x_k+y_k)\le(H/w)C\le2\beta C.\)
This proves the required stability, including zero deviations and empty destination projects. Furthermore,
\(W(x)=w\ge D/(2\beta)\ge\mathrm{OPT}/(2\beta).\)
Thus the output is a \((2\beta,2\beta)\)-solution.
If \(D=0\), nonnegativity and \(\mu_t>0\) force the supplied optimal variables to satisfy \(a=z=0\). Dual feasibility then gives \(V_k(q)=0\) throughout \(0\le q\le\mu\). Any pure allocation with zero rewards is a valid solution.
All finite-instance oracle queries have polynomial encoding length, so their answers have polynomial bit length by the stated oracle promise.
The finite construction uses comparisons, sums, differences, and divisions by integer set cardinalities, together with two greedy matching routines. In each routine, an agent’s payment strictly increases whenever it moves and is replaced by one of its \(m\) singleton values; hence each agent moves at most \(m\) times. These operations preserve polynomial rational bit length. The final computations of \(w/H\) and \(h_t/\mu_t\) also have polynomial bit complexity.
The algorithm operates on exactly \(\tau\) finite agents. It never expands rational masses into individual units, and it never enumerates the subsets used in the convex-combination proofs.
⟨structured verdict parsed — rendered above⟩
The argument resolves the assigned task. The reductions, stability transfer, approximation constants, and complexity claims are valid. I found no major or minor mathematical issues.
The convexity inequality follows directly from subadditivity and positive homogeneity. Its endpoints are valid because \(V_k(0)=0\). Summing these inequalities establishes convexity of \(W\) on the allocation domain.
The induced valuations \(v_k(S)=V_k(q^S)\) are normalized and monotone. The subadditivity calculation correctly handles overlapping sets: although \(q^S+q^T\) can exceed \(\mu\), each \(V_k\) is defined on the entire nonnegative orthant, so that query-free inequality is legitimate.
Each finite value query translates to one permitted rational-vector query.
Positivity of \(\mu_t\) justifies every division defining \(\lambda_j\). The candidate allocations are feasible, and the asserted convex-combination identity holds in every coordinate, including all coordinates belonging to other types.
Convexity guarantees a candidate with welfare at least the current welfare. Processing one type preserves purity of previously processed types, so the procedure terminates with a partition \(B\) satisfying
\[
\sum_k v_k(B_k)\ge W(A)\ge D/\beta.
\]
The bound of \(m^2\tau\) value queries is correct for direct evaluation of all candidates. Query coordinates have the claimed polynomial encoding lengths.
The change of variables \(d_t=a_t\mu_t\) is invertible because all masses are strictly positive, and it preserves nonnegativity and the objective.
The forward feasibility implication simply specializes the mass constraints to box vertices. For the converse, the displayed product weights have the claimed normalization and coordinate marginals. Thus the convex-combination identity and subsequent convexity inequality establish feasibility for every real \(q\) in the box, including irrational vectors and boundary points.
This proves exact equality of the dual optima and optimality of the transformed supplied variables. The finite configuration LP has finitely many variables, is feasible and bounded, and has precisely the displayed dual, so the strong-duality invocation is valid.
The separate inequality \(W(x)\le D\) follows by applying dual feasibility to each allocation row and summing. Every row lies in the required box.
The stated black-box guarantee matches the construction supporting [Anshelevich–Sekar, Theorem 2](https://arxiv.org/pdf/1508.06781). The theorem’s proof preserves at least half the input welfare. Lemma 11 gives total payments equal to the sum of agent dual prices plus project slack over occupied projects, hence at most the dual objective. Its stability argument covers both occupied and empty projects. The paper explicitly permits supplied allocations and optimal dual prices without demand queries.
All required hypotheses hold here: the finite valuations are normalized, monotone and subadditive; \(B\) is a partition; its welfare is at least \(D/\beta\); and the transformed dual variables are optimal.
Consequently, the prover may use the asserted partition \(S\) and nonnegative payments \(h_t\). Zero-deviation stability yields \(w\le H\), while the welfare and payment guarantees yield
\[
w\ge D/(2\beta),\qquad H\le D.
\]
When \(D>0\), both denominators used subsequently are therefore strictly positive.
Purity ensures that each outside type has exactly one donor project, and each incumbent type has no incoming mass. Hence the parameters \(\theta_t\) describe every allowed deviation.
The finite random subset has the stated expected mass vector. Applying convexity to this finite distribution is valid for real probabilities; neither sampling nor oracle access at irrational vectors is required.
Taking expectations of the finite stability inequalities counts each incumbent payment once and each outside payment with coefficient \(\theta_t\). This exactly matches the unscaled incumbent and incoming mass payments.
Scaling by \(w/H\) gives full budget balance. The stability factor satisfies
\[
H/w\le D/w\le 2\beta.
\]
Empty destinations and zero deviations are included in the same calculation. The welfare guarantee follows from \(\mathrm{OPT}\le D\), with the inequality direction correctly used.
For \(D=0\), nonnegative dual variables and strictly positive masses force \(a=z=0\). Dual feasibility then makes every valuation zero on the box. The proposed zero-payment allocation satisfies all requirements.
The cases \(m=1\) and \(\tau=1\) cause no failure in rounding, dual conversion, or stability transfer.
The construction’s greedy routines have at most \(m\) moves per agent: each move strictly increases the payment to one of that agent’s finitely many singleton values. The remaining arithmetic consists of polynomially many sums, differences, and divisions by positive set cardinalities. These operations have polynomial rational bit growth. The final divisions by \(H\) and \(\mu_t\) also have polynomial bit complexity.
The exponential subset distributions occur only in correctness arguments. They are never enumerated by the algorithm.
No additional clarification is needed to make the argument verifiable.
⟨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.