Answer: An expected-polynomial-time algorithm exists that outputs exactly \(S\sim r_k(\bar x)\) for a fixed instance-dependent \(\bar x\in P_k\), with \(\mathbb{E}[W(S)]\ge(1-1/e)\mathrm{OPT}\).
Theorem 3.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere is a $(1-1/e)$-approximate, truthful-in-expectation mechanism for combinatorial public projects with matroid rank sum valuations in the bounded-lottery-value oracle model, running in expected $\poly(n,m)$ time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\), \(k\), a finite type set \(T\), rational masses \(\mu_t\), and bounded-lottery-value oracles for normalized monotone MRS valuations \(v_t\), compute in expected time polynomial in \(m\), \(|T|\), and the input encoding a randomized feasible project set \(S\subseteq[m]\), sampled as \(S\sim r_k(x)\) for some \(x\in P_k=\{x\in[0,1]^m:\sum_jx_j\le k\}\), such that \(\mathbb{E}[\sum_{t\in T}\mu_t v_t(S)]\ge(1-1/e)\max_{|R|\le k}\sum_{t\in T}\mu_t v_t(R)\).
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) projects and an integer budget \(0\le k\le m\). Each type has a normalized monotone valuation \(v_t:2^{[m]}\to\mathbb{Q}_{\ge0}\), with \(v_t(\emptyset)=0\), that is MRS: a finite nonnegative linear combination of matroid rank functions on \([m]\). No decomposition is supplied.
An exact bounded-lottery-value oracle accepts a rational vector \(p\ge0\) with \(\sum_jp_j\le1\), an integer \(0\le b\le m\), and any promised set \(R\subseteq[m]\). It returns the expected valuation of \(R\) united with the projects appearing in \(b\) independent draws, each choosing project \(j\) with probability \(p_j\) and a null symbol with the remaining probability.
Let \(L\) include the explicit input bit length and a supplied bound on the bit length of every \(v_t(A)\). Oracle calls have unit cost; query construction, answer processing, and other bit operations count toward runtime.
Write \(W(A)=\sum_t\mu_tv_t(A)\) and \(P_k=\{x\in[0,1]^m:\sum_jx_j\le k\}\). For \(k\ge1\), \(r_k(x)\) is the set of distinct projects in \(k\) independent draws with project probabilities \(x_j/k\) and null probability \(1-\sum_jx_j/k\); define \(r_0(0)\) to return \(\emptyset\).
Can an algorithm, in expected time polynomial in \(m,\tau,k,L\), output \(S\sim r_k(x)\) for some instance-dependent \(x\in P_k\), with \(\mathbb{E}[W(S)]\ge(1-1/e)\max_{R\subseteq[m],\,|R|\le k}W(R)\), or is this approximation guarantee computationally impossible in that model?
For finite societies, an expected-polynomial-time truthful-in-expectation \((1-1/e)\)-approximation mechanism is known in the bounded-lottery-value oracle model. [Dughmi](https://arxiv.org/pdf/1103.0041)
The full treatment implements the guarantee using modified rounding and a mixture of allocation rules; this does not establish the prescribed single-distribution requirement above. No source located addresses exactly this support-mass formulation. [Dughmi, Roughgarden and Yan](https://theory.stanford.edu/~tim/papers/convex.pdf)
Yes. An expected-polynomial-time algorithm can output exactly the prescribed single distribution and achieve the \(1-1/e\) guarantee.
Two observations make this possible:
The algorithm below uses only oracle queries with \(b=0\), avoiding any possible growth in the encoding length of exact lottery expectations.
Write
\(F(x)=\mathbb{E}_{S\sim r_k(x)}[W(S)]\), and \(\mathrm{OPT}=\max_{|R|\le k}W(R)\).
Because positive linear combinations of MRS valuations are MRS, \(W\) is MRS. In particular, it is normalized, monotone, and submodular.
The cases \(k=0\) and \(k=1\) are immediate. For \(k=0\), output \(\emptyset\). For \(k=1\), query all singleton values and output a maximizing singleton; this is exactly \(r_1(e_j)\).
Henceforth suppose \(k\ge2\). Define
\(U=\max_{j\in[m]}W(\{j\})\).
Submodularity and normalization give, for every set \(A\) and project \(j\),
\(0\le W(A\cup\{j\})-W(A)\le W(\{j\})\le U\).
Consequently, \(W(A)\le\sum_{j\in A}W(\{j\})\le mU\). If \(U=0\), every welfare value is zero, and outputting \(\emptyset\sim r_k(0)\) suffices. Assume below that \(U>0\). Since singleton sets are feasible, \(U\le\mathrm{OPT}\).
The objective \(F\) is the bounded-lottery rounding objective studied in [Dughmi, Section 3](https://arxiv.org/pdf/1103.0041). We give the needed concavity proof explicitly.
Let \(A_b(x)\) be the set of projects appearing in \(b\) independent draws with project probabilities \(x_j/k\) and the corresponding null probability.
Expanding the expectation over ordered draw outcomes makes \(F\) a polynomial in \(x\). Differentiating this finite expansion gives
\(\displaystyle \frac{\partial F}{\partial x_j}(x)=\mathbb{E}\big[W(A_{k-1}(x)\cup\{j\})-W(A_{k-1}(x))\big].\)
Indeed, differentiating one draw replaces its distribution by \(1/k\) times the signed difference between choosing \(j\) and choosing null. Summing over the \(k\) interchangeable positions cancels the factor \(1/k\).
For any set \(A\), define its discrete Hessian by
\(\displaystyle H_W(A)_{ij}=W(A\cup\{i,j\})-W(A\cup\{i\})-W(A\cup\{j\})+W(A).\)
Differentiating twice similarly yields
\(\displaystyle \nabla^2F(x)=\frac{k-1}{k}\,\mathbb{E}\big[H_W(A_{k-2}(x))\big].\)
This includes diagonal entries: choosing the same project twice still adds it only once.
We now verify that each discrete Hessian is negative semidefinite. First consider one matroid rank function \(r\), and fix \(A\). Let
\(N=\{i:r(A\cup\{i\})=r(A)+1\}\).
If \(i\notin N\), diminishing returns implies that row \(i\) of \(H_r(A)\) is zero. On \(N\), define
\(i\sim j\quad\Longleftrightarrow\quad r(A\cup\{i,j\})=r(A)+1.\)
This is an equivalence relation. Reflexivity and symmetry are immediate. For transitivity, if \(i\sim j\) and \(j\sim \ell\), rank submodularity gives
\(2r(A)+2\ge r(A\cup\{i,j,\ell\})+r(A\cup\{j\})\).
Thus \(r(A\cup\{i,j,\ell\})\le r(A)+1\), which implies \(i\sim\ell\).
If \(C\) ranges over the equivalence classes, the rank increments show that
\(\displaystyle H_r(A)=-\sum_C\mathbf{1}_C\mathbf{1}_C^{\mathsf T}.\)
Therefore, for every real vector \(z\),
\(\displaystyle z^{\mathsf T}H_r(A)z=-\sum_C\left(\sum_{i\in C}z_i\right)^2\le0.\)
Nonnegative linear combinations preserve this property, so \(H_W(A)\) is negative semidefinite. The Hessian identity proves that \(F\) is concave on \(P_k\).
Set \(f=F/U\). Given \(x\in P_k\), sample \(A=A_{k-1}(x)\), and form
\(\displaystyle g_j=\frac{W(A\cup\{j\})-W(A)}{U}\qquad(j\in[m]).\)
Then
\(\mathbb{E}[g\mid x]=\nabla f(x)\), \(0\le g_j\le1\), and \(\|g\|_2^2\le m\).
Every value required here is obtained by querying each type with \(p=0\), \(b=0\), and the appropriate promised set.
Let \(R\) attain \(\mathrm{OPT}\), and write \(\mathbf{1}_R\) for its incidence vector. Under \(r_k(\mathbf{1}_R)\), each project in \(R\) appears with probability
\(\alpha_k=1-(1-1/k)^k.\)
For any matroid rank summand, choose a basis \(B\) of \(R\). For every rounded set \(S\), the set \(S\cap B\) is independent, so its rank is at least \(|S\cap B|\). Taking expectations gives
\(\mathbb{E}[r(S)]\ge\alpha_k|B|=\alpha_k r(R).\)
Summing over the MRS summands proves
\(F(\mathbf{1}_R)\ge\alpha_k\mathrm{OPT}.\)
We need a quantitative gap. Since
\(\log(1-1/k)\le-1/k-1/(2k^2)\),
we have
\(\displaystyle \alpha_k-(1-1/e)\ge e^{-1}\bigl(1-e^{-1/(2k)}\bigr).\)
For \(0\le a\le1\),
\(\displaystyle 1-e^{-a}=\int_0^a e^{-u}\,du\ge a-a^2/2\ge a/2.\)
Using \(e<3\) and \(a=1/(2k)\) therefore gives
\(\displaystyle \alpha_k-(1-1/e)\ge\frac{1}{12k}.\)
Thus an additive optimization loss of \(U/(24k)\) is sufficient.
Define the following routine, denoted \(\mathrm{Optimize}\):
\(x_{t+1}=\Pi_{P_k}(x_t+\eta g_t)\),
where \(\Pi_{P_k}\) is Euclidean projection.
\(\displaystyle X=\frac1T\sum_{t=0}^{T-1}x_t\).
Every iterate and \(X\) belong to \(P_k\).
Let \(x^\star\) maximize \(f\) on \(P_k\); such a point exists by continuity and compactness. Euclidean projection gives
\(\displaystyle \|x_{t+1}-x^\star\|_2^2 \le\|x_t-x^\star\|_2^2 +2\eta g_t^{\mathsf T}(x_t-x^\star) +\eta^2\|g_t\|_2^2.\)
Concavity gives
\(f(x^\star)-f(x_t)\le\nabla f(x_t)^{\mathsf T}(x^\star-x_t).\)
Taking conditional expectations, using the unbiased estimator, and summing the preceding inequalities yields
\(\displaystyle \frac1T\sum_{t=0}^{T-1}\mathbb{E}[f(x^\star)-f(x_t)] \le\frac{m}{2\eta T}+\frac{\eta m}{2} =\frac{m}{q} =\frac1{24k}. \)
Here we used \(\|x_0-x^\star\|_2^2\le m\).
Concavity also gives, for every realization of the routine,
\(\displaystyle f(X)\ge\frac1T\sum_{t=0}^{T-1}f(x_t).\)
Consequently,
\(\displaystyle \mathbb{E}[F(X)] \ge\max_{x\in P_k}F(x)-\frac{U}{24k} \ge\alpha_k\mathrm{OPT}-\frac{U}{24k}.\)
Let
\(\bar x=\mathbb{E}[X]\),
where the expectation concerns one invocation of \(\mathrm{Optimize}\) on the fixed instance. This is a deterministic, instance-dependent vector. Because \(P_k\) is convex, \(\bar x\in P_k\).
The output algorithm is:
For every \(i\) and project \(j\),
\(\displaystyle \Pr(J_i=j)=\mathbb{E}[X_j^{(i)}/k]=\bar x_j/k.\)
The complete random experiments for different \(i\) are independent. Therefore the \(J_i\) are independent draws with precisely the probabilities defining \(r_k(\bar x)\). Hence
\(S\sim r_k(\bar x)\) exactly.
The algorithm need not compute or explicitly output \(\bar x\); the task requires outputting \(S\).
Finally, Jensen’s inequality and the optimizer bound give
\(\displaystyle \mathbb{E}[W(S)] =F(\bar x) \ge\mathbb{E}[F(X)] \ge\alpha_k\mathrm{OPT}-\frac{U}{24k}. \)
Since \(U\le\mathrm{OPT}\) and the slack is at least \(1/(12k)\),
\(\displaystyle \mathbb{E}[W(S)] \ge\left(1-\frac1e+\frac1{24k}\right)\mathrm{OPT} \ge(1-1/e)\mathrm{OPT}. \)
Only queries with \(b=0\) are used. Each answer is therefore an individual value \(v_t(A)\), whose bit length is bounded by the supplied \(L\). Forming \(W(A)\), \(U\), and a gradient coordinate uses rational arithmetic of bit length polynomial in \(\tau\) and \(L\).
Projection is also exactly computable with rational arithmetic. For \(y=x_t+\eta g_t\), its coordinates have the form
\(\displaystyle (\Pi_{P_k}(y))_j=\min\{1,\max\{0,y_j-\lambda\}\}.\)
If clipping at \(\lambda=0\) satisfies the budget, take \(\lambda=0\). Otherwise choose \(\lambda\) so the coordinate sum equals \(k\). Sorting the rational breakpoints \(y_j\) and \(y_j-1\) identifies an interval on which this sum is affine. Solving there requires division only by an integer at most \(m\); if the sum is constant on an interval, a rational endpoint suffices.
For completeness, rational sizes cannot grow beyond polynomial length during these iterations. Maintain a common denominator for the current coordinates. Each iteration multiplies it by denominators of \(m\) gradient coordinates, by \(q\), and by at most one integer bounded by \(m\). Thus its bit length grows by a polynomial amount per iteration. Since \(T=(24mk)^2\), every coordinate and the returned average have polynomial bit length.
To sample a rational categorical distribution, express its probabilities over a common denominator \(D\), sample uniformly from the integers below \(D\), and use cumulative intervals. Uniform sampling uses rejection from binary strings of length \(\lceil\log_2D\rceil\), with fewer than two trials in expectation. Its expected bit cost is polynomial.
There are \(k\) optimizer invocations, each with \(T\) iterations and at most \((m+1)\tau\) value queries per iteration. All query construction, arithmetic, projection, and sampling therefore have expected runtime polynomial in \(m,\tau,k,L\). The support masses are handled directly; no expansion into individual citizens is needed.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes the required approximation, the exact single-distribution property, and expected polynomial runtime in the stated oracle model. I found no major or minor gaps requiring repair.
The positive weighted sum \(W=\sum_t\mu_t v_t\) is MRS: each type has a finite nonnegative rank decomposition, and multiplying its coefficients by \(\mu_t\) preserves nonnegativity. The algorithm does not need those decompositions.
Normalization, monotonicity, and submodularity therefore hold for \(W\). These properties justify
\[
0\le W(A\cup\{j\})-W(A)\le W(\{j\})\le U
\]
and \(W(A)\le mU\).
For \(k=0\), the only feasible set is empty, with welfare zero. For \(k=1\), a maximizing singleton is optimal, including when all singleton values vanish. For \(k\ge2\), \(U=0\) implies every welfare value is zero. Otherwise \(U>0\), and \(U\le\mathrm{OPT}\) because singleton sets are feasible. All subsequent divisions by \(U\) are consequently legitimate.
Expanding over ordered outcomes produces a finite polynomial: project probabilities are \(x_j/k\), and null probability is \(1-\sum_jx_j/k\).
Differentiating a draw with respect to \(x_j\) replaces its outcome by the signed difference between project \(j\) and null, scaled by \(1/k\). There are \(k\) interchangeable positions, giving the stated gradient formula.
For the second derivative, there are \(k(k-1)\) ordered pairs of distinct draw positions, each contributing a factor \(1/k^2\). This gives the coefficient \((k-1)/k\). A single draw contributes no second derivative because its probabilities are affine.
When both derivatives concern the same project, adding that project twice still produces one set element. Thus the discrete-Hessian formula correctly includes
\[
H_W(A)_{ii}=W(A)-W(A\cup\{i\}).
\]
For a matroid rank function, a project outside \(N\) has zero marginal rank at \(A\). Diminishing returns and monotonicity force its marginal rank to remain zero after adding any other project, so its entire discrete-Hessian row is zero.
On \(N\), the proposed relation is reflexive and symmetric. The displayed rank-submodularity inequality correctly proves transitivity: the triple has rank at most \(r(A)+1\), while the pair \(\{i,\ell\}\) has rank at least \(r(A)+1\).
Within an equivalence class, the discrete-Hessian entries are \(-1\), including the diagonal. Between different classes, the pair increases rank by two, so the entries are zero. Consequently,
\[
H_r(A)=-\sum_C\mathbf1_C\mathbf1_C^{\mathsf T}
\]
is correct.
Nonnegative sums and expectations preserve negative semidefiniteness. Since \(P_k\) is convex and \(F\) is a polynomial, the Hessian calculation establishes concavity throughout \(P_k\), including its boundary.
Sampling \(A_{k-1}(x)\) and evaluating the stated marginal differences gives exactly the gradient expectation derived above. Dividing by \(U\) yields coordinates in \([0,1]\), hence squared Euclidean norm at most \(m\).
Every required value is available through the allowed query \(p=0\), \(b=0\), with the chosen promised set. The oracle then returns the deterministic value of that set. Welfare evaluation uses the supplied support masses directly.
Every project in an optimal set \(R\) appears under \(r_k(\mathbf1_R)\) with probability
\[
\alpha_k=1-(1-1/k)^k,
\]
even when \(|R|<k\); the remaining probability is assigned to null.
For each matroid summand, a basis \(B\) of \(R\) is independent. Thus \(S\cap B\) is independent, and rank monotonicity gives \(r(S)\ge|S\cap B|\). Taking expectations and summing the nonnegative rank coefficients proves
\[
F(\mathbf1_R)\ge\alpha_k\mathrm{OPT}.
\]
The slack calculation is also valid for every \(k\ge2\). The logarithmic bound gives
\[
\alpha_k-(1-1/e)\ge e^{-1}(1-e^{-1/(2k)}).
\]
With \(a=1/(2k)\), the supplied estimate \(1-e^{-a}\ge a/2\), together with \(e<3\), yields the claimed lower bound \(1/(12k)\). The chosen optimization tolerance \(U/(24k)\) is strictly smaller than the available slack.
Euclidean projection is well-defined because \(P_k\) is nonempty, closed, and convex. Its distance inequality applies to the feasible comparator \(x^\star\).
Conditional unbiasedness and concavity give the displayed expected regret estimate after telescoping. The bounds \(\|x^\star\|_2^2\le m\) and \(\|g_t\|_2^2\le m\) are valid. Substituting \(T=q^2\) and \(\eta=1/q\) gives
\[
\frac{m}{2\eta T}+\frac{\eta m}{2}
=\frac m q
=\frac1{24k}.
\]
The routine averages precisely the iterates appearing in this bound. Concavity applies to that finite average, proving the claimed expected objective guarantee for \(X\). Existence of \(x^\star\) follows from continuity on compact \(P_k\).
The vector \(\bar x=\mathbb E[X]\) is fixed by the instance and belongs to \(P_k\): all coordinate bounds and the budget inequality survive expectation.
Each draw uses a separate, independent optimizer invocation and fresh categorical randomness. Therefore its marginal project probability is \(\bar x_j/k\), and the complete draw experiments are mutually independent. The null probability is likewise \(1-\sum_j\bar x_j/k\).
These facts establish the full joint distribution of the draws, not merely their individual marginals. Taking their distinct non-null projects consequently gives exactly \(S\sim r_k(\bar x)\).
The task requires outputting \(S\), so the algorithm need not compute or encode \(\bar x\). Jensen’s inequality applies because \(F\) is concave and bounded on \(P_k\). Combining it with the optimization estimate and \(U\le\mathrm{OPT}\) gives the claimed guarantee, including the stronger coefficient \(1-1/e+1/(24k)\) for the nondegenerate \(k\ge2\) case.
Using only \(b=0\) ensures that every oracle answer has the supplied value-bit bound. Rational welfare sums, the fixed positive \(U\), and normalized marginal values consequently have polynomial bit length in \(\tau\) and \(L\).
The projection formula correctly handles the coordinate bounds and budget. Its breakpoints are rational; on each interval, the coordinate sum is affine with integer slope of magnitude at most \(m\). Thus the described exact projection requires only rational arithmetic and division by an integer at most \(m\).
The common-denominator accounting is sufficient: each iteration adds only polynomially many denominator bits, and there are polynomially many iterations. Coordinate numerators also remain controlled by feasibility. Forming the returned average preserves polynomial bit length.
Exact categorical sampling from these rational vectors uses rejection sampling with fewer than two trials in expectation. The denominator-one case is deterministic. Sampling the gradient’s draw sets, constructing queries, processing answers, and carrying out projections all fit the stated expected polynomial bound.
Finally, there are \(k\) optimizer runs, each with \((24mk)^2\) iterations and at most \((m+1)\tau\) value queries per iteration, plus polynomial initialization work. No expansion of the support masses into individual citizens is used.
The write-up resolves the assigned algorithmic question. No additional clarification is needed to make its conclusion 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.