Answer: Yes. An additive bicriteria FPTAS exists for the stated continuum payment model, with rational finite output and exact transfer coverage.
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven ϵ > 0, there exists an algorithm that runs in time polynomial in the instance size and 1 ε and returns an ε-IC and IR solution to Problem (1) with LL constraints hav- ing value at least OPT −ε, where OPT is the optimal value of Problem (1) with LL constraints.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many advertiser types \(T\) with rational masses \(\mu_t\), values \(v_t\), and outside-utility thresholds \(a_t\), a rational slot supply per unit mass \(\kappa\), a nonincreasing piecewise-rational click-rate curve \(\lambda\), and a finite rational lottery \(\nu\) over external bid-mass profiles, compute a finite-description randomized bidding policy \(\Gamma\) and transfers \(q_t\geq 0\). A policy assigns each type's mass across bids in \([0,1]\); GSP ranks combined bid mass and allocates ranks up to \(\kappa\), with symmetric assignment within each type so participation is measured per advertiser. Maximize expected total colluder value minus agency payments, subject to expected per-advertiser utility for each type being at least \(a_t-\varepsilon\), aggregate transfers covering expected payments, and an objective value at least \(\mathrm{OPT}-\varepsilon\). Is there an algorithm polynomial in \(|T|\), the external-lottery and click-curve descriptions, input bit length, and \(1/\varepsilon\)?
A society is given by its support: the list of \(\tau\) advertiser 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. Each type has binary-rational value \(v_t\in[0,1]\) and outside-utility threshold \(a_t\in[0,1]\).
The input includes a finite rational lottery \(\nu\) over external profiles, each listing rational bids in \([0,1]\) and positive rational masses of common total \(E\); rational slot supply \(0<\kappa\leq1+E\); and a nonincreasing curve \(\lambda:[0,\kappa]\to[0,1]\). Its \(m\) pieces have rational breakpoints and densely encoded rational-function formulas with no poles on their intervals. Let \(D\) be the external-lottery description length and \(L\) the total input bit length.
A bidding profile measurably assigns each type's mass to bids in \([0,1]\); a randomized policy \(\Gamma\) selects a joint profile independently of the external draw. Combined mass is ranked by decreasing bid; colluders precede external mass at equal bids, and the agency specifies the order of tied colluder mass. Assignments are symmetric within each type.
For each realization, let \(b(x)\) be the ranked bid function on \([0,1+E)\), and \(A_t\) the ranks occupied by type \(t\). Mass at rank \(x<\kappa\) receives click rate \(\lambda(x)\) and pays \(\lambda(x)b(x+)\); unallocated mass receives and pays zero. Here \(b(x+)\) is the right-hand limit, with zero beyond total mass.
Define per-advertiser expected revenue and auction payment by \(r_t(\Gamma)=\frac{v_t}{\mu_t}\mathbb E\int_{A_t\cap[0,\kappa]}\lambda(x)\,dx\) and \(p_t(\Gamma)=\frac{1}{\mu_t}\mathbb E\int_{A_t\cap[0,\kappa]}\lambda(x)b(x+)\,dx\). Expectations include both lotteries.
Transfers \(q_t\in[0,1]\) are fixed per advertiser and paid to the agency. Exact feasibility means \(r_t(\Gamma)-q_t\geq a_t\) for every type and \(\sum_t\mu_tq_t\geq\sum_t\mu_tp_t(\Gamma)\). Promise that some deterministic profile satisfies \(r_t-p_t\geq a_t\) for every type.
Let \(\mathrm{OPT}\) be the supremum of \(U(\Gamma)=\sum_t\mu_t(r_t(\Gamma)-p_t(\Gamma))\) over exactly feasible measurable policies and transfers. A finitely encoded output policy is a finite rational lottery over profiles listing rational constant-bid mass blocks, including their tie order.
For every rational \(0<\varepsilon<1\), can such a policy and rational transfers be computed in time polynomial in \(m,\tau,D,L,1/\varepsilon\), with \(r_t(\Gamma)-q_t\geq a_t-\varepsilon\) for every type, exact transfer coverage, and \(U(\Gamma)\geq\mathrm{OPT}-\varepsilon\)?
For finite advertisers, an additive bicriteria FPTAS achieves these participation and objective errors with nonnegative transfers and exact agency payment coverage, under the analogous deterministic-feasibility promise ([Romano et al., 2022](https://www.ijcai.org/proceedings/2022/0066.pdf)). No result settling this distribution-over-types version was located.
Yes, for the payment rule stated in the question. There is an algorithm with the required polynomial running time, finite rational output, participation error, exact transfer coverage, and objective guarantee.
The crucial feature of this continuum model is that almost every advertiser pays its own bid. This differs from finite-advertiser GSP, where the payment uses the next advertiser’s bid; see [Romano et al., 2022](https://www.ijcai.org/proceedings/2022/0066.pdf). The proof below uses the specified continuum rule throughout.
Extend the click curve to nonnegative ranks by setting \(\bar\lambda(x)=\lambda(x)\) for \(x<\kappa\), and \(\bar\lambda(x)=0\) for \(x\geq\kappa\). This extension is nonincreasing and takes values in \([0,1]\). Its value at \(\kappa\) does not affect any integral.
Write the external lottery as profiles indexed by \(s\), with rational probabilities \(\pi_s\). For a bid \(b\), let \(C_s(b)\) denote the external mass in profile \(s\) bidding strictly more than \(b\).
Parameterize colluder mass, in its specified ranking order, by \(y\in[0,1)\). A deterministic profile is then represented by:
In external realization \(s\), colluder mass at coordinate \(y\) occupies rank \(y+C_s(\beta(y))\), almost everywhere. External mass with the same bid comes after all colluder mass at that bid, which explains the strict inequality in the definition of \(C_s\).
Define its expected click rate by
\(\displaystyle h_\beta(y)=\sum_s\pi_s\bar\lambda\bigl(y+C_s(\beta(y))\bigr).\)
Since \(\beta\) is nonincreasing, \(C_s(\beta(y))\) is nondecreasing. Consequently, \(h_\beta\) is nonincreasing.
A bounded monotone ranked bid function has only countably many discontinuities. Therefore \(b(x+)=b(x)\) almost everywhere. Thus, writing \(P\) for aggregate auction payment,
\(\displaystyle r_t=\frac{v_t}{\mu_t}\int_{\{y:t(y)=t\}}h_\beta(y)\,dy,\qquad P=\sum_t\mu_tp_t=\int_0^1\beta(y)h_\beta(y)\,dy.\)
These identities also hold after taking expectations over policies.
In particular, \(0\leq r_t,p_t\leq1\), and \(0\leq P\leq1\). The deterministic-feasibility promise implies exact feasibility: choose \(q_t=p_t\) for its promised profile.
Every exactly feasible policy satisfies
\(\displaystyle 0\leq\sum_t\mu_ta_t\leq U\leq1.\)
The lower bound follows by summing participation inequalities and using transfer coverage. The upper bound follows because aggregate revenue is at most \(1\) and payments are nonnegative. Hence \(0\leq\mathrm{OPT}\leq1\).
Let \(\mathcal B\) consist of \(0\) and every bid appearing in any external profile. Its cardinality is polynomial in \(D\).
For \(z\in[0,1]\), define
\(\displaystyle F(z)=\max\{b\in\mathcal B:b\leq z\}.\)
For every external bid \(e\),
\(\displaystyle e>F(z)\quad\Longleftrightarrow\quad e>z.\)
Indeed, if \(e\leq z\), then \(e\in\mathcal B\) implies \(F(z)\geq e\); the other direction follows from \(F(z)\leq z\).
Replace \(\beta\) by \(F\circ\beta\), retaining the original colluder order when newly created ties occur. Every colluder’s rank in every external realization is unchanged. Consequently, all type revenues remain unchanged, while aggregate payment weakly decreases.
Thus, for every weighted objective with nonnegative revenue coefficients and a nonnegative payment penalty, bids can be restricted to \(\mathcal B\) without loss.
The all-zero-bid profile, denoted by \(\Gamma_0\), has \(P(\Gamma_0)=0\) and \(r_t(\Gamma_0)\geq0\).
We construct an oracle for
\(\displaystyle J(\Gamma)=\sum_t\alpha_t r_t(\Gamma)-\beta P(\Gamma),\)
where \(\alpha_t\geq0\), \(\beta\geq0\), \(\sum_t\alpha_t\leq1\), and \(\beta\leq1\).
For fixed bid function, the weighted revenue density of type \(t\) is
\(\displaystyle c_t=\frac{\alpha_tv_t}{\mu_t}.\)
Order types so that \(c_1\geq\cdots\geq c_\tau\), and place each type contiguously in that order.
This maximizes weighted revenue for the fixed bid function. To verify this, let \(M_i=\sum_{t\leq i}\mu_t\). For any measurable set \(A\) of measure \(M_i\), monotonicity of \(h_\beta\) gives
\(\displaystyle \int_Ah_\beta(y)\,dy\leq\int_0^{M_i}h_\beta(y)\,dy.\)
For example, this follows by comparing the equally sized sets \([0,M_i)\setminus A\) and \(A\setminus[0,M_i)\): every point of the former precedes every point of the latter.
Now express weighted revenue as
\(\displaystyle c_\tau\int_0^1h_\beta(y)\,dy+\sum_{i=1}^{\tau-1}(c_i-c_{i+1})\int_{\{t(y)\leq i\}}h_\beta(y)\,dy.\)
All coefficients in the sum are nonnegative, and each integral is maximized by the contiguous ordering. Aggregate payment does not depend on type labels.
Fix a positive integer \(K\). Subdivide each contiguous type interval into \(K\) equal blocks of mass \(\mu_t/K\).
First restrict bids to \(\mathcal B\) as above. On each subdivision interval \(I=(l,r)\), replace the bid function by its essential minimum on \(I\). The resulting bids remain nonincreasing and belong to \(\mathcal B\).
Let \(h\) and \(h'\) denote the click functions before and after this replacement. Pointwise almost everywhere, the replacement lowers bids, so
\(\displaystyle h'(y)\leq h(y),\qquad \beta'(y)h'(y)\leq\beta(y)h(y).\)
Therefore payment cannot increase.
Because the original bid function uses finitely many levels, its essential minimum on \(I\) is its bid level immediately before \(r\). Monotonicity of \(\bar\lambda\) then gives \(h'(y)\geq h(r-)\) for almost every \(y\in I\). Hence
\(\displaystyle \int_I(h-h')\,dy\leq |I|\bigl(h(l+)-h(r-)\bigr).\)
Within a type interval, all block lengths equal \(\mu_t/K\). The sum of their variations is at most \(1\), because \(h\) is nonincreasing and bounded in \([0,1]\). Therefore the revenue loss for each type is at most
\(\displaystyle \frac{v_t}{\mu_t}\frac{\mu_t}{K}=\frac{v_t}{K}\leq\frac1K.\)
After sorting, subdivision therefore loses at most \(1/K\) in the weighted objective.
This bound depends on \(K\), not on \(1/\min_t\mu_t\).
Fix another positive integer \(H\), and write \(h_0=1/H\).
For an interval \([u,u+\ell]\), define the rational lower Riemann sum
\(\displaystyle I^-(u,\ell)=\frac{\ell}{H}\sum_{j=1}^{H}\bar\lambda\left(u+\frac{j\ell}{H}\right).\)
Monotonicity gives
\(\displaystyle 0\leq\int_u^{u+\ell}\bar\lambda(x)\,dx-I^-(u,\ell)\leq\frac{\ell}{H}.\)
The bound follows by subtracting lower sums from upper sums; their difference is
\(\displaystyle \frac{\ell}{H}\bigl(\bar\lambda(u)-\bar\lambda(u+\ell)\bigr)\leq\frac{\ell}{H}.\)
For a constant-bid block starting at colluder coordinate \(y\), of mass \(\ell\) and bid \(b\), use
\(\displaystyle \sum_s\pi_s I^-(y+C_s(b),\ell)\)
as its expected click integral.
Summing these estimates produces rational numbers \(\widehat r_t\) and \(P^-\) satisfying
\(\displaystyle 0\leq r_t-\widehat r_t\leq h_0,\qquad 0\leq P-P^-\leq h_0.\)
The first bound uses the fact that all blocks of type \(t\) have total mass \(\mu_t\). Define the conservative payment estimate
\(\displaystyle \widehat P=P^-+h_0.\)
Then
\(\displaystyle P\leq\widehat P\leq P+h_0.\)
All these quantities are rational. Evaluation of the densely encoded rational functions at rational arguments takes polynomial time and produces polynomial-length rational numbers. Breakpoints can be located directly from their rational list. No symbolic integration is required.
For the sorted type order, there are \(N=\tau K\) blocks. Their starting colluder coordinates are fixed by the ordered masses, independently of their bids.
For each block \(j\) of type \(t\), and each \(b\in\mathcal B\), compute the edge weight
\(\displaystyle \left(\frac{\alpha_tv_t}{\mu_t}-\beta b\right)\sum_s\pi_s I^-(y_j+C_s(b),\mu_t/K).\)
A dynamic program over block index and previous bid maximizes their sum subject to nonincreasing bids. This exactly maximizes \(\sum_t\alpha_t\widehat r_t-\beta\widehat P\) over these profiles: the additional term \(-\beta h_0\) is constant.
For any such profile,
\(\displaystyle 0\leq J-\left(\sum_t\alpha_t\widehat r_t-\beta\widehat P\right)\leq h_0\left(\sum_t\alpha_t+\beta\right)\leq2h_0.\)
Combining bid restriction, sorting, subdivision, and this numerical bound proves the following oracle guarantee:
For every measurable policy \(\Gamma\), the returned rational-block profile \(\sigma\) satisfies
\(\displaystyle \sum_t\alpha_t\widehat r_t(\sigma)-\beta\widehat P(\sigma)\geq J(\Gamma)-\rho,\qquad \rho=\frac1K+\frac2H.\)
For randomized \(\Gamma\), this follows by taking expectations of the deterministic comparison.
Set
\(\displaystyle d=\frac{\varepsilon}{32},\qquad K=\left\lceil\frac{128}{\varepsilon}\right\rceil,\qquad H=\left\lceil\frac{256}{\varepsilon}\right\rceil.\)
Then \(\rho\leq\varepsilon/64=d/2\).
For a rational objective target \(z\in[0,1]\), consider these estimated constraint margins for a profile and transfer vector:
\(\displaystyle f_t=\widehat r_t-q_t-a_t+\frac{\varepsilon}{2}\quad\text{for each type }t,\)
\(\displaystyle f_C=\sum_t\mu_tq_t-\widehat P-\frac{\varepsilon}{16},\)
\(\displaystyle f_O=\sum_t\mu_t\widehat r_t-\widehat P-z.\)
There are \(n=\tau+2\) margins, and all belong to \([-3,3]\).
Let nonnegative weights \(w_t,w_C,w_O\) sum to \(1\). Maximizing their weighted margin uses revenue and payment coefficients
\(\displaystyle \alpha_t=w_t+w_O\mu_t,\qquad \beta=w_C+w_O.\)
These satisfy the oracle’s hypotheses. The coefficient of transfer \(q_t\) is \(w_C\mu_t-w_t\), so maximizing over \(q_t\in[0,1]\) simply chooses \(q_t=1\) when this coefficient is positive and \(q_t=0\) otherwise.
Consequently, the oracle and this transfer choice approximately maximize the weighted constraint margin over all measurable policies and transfers.
Start with unnormalized weights \(A_i^1=1\). At iteration \(k\), normalize them to \(w_i^k\), obtain a profile and transfers as above, and compute their estimated margins \(f_i^k\). Put \(g_i^k=f_i^k/3\), and update
\(\displaystyle A_i^{k+1}=A_i^k(1-\eta g_i^k),\qquad \eta=\frac d{12}.\)
All weights stay positive because \(|g_i^k|\leq1\) and \(\eta<1/2\).
Run
\(\displaystyle T=\left\lceil\frac{12n}{\eta d}\right\rceil\)
iterations.
Using \(\log(1-x)\leq-x\) and \(\log(1-x)\geq-x-x^2\) for \(|x|\leq1/2\), comparison of the total weight with each individual weight gives
\(\displaystyle \frac1T\sum_{k=1}^{T}f_i^k\geq\frac1T\sum_{k=1}^{T}\sum_jw_j^kf_j^k-\frac{3\log n}{\eta T}-3\eta.\)
Here \(3\log n/(\eta T)\leq d/4\) and \(3\eta=d/4\).
Suppose there exists a measurable comparator policy and transfers for which the true versions of all three kinds of margin are nonnegative. At every iteration, their weighted true margin is nonnegative, so the oracle guarantee implies \(\sum_jw_j^kf_j^k\geq-\rho\). Thus every averaged estimated margin is at least \(-d\).
Output the uniform lottery over the \(T\) profiles, with fixed transfers
\(\displaystyle \bar q_t=\frac1T\sum_{k=1}^{T}q_t^k.\)
These transfers are rational and belong to \([0,1]\). They are fixed across policy realizations; averaging the margins is valid because revenue, payment, and transfer constraints are linear in these quantities.
Choose an exactly feasible pair \((\Gamma^*,q^*)\) with
\(\displaystyle U(\Gamma^*)\geq\mathrm{OPT}-\frac{\varepsilon}{16}.\)
Such a pair exists by the definition of supremum and the established nonemptiness.
Let \(\theta=\varepsilon/8\), and define
\(\displaystyle \Gamma'=(1-\theta)\Gamma^*+\theta\Gamma_0,\qquad q_t'=(1-\theta)q_t^*+\frac{\theta}{2}.\)
The transfers remain in \([0,1]\). Since the zero-bid policy has nonnegative revenues and zero payment,
\(\displaystyle r_t(\Gamma')-q_t'\geq(1-\theta)a_t-\frac{\theta}{2}\geq a_t-\frac{3\varepsilon}{16},\)
and
\(\displaystyle \sum_t\mu_tq_t'-P(\Gamma')\geq\frac{\theta}{2}=\frac{\varepsilon}{16}.\)
Also, since \(0\leq U(\Gamma^*)\leq1\) and \(U(\Gamma_0)\geq0\),
\(\displaystyle U(\Gamma')\geq U(\Gamma^*)-\theta\geq\mathrm{OPT}-\frac{3\varepsilon}{16}.\)
Thus the true participation and coverage margins from Section 4 are nonnegative for this comparator. Its objective margin is nonnegative whenever \(z\leq U(\Gamma')\).
Run the procedure for every target
\(\displaystyle z\in\left\{j\frac{\varepsilon}{8}:0\leq j\leq\left\lfloor\frac8\varepsilon\right\rfloor\right\}.\)
At least one target satisfies both \(z\leq U(\Gamma')\) and
\(\displaystyle z\geq\mathrm{OPT}-\frac{3\varepsilon}{8}.\)
Indeed:
For this target, the averaged estimated margins are at least \(-d\). Therefore its output satisfies
\(\displaystyle \widehat r_t-\bar q_t\geq a_t-\frac{\varepsilon}{2}-d\geq a_t-\varepsilon,\)
\(\displaystyle \sum_t\mu_t\bar q_t-\widehat P\geq\frac{\varepsilon}{16}-d=\frac{\varepsilon}{32}>0,\)
and
\(\displaystyle \widehat U:=\sum_t\mu_t\widehat r_t-\widehat P\geq z-d\geq\mathrm{OPT}-\frac{13\varepsilon}{32}.\)
The algorithm need not know which target has this property. For each output, check the rational conditions
\(\displaystyle \widehat r_t-\bar q_t\geq a_t-\varepsilon\quad\text{for all }t,\qquad \sum_t\mu_t\bar q_t\geq\widehat P.\)
Among outputs passing these checks, choose one maximizing the rational number \(\widehat U\). The good target’s output passes, so this selection is defined.
Because \(\widehat r_t\leq r_t\), \(\widehat P\geq P\), and \(\widehat U\leq U\), the selected output has
\(\displaystyle r_t-\bar q_t\geq a_t-\varepsilon,\qquad \sum_t\mu_t\bar q_t\geq P,\qquad U\geq\mathrm{OPT}-\frac{13\varepsilon}{32}\geq\mathrm{OPT}-\varepsilon.\)
In particular, transfer coverage is exact.
Each oracle output lists at most \(\tau K\) constant-bid blocks. Their masses are rational numbers \(\mu_t/K\), their bids belong to the rational alphabet \(\mathcal B\), and their sequence specifies the colluder tie order.
The selected policy is a rational uniform lottery over \(T\) such profiles, drawn independently of the external realization. Its transfers are rational averages of vectors with coordinates in \(\{0,1\}\).
There are polynomially many objective targets and iterations:
All sampling coordinates have polynomial bit length, even when a type mass is very small or \(E\) is large. Rational-function evaluations, sums, dynamic-program comparisons, and weight updates likewise have polynomial bit complexity. Each weight update adds only polynomially many bits, and there are polynomially many updates.
Thus the running time and output length are polynomial in \(m,\tau,D,L,1/\varepsilon\), with the accuracy input’s encoding included in the total input length.
⟨structured verdict parsed — rendered above⟩
The claimed additive bicriteria FPTAS is established for the payment rule in USER_TASK. The argument provides the required finite rational policy, fixed rational transfers, participation error, exact payment coverage, and objective guarantee. I found no blocking issues.
The strict inequality in \(C_s(b)\) correctly implements the specified priority of colluders over external mass at equal bids. Thus the colluder coordinate \(y\) has combined rank \(y+C_s(\beta(y))\), apart from irrelevant boundary points.
Because \(\beta\) is nonincreasing, \(C_s(\beta(y))\) is nondecreasing. Consequently, the rank argument is nondecreasing, and composition with the nonincreasing extended click curve makes \(h_\beta\) nonincreasing.
The payment simplification is valid. A bounded nonincreasing ranked bid function has at most countably many discontinuities, so \(b(x+)=b(x)\) almost everywhere. Integration over a type’s allocated ranks therefore gives the displayed revenue and aggregate-payment identities. This justifies using an advertiser’s own bid in the subsequent calculations.
The bounds \(0\leq r_t,p_t\leq1\) follow from the ranges of values, bids, and click rates. The promised deterministic profile supplies feasible transfers \(q_t=p_t\), establishing nonemptiness. Summing participation and coverage gives \(U\geq\sum_t\mu_ta_t\geq0\); aggregate revenue at most \(1\) gives \(U\leq1\). Hence the stated bounds on \(\mathrm{OPT}\) are correct.
The equivalence \(e>F(z)\) if and only if \(e>z\) holds for every external bid \(e\), including equality cases.
Rounding bids down therefore preserves every external mass prefix \(C_s\). Retaining the original colluder order within newly created ties also preserves colluder coordinates. Thus clicks and type revenues remain unchanged, while the almost-everywhere own-bid payment weakly decreases.
The resulting alphabet is finite and has size polynomial in the external description length. The zero-bid profile has exactly zero payment under the stated continuum payment rule.
Sorting types. The coefficients \(c_t=\alpha_tv_t/\mu_t\) are well-defined because all type masses are positive. The prefix-integral inequality follows from monotonicity of \(h_\beta\). The displayed decomposition of weighted revenue is correct, including when coefficients coincide or vanish. Its coefficients are nonnegative after sorting, so contiguous type placement maximizes weighted revenue. Payment is unaffected by relabeling types.
Subdivision. After bid restriction, the essential minimum on a positive-length subdivision belongs to the finite bid alphabet. Replacing each subdivision by that minimum preserves nonincreasing bids.
Lowering bids can only move colluders weakly later relative to external mass, so \(h'\leq h\). Since bids and clicks are nonnegative, payment cannot increase.
The lower bound \(h'(y)\geq h(r-)\) is also valid: near the right endpoint, the original finite-level bid function already uses the subdivision’s minimum bid, while earlier points with that same bid have weakly better ranks.
The block-loss inequality consequently holds. Within a type, the sum of within-block variations is at most the total variation of \(h\), which is at most \(1\). The normalization by \(\mu_t\) cancels the block length factor, giving per-type revenue loss at most \(v_t/K\leq1/K\). Therefore weighted revenue loss is at most \(1/K\). No lower bound on the smallest type mass is needed.
Numerical integration. The lower Riemann sums remain valid at jumps and at the allocation cutoff because the extended curve is nonincreasing. The upper-minus-lower sum telescopes to the stated bound \(\ell/H\).
Summing block errors yields
\(0\leq r_t-\widehat r_t\leq1/H\) and
\(0\leq P-P^-\leq1/H\).
Thus \(\widehat P=P^-+1/H\) is a valid upper estimate, with excess at most \(1/H\).
Dynamic programming. For the fixed sorted type order, block coordinates and lengths are independent of bids. A state recording block index and previous bid enforces exactly the required nonincreasing sequence. The displayed edge weights are the estimated weighted objective, apart from the constant payment correction.
The numerical objective error lies between \(0\) and \(2/H\). Combined with subdivision loss, this gives the claimed oracle error
\(\rho=1/K+2/H\).
The comparison extends to randomized policies by averaging the deterministic comparisons.
The weighted-margin coefficients satisfy
\(\sum_t\alpha_t=1-w_C\leq1\) and
\(\beta=1-\sum_tw_t\leq1\).
They are nonnegative, so the oracle applies.
The coefficient of \(q_t\) is correctly identified as \(w_C\mu_t-w_t\). Maximizing each transfer over \([0,1]\) therefore permits the stated binary choice; either endpoint is valid when the coefficient vanishes.
The estimated margins lie in \([-3,3]\). Hence the multiplicative updates stay positive and satisfy the hypotheses of both logarithmic inequalities.
The displayed regret inequality has the correct sign and scaling. With the specified iteration count,
\(3\log n/(\eta T)\leq d/4\), and \(3\eta=d/4\).
Also,
\(\rho\leq\varepsilon/64=d/2\).
Thus a comparator with nonnegative true margins implies every averaged estimated margin is at least \(-d\).
Averaging the transfer vectors produces one fixed rational transfer vector in \([0,1]^\tau\). Linearity justifies using that vector with the uniform policy lottery.
Nonemptiness and the definition of supremum justify choosing the stated near-optimal feasible comparator; attainment of \(\mathrm{OPT}\) is unnecessary.
The modified transfers stay in \([0,1]\). The participation loss is at most
\(\theta(a_t+1/2)\leq3\varepsilon/16\),
and the aggregate coverage slack is at least
\(\theta/2=\varepsilon/16\).
The objective loss is at most \(\theta=\varepsilon/8\), giving
\(U(\Gamma')\geq\mathrm{OPT}-3\varepsilon/16\).
Both grid cases are correct. In particular, rounding \(\mathrm{OPT}-\varepsilon/4\) down loses less than another \(\varepsilon/8\), and the resulting target is below \(U(\Gamma')\).
For the good target, the averaged estimates give:
The rational screening procedure necessarily accepts this candidate. Selecting the accepted candidate with largest estimated objective preserves that guarantee. Since revenues are underestimated and payment is overestimated, the selected policy satisfies the actual participation and exact coverage requirements, as well as \(U\geq\mathrm{OPT}-\varepsilon\).
The output profiles have rational masses and bids, with explicit tie order. Their uniform lottery and averaged transfers are rational and independent of the external draw.
The numbers of targets, iterations, blocks, dynamic-program states, and curve evaluations are polynomial in the specified parameters and \(1/\varepsilon\).
Dense rational-function encoding bounds the degrees by the input length. Rational sampling coordinates and evaluations have polynomial bit length, including for very small type masses or large external mass.
The exact weight updates do not invalidate this bound: each update uses margins computed from a rational block profile with polynomial-size data. Polynomially many such multiplicative updates give polynomial-size weight representations. Normalization, objective comparisons, and dynamic-program arithmetic therefore also have polynomial bit complexity.
No cited external optimization theorem is needed to complete the argument; the necessary oracle and regret estimates are supplied in the write-up.
None. The proof establishes the requested approximation guarantee; it does not claim exact computation of \(\mathrm{OPT}\).
⟨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.