Answer: Polynomial-time exact optimization is possible: the computed direct rule attains welfare \(\operatorname{EFO}_W(\mu,w,B)\), and therefore satisfies the requested \(\tfrac12\) guarantee.
Theorem 4.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any position environment with common budgets, the welfare obtained by the clinching auction is a 2-approximation to the envy-free optimal welfare. Furthermore, this ratio is tight even for the single-item environment.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a rational finite-support value distribution \(\mu\) on \(K\) values, a rational nonincreasing step supply profile \(w:[0,1]\to[0,1]\) with \(S\) steps, and a common per-advertiser budget \(B\), compute in time polynomial in \(K\), \(S\), and the input bit length a finite description of a direct rule \(a_\mu(z),p_\mu(z)\). Require \(a_\mu\) to be nondecreasing and \(p_\mu(z)=z a_\mu(z)-\int_0^z a_\mu(s)\,ds\), with \(0\le p_\mu(z)\le B\). For truthful value quantile \(v(q)\), set \(x(q)=a_\mu(v(q))\) and require \(\int_0^r x(q)\,dq\le\int_0^r w(q)\,dq\) for every \(r\in[0,1]\), with the truthful outcome individually rational and envy-free. The rule's welfare \(\int_0^1 v(q)x(q)\,dq\) must be at least \(\tfrac12\operatorname{EFO}_W(\mu,w,B)\), where the benchmark maximizes welfare over feasible, envy-free, individually rational outcomes with per-advertiser payments at most \(B\).
A society of total mass \(1\) is given by its support: \(\tau=K\ge1\) distinct nonnegative rational values, each with a positive binary-rational mass; \(\tau\) counts supported types, not possible types. There is one service, so \(m=1\). Let \(L\) be the total input bit length.
The other inputs are a common rational budget \(B\ge0\) and a nonincreasing supply profile \(w:[0,1]\to[0,1]\) with \(S\) steps, rational breakpoints and rational heights. Let \(v(q)\) be the nonincreasing value quantile, with equal values occupying a contiguous interval.
An outcome assigns each supported value \(t\) an allocation probability \(A(t)\in[0,1]\) and payment \(P(t)\in[0,B]\). It is individually rational if \(tA(t)-P(t)\ge0\), and envy-free if \(tA(t)-P(t)\ge tA(u)-P(u)\) for all supported \(t,u\); ties receive identical outcomes.
Feasibility means \(\int_0^r A(v(q))\,dq\le\int_0^r w(q)\,dq\) for every \(r\in[0,1]\). Define \(\operatorname{EFO}_W(\mu,w,B)\) as the maximum of \(\int_0^1 v(q)A(v(q))\,dq\) over feasible, envy-free, individually rational outcomes.
A direct rule consists of a nondecreasing measurable allocation \(a_\mu:[0,\infty)\to[0,1]\) and payments \(p_\mu(z)=za_\mu(z)-\int_0^z a_\mu(s)\,ds\), satisfying \(0\le p_\mu(z)\le B\) for every report \(z\ge0\). The distribution is held fixed when an individual reports; the truthful outcome must satisfy the preceding feasibility, individual rationality and envy-freedom conditions.
Does an algorithm running in time polynomial in \(m,\tau,S,L\) always compute a finite description of such a direct rule with welfare \(\int_0^1 v(q)a_\mu(v(q))\,dq\ge\tfrac12\operatorname{EFO}_W(\mu,w,B)\), or is this approximation guarantee unattainable in polynomial time?
For finite position auctions with a common budget, clinching achieves at least \(\tfrac12\) of envy-free optimal welfare; its ratio is tight even for one item. [Devanur–Ha–Hartline](https://arxiv.org/pdf/1212.5766).
For continuum populations, welfare-optimal mechanisms with linear pricing and uniform transfers are known for a divisible good without unit demand; this differs from the bounded allocations and nonnegative payments above. [Richter](https://www.sciencedirect.com/science/article/abs/pii/S0899825619300193). No result settling the precise approximation question above was located.
Under the stated definitions, the guarantee is attainable: a polynomial-time algorithm computes a direct rule whose welfare equals \(\operatorname{EFO}_W(\mu,w,B)\).
The condition that the distribution remains fixed when an individual reports is essential. The construction below solves the full stated problem for every supported population and supply profile.
Order the supported values increasingly as \(0\le t_1<\cdots<t_K\), and let \(h_i>0\) denote the mass of \(t_i\). Thus \(\sum_{i=1}^K h_i=1\).
Write \(x_i=A(t_i)\). We first prove that an allocation vector admits envy-free, individually rational payments in \([0,B]\) if and only if
\[
\]
<!-- Delimiters below follow the requested \( \) convention. -->
\(\displaystyle 0\le x_1\le\cdots\le x_K\le1,\qquad \sum_{j=1}^{K-1}t_j(x_{j+1}-x_j)\le B.\)
All empty sums are zero.
Necessity. Suppose payments \(P_i\) satisfy the required conditions. For \(i<k\), the two envy-free inequalities imply
\(\displaystyle t_i(x_k-x_i)\le P_k-P_i\le t_k(x_k-x_i).\)
Consequently, \((t_k-t_i)(x_k-x_i)\ge0\). Because the supported values are distinct, \(x_k\ge x_i\).
Applying the lower payment bound to adjacent supported values and summing gives
\(\displaystyle P_K\ge P_1+\sum_{j=1}^{K-1}t_j(x_{j+1}-x_j)\ge\sum_{j=1}^{K-1}t_j(x_{j+1}-x_j).\)
Since \(P_K\le B\), the claimed budget inequality follows.
Sufficiency. Suppose the displayed allocation and budget inequalities hold. Define
\(\displaystyle \Delta_j=x_{j+1}-x_j,\qquad \pi_i=\sum_{j=1}^{i-1}t_j\Delta_j.\)
Every \(\Delta_j\) is nonnegative. Hence \(0\le\pi_i\le\pi_K\le B\).
For \(i<k\), each \(t_j\) appearing in \(\pi_k-\pi_i\) lies between \(t_i\) and \(t_k\). Therefore
\(\displaystyle t_i(x_k-x_i)\le\sum_{j=i}^{k-1}t_j\Delta_j=\pi_k-\pi_i\le t_k(x_k-x_i).\)
These are precisely the two envy-free inequalities for types \(t_i,t_k\).
Moreover,
\(\displaystyle \pi_i\le t_i\sum_{j=1}^{i-1}\Delta_j=t_i(x_i-x_1),\)
so \(t_ix_i-\pi_i\ge t_ix_1\ge0\). Thus individual rationality holds.
This proves the characterization. It also shows that \(\pi_i\) is the smallest possible payment for each supported type: every admissible payment vector satisfies \(P_i\ge\pi_i\).
Define the cumulative supply
\(\displaystyle W(r)=\int_0^r w(q)\,dq\)
and the quantile endpoints
\(\displaystyle q_{K+1}=0,\qquad q_i=\sum_{j=i}^K h_j\quad(1\le i\le K).\)
Apart from endpoints of measure zero, value \(t_i\) occupies \([q_{i+1},q_i]\). Let
\(\displaystyle F_x(r)=\int_0^r A(v(q))\,dq.\)
At the endpoints,
\(\displaystyle F_x(q_i)=\sum_{j=i}^K h_jx_j.\)
We claim that feasibility is equivalent to the following \(K\) inequalities:
\(\displaystyle \sum_{j=i}^K h_jx_j\le W(q_i)\qquad(1\le i\le K).\)
Necessity follows by evaluating feasibility at \(q_i\).
For sufficiency, the nonincreasing supply profile makes \(W\) concave. Explicitly, for \(a<b<c\), monotonicity of \(w\) gives
\(\displaystyle \frac{W(b)-W(a)}{b-a}\ge\frac{W(c)-W(b)}{c-b},\)
which implies the defining chord inequality for concavity.
On each interval \([q_{i+1},q_i]\), \(F_x\) is affine. If \(r=(1-\lambda)q_{i+1}+\lambda q_i\), where \(0\le\lambda\le1\), the endpoint inequalities imply
\(\displaystyle F_x(r)\le(1-\lambda)W(q_{i+1})+\lambda W(q_i)\le W(r).\)
Here the endpoint \(q_{K+1}=0\) satisfies \(F_x(0)=W(0)=0\). Thus the finitely many constraints ensure feasibility everywhere.
Combining the preceding characterizations, solve the following rational linear program with variables \(x_1,\ldots,x_K\):
Its feasible allocation vectors are exactly those appearing in feasible, envy-free, individually rational supported outcomes. Its objective is their welfare. Therefore its optimal value equals \(\operatorname{EFO}_W(\mu,w,B)\).
The feasible region is nonempty, because the zero allocation is feasible. It is closed and contained in \([0,1]^K\), so an optimum exists.
Let \(x\) be an optimal solution and retain \(\Delta_j=x_{j+1}-x_j\). Define, for every \(z\ge0\),
\(\displaystyle a_\mu(z)=x_1+\sum_{j=1}^{K-1}\Delta_j\,\mathbf{1}_{\{z>t_j\}}.\)
This is a measurable, nondecreasing allocation taking values in \([0,1]\). The strict threshold convention matters: at \(z=t_j\), the corresponding increment has not yet occurred. In particular,
\(\displaystyle a_\mu(t_i)=x_1+\sum_{j=1}^{i-1}\Delta_j=x_i.\)
Integrating the finite sum gives
\(\displaystyle \int_0^z a_\mu(s)\,ds=x_1z+\sum_{j=1}^{K-1}\Delta_j(z-t_j)_+,\)
where \((y)_+=\max\{y,0\}\). Consequently, the prescribed payment formula yields
\(\displaystyle p_\mu(z)=za_\mu(z)-\int_0^z a_\mu(s)\,ds=\sum_{j=1}^{K-1}t_j\Delta_j\,\mathbf{1}_{\{z>t_j\}}.\)
At a threshold \(z=t_j\), both contributions from that increment are zero, so this identity holds at every report, including thresholds.
Every summand is nonnegative, and hence
\(\displaystyle 0\le p_\mu(z)\le\sum_{j=1}^{K-1}t_j\Delta_j=\pi_K\le B\)
for every \(z\ge0\). At each supported value, \(p_\mu(t_i)=\pi_i\). Thus the truthful supported outcome has exactly the allocation and payments proved feasible, individually rational, and envy-free above.
For completeness, the rule also makes truthful reporting optimal against all reports. For a true value \(t\), let \(u_t(z)=ta_\mu(z)-p_\mu(z)\). If \(z\le t\), then
\(\displaystyle u_t(t)-u_t(z)=\int_z^t\bigl(a_\mu(s)-a_\mu(z)\bigr)\,ds\ge0.\)
If \(z\ge t\), then
\(\displaystyle u_t(t)-u_t(z)=\int_t^z\bigl(a_\mu(z)-a_\mu(s)\bigr)\,ds\ge0.\)
Both inequalities follow from allocation monotonicity. Truthful utility is \(\int_0^t a_\mu(s)\,ds\ge0\).
The resulting welfare is therefore exactly
\(\displaystyle \int_0^1 v(q)a_\mu(v(q))\,dq=\sum_{i=1}^K h_it_ix_i=\operatorname{EFO}_W(\mu,w,B).\)
The linear program has \(K\) variables and a number of constraints linear in \(K\). Each \(W(q_i)\) is computed exactly by summing the rational supply height times the length of its intersection with \([0,q_i]\), over the \(S\) supply steps.
Sorting, these rational sums and products, and constructing the program all take polynomial time in \(K,S,L\). Their encoding lengths are polynomial in the input length: products add operand bit lengths, and a sum of polynomially many rationals has polynomial bit length.
We apply the standard exact rational linear-programming theorem: a nonempty rational linear program with bounded feasible region admits an exact rational optimizer computable in time polynomial in its binary encoding length. Exact recovery from polynomial-time LP algorithms is discussed in [Vishnoi’s linear-programming notes](https://nisheethvishnoi.wordpress.com/wp-content/uploads/2018/05/lecture71.pdf). All hypotheses hold here, including when the feasible region has lower dimension.
The output consists of the rational base allocation \(x_1\), the \(K-1\) rational thresholds \(t_j\), their increments \(\Delta_j\), and the strict threshold convention. This is a finite description of polynomial bit length.
Thus, with \(m=1\), the algorithm runs in time polynomial in \(m,\tau,S,L\) and achieves the benchmark exactly. The cited finite-auction approximation result is not needed: the fixed-distribution reporting condition permits the exact extension proved above.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned question correctly. Under the definitions in USER_TASK, its algorithm computes a direct rule attaining the envy-free optimum exactly, and therefore satisfies the requested approximation guarantee. I found no mathematical gaps or false steps.
The necessity argument is correct. For any supported values \(t_i<t_k\), the two envy-free inequalities give
\[
t_i(x_k-x_i)\le P_k-P_i\le t_k(x_k-x_i).
\]
These inequalities force \(x_k\ge x_i\). Summing the adjacent lower bounds and using \(P_1\ge0\) and \(P_K\le B\) establishes the claimed budget constraint.
The sufficiency argument also holds:
The additional claim that every admissible payment vector satisfies \(P_i\ge\pi_i\) follows from summing the adjacent lower bounds through index \(i-1\). The constructed vector attains these lower bounds simultaneously.
Thus the characterization is both necessary and sufficient, with the correct quantifiers.
The quantile indexing is consistent: \(q_{K+1}=0\), \(q_1=1\), and the interval occupied by \(t_i\) has length \(h_i\). Consequently,
\[
F_x(q_i)=\sum_{j=i}^K h_jx_j.
\]
The concavity argument for \(W\) is valid. A nonincreasing integrable supply profile has nonincreasing interval-average slopes, yielding the stated chord inequality. Step discontinuities and the values assigned at their endpoints do not affect the integrals.
On each supported quantile interval, \(F_x\) is affine. Its endpoint bounds therefore imply that it lies below the chord joining the corresponding values of \(W\), and concavity places that chord below \(W\). The separately identified endpoint condition at zero completes the argument.
Hence the finite constraints are equivalent to feasibility for every quantile prefix. No constraints at additional supply breakpoints are needed.
The linear program combines exactly the allocation, budget, and feasibility conditions established above. Its objective equals supported welfare.
Both directions of the correspondence are justified:
Thus the optimal value equals \(\operatorname{EFO}_W(\mu,w,B)\), rather than merely bounding it.
The zero allocation proves nonemptiness. The region is closed and bounded, and the objective is continuous, so the maximum is attained.
The strict threshold convention is valid under the task’s requirement of a nondecreasing measurable allocation. Right-continuity is not required.
At a supported report \(t_i\), precisely the increments indexed below \(i\) are active. Therefore \(a_\mu(t_i)=x_i\), including at the smallest and largest supported values.
The integration and payment computations are correct. An individual threshold contributes
\[
\Delta_j(z-t_j)_+
\]
to the allocation integral. Its resulting payment contribution is zero when \(z\le t_j\), and \(t_j\Delta_j\) when \(z>t_j\). At equality, both contributions are zero, as the prover states.
It follows that the payment formula holds pointwise at every report and satisfies the global bounds \(0\le p_\mu(z)\le B\). At supported values it reproduces \(\pi_i\).
Both displayed utility-difference identities are algebraically correct. Monotonicity gives their nonnegativity, including when either report lies at a discontinuity. Thus the stronger claim of truthful optimality against all reports is also established.
The truthful population receives exactly the supported outcome already verified. The fixed-distribution condition makes this extension consistent with the task: a report changes the selected outcome without changing the rule’s distribution parameter.
The program has \(K\) variables and linearly many constraints. Although its coefficient matrix can contain quadratically many entries, this remains polynomial in \(K\).
The stated exact computations of quantile endpoints, cumulative supply values, and objective coefficients use polynomially many rational operations. Their intermediate and final encoding lengths are polynomial in the input length; the argument does not confuse arithmetic-operation counts with binary running time.
The invoked rational linear-programming theorem is stated with sufficient hypotheses: rational data, a nonempty bounded feasible region, and running time polynomial in binary encoding length. All are verified here. Lower-dimensional feasible regions are permitted by that general theorem. The linked [Vishnoi notes](https://nisheethvishnoi.wordpress.com/wp-content/uploads/2018/05/lecture71.pdf), page 2, state polynomial-time rational LP optimization and discuss recovery of an exact rational optimizer.
The optimizer consequently has polynomial encoding length. The base allocation, rational thresholds, increments, and threshold convention give a polynomial-size description of the allocation rule; the prescribed payment formula determines its payments.
The written argument also covers the potentially delicate cases:
These cases require no additional assumptions or missing lemmas.
The finite-auction and divisible-good results supplied in the task are not used. The conclusion follows from the task’s own outcome and direct-rule definitions.
Actionable feedback: No mathematical repair or additional clarification is required.
⟨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.