Answer: \(R(D)=1\) for every admissible \(D\), and \(\sup_D R(D)=1\). A deterministic policy attains the benchmark at every stopping level and is computable in time polynomial in \(m,\tau,q,L\). The bound \(H(D)\) is sharp only when \(q=1\).
Proposition 6.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateNo algorithm can have better than a Pm i=1 hi approximation to optimal social welfare.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given at most τ advertiser types \(t=(k_t,c_t)\), with rational masses μ_t summing to \(1\), and a finite rational distribution \(D\) over per-capita total supply \(S\), impressions arrive as infinitesimal supply and the stopping level is hidden. An online policy irrevocably advances advertiser mass through progress states \(0,\ldots,k_t\), earning \(c_t\) per unit mass that completes its campaign. The clairvoyant benchmark at supply \(s\) is \(\max\{\sum_t c_t x_t:\sum_t k_t x_t\le s,\ 0\le x_t\le μ_t\}\). For inputs with binary encoding length \(L\), characterize the minimum worst-case ratio \(\sup_{μ,D}\inf_A \mathbb{E}[\mathrm{OPT}_{μ}(S)]/\mathbb{E}[W_A(S)]\), and determine whether the cumulative-hazard lower bound from Proposition 6.1 has a tight analogue with a policy computable in time polynomial in τ, the support size of \(D\), campaign demands, and \(L\).
A society is given by its support: the list of \(\tau\) advertiser types \(t=(k_t,c_t)\) with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\), \(k_t\in\mathbb Z_{>0}\), and \(c_t\in\mathbb Q_{\ge0}\), with some \(c_t>0\). Here \(\tau\) is the support size, not the number of possible types.
Write \(m=\sum_t k_t\) and \(M=\sum_t\mu_t k_t\). The known supply distribution \(D\) has \(q\) positive-probability rational atoms \(0<s_1<\cdots<s_q\le M\), with binary-rational probabilities \(p_j\); \(L\) is the total input bit length. No monotone-hazard assumption is imposed.
Supply arrives continuously and must be allocated immediately or discarded; its stopping level \(S\sim D\) is hidden. All types are known, and policies may randomize without incentive constraints.
An infinitesimal mass \(\delta\) advanced from progress \(j-1\) to \(j\) consumes \(\delta\) supply. Formally, cumulative transition masses \(F_{t,j}(s)\) are nondecreasing and absolutely continuous, start at zero, satisfy \(\mu_t\ge F_{t,1}(s)\ge\cdots\ge F_{t,k_t}(s)\ge0\), and obey \(\sum_{t,j}F'_{t,j}(s)\le1\) almost everywhere. Policies may split mass and pause or resume campaigns; transitions are irreversible.
At stopping supply \(s\), welfare is \(W_A(s)=\sum_t c_tF_{t,k_t}(s)\); incomplete mass earns zero. The benchmark is \(\mathrm{OPT}_{\mu}(s)=\max\{\sum_t c_tx_t:\sum_t k_tx_t\le s,\ 0\le x_t\le\mu_t\}\).
Define \(H(D)=\sum_{j=1}^{q}p_j/\sum_{\ell=j}^{q}p_\ell\) and \(R(D)=\sup_{(t,\mu)}\inf_A\mathbb E_D[\mathrm{OPT}_{\mu}(S)]/\mathbb E_{D,A}[W_A(S)]\), over societies satisfying the supply bound; a zero denominator gives infinite ratio.
What is the sharp ratio \(R(D)\), and hence \(\sup_D R(D)\)? Does \(H(D)\) remain a tight worst-case approximation bound, with an attaining policy computable in time polynomial in \(m,\tau,q,L\), or does the sharp bound differ?
For indivisible bidders with campaign-completion valuations, a cumulative-hazard competitive lower bound and matching upper bound are established; polynomial-time implementation is also given with an additional factor of \(2\). [Source](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/adauctions2009_babioff_blumrosen_roth.pdf)
No result settling exactly this mass-and-progress model was located in the literature search.
For the stated mass-and-progress model, \(R(D)=1\) for every admissible \(D\). Consequently, \(\sup_D R(D)=1\).
A deterministic policy attains the benchmark at every stopping level and is computable in polynomial time. This holds for arbitrary campaign lengths \(k_t\), not just unit-length campaigns.
Fix a society and any feasible policy realization. Absolute continuity, the zero initial conditions, and the supply constraint imply
\(\displaystyle \sum_t\sum_{j=1}^{k_t}F_{t,j}(s)=\int_0^s\sum_t\sum_{j=1}^{k_t}F'_{t,j}(u)\,du\le s.\)
Since \(F_{t,j}(s)\ge F_{t,k_t}(s)\) for every \(j\),
\(\displaystyle \sum_t k_tF_{t,k_t}(s)\le s.\)
Also, \(0\le F_{t,k_t}(s)\le\mu_t\). Thus the completed masses \(x_t=F_{t,k_t}(s)\) constitute a feasible solution to the benchmark optimization problem. Therefore
\(\displaystyle W_A(s)\le\mathrm{OPT}_{\mu}(s).\)
This holds for every admissible realization of a randomized policy, so it also holds after taking expectations.
Relabel the types so that their welfare densities satisfy
\(\displaystyle d_1\ge d_2\ge\cdots\ge d_\tau\ge0,\qquad d_i=\frac{c_i}{k_i}.\)
Define their supply capacities and cumulative capacities by
\(\displaystyle a_i=k_i\mu_i,\qquad B_0=0,\qquad B_r=\sum_{i=1}^r a_i.\)
In particular, \(B_\tau=M\). For \(0\le s\le M\), define
\(\displaystyle y_i(s)=\min\{a_i,\max\{0,s-B_{i-1}\}\},\qquad x_i(s)=\frac{y_i(s)}{k_i}.\)
These allocations fill the types in decreasing density order. They satisfy \(0\le x_i(s)\le\mu_i\) and
\(\displaystyle \sum_{i=1}^{\tau}k_ix_i(s)=s.\)
We verify optimality explicitly. Given any benchmark-feasible allocation \(z_i\), put \(u_i=k_iz_i\). Then \(0\le u_i\le a_i\) and \(\sum_i u_i\le s\). Consequently, for each \(r\),
\(\displaystyle \sum_{i=1}^r u_i\le\min\{s,B_r\}.\)
The constructed allocation satisfies
\(\displaystyle \sum_{i=1}^r y_i(s)=\min\{s,B_r\},\)
because the first \(r\) types occupy consecutive supply intervals whose union is \([0,B_r]\).
Set \(d_{\tau+1}=0\). The finite telescoping identity gives
\(\displaystyle \sum_{i=1}^{\tau}c_iz_i=\sum_{i=1}^{\tau}d_iu_i=\sum_{r=1}^{\tau}(d_r-d_{r+1})\sum_{i=1}^r u_i.\)
All coefficients \(d_r-d_{r+1}\) are nonnegative. Applying the prefix bounds therefore yields
\(\displaystyle \sum_{i=1}^{\tau}c_iz_i\le\sum_{r=1}^{\tau}(d_r-d_{r+1})\min\{s,B_r\}=\sum_{i=1}^{\tau}c_ix_i(s).\)
Hence \(x(s)\) attains \(\mathrm{OPT}_{\mu}(s)\) for every \(s\in[0,M]\). Crucially, each coordinate \(x_i(s)\) is nondecreasing in \(s\).
Define the policy by
\(\displaystyle F_{i,j}(s)=x_i(s)\qquad\text{for every }i\text{ and }1\le j\le k_i.\)
These functions are nondecreasing, absolutely continuous, and zero at \(s=0\). The progress constraints hold because
\(\displaystyle \mu_i\ge F_{i,1}(s)=\cdots=F_{i,k_i}(s)\ge0.\)
For \(s\in(B_{i-1},B_i)\), the only changing type is \(i\), and each of its transition masses increases at rate \(1/k_i\). Thus, away from the finitely many breakpoints,
\(\displaystyle \sum_t\sum_{j=1}^{k_t}F'_{t,j}(s)=k_i\frac1{k_i}=1.\)
After \(M\), keep every function constant. The supply constraint therefore holds almost everywhere.
This is an online policy: its action depends only on the current supply level and the known society. Its welfare satisfies
\(\displaystyle W_A(s)=\sum_i c_iF_{i,k_i}(s)=\sum_i c_ix_i(s)=\mathrm{OPT}_{\mu}(s)\)
at every possible stopping level.
The equality of the transition masses is permitted by the stated formal constraints. They impose neither a positive transit delay nor a positive minimum campaign mass.
Because some type has positive value, its mass is positive, and every supply atom is positive, \(\mathrm{OPT}_{\mu}(s_j)>0\). The attaining policy therefore has positive expected welfare.
Section 1 shows that every policy has ratio at least \(1\), while Section 3 attains ratio \(1\). Thus, for every eligible society,
\(\displaystyle \inf_A\frac{\mathbb E_D[\mathrm{OPT}_{\mu}(S)]}{\mathbb E_{D,A}[W_A(S)]}=1.\)
Taking the supremum over societies proves \(R(D)=1\), and then \(\sup_D R(D)=1\).
To compute the policy, sort the rational densities \(c_i/k_i\), compute the rational breakpoints \(B_i\), and output the rates \(1/k_i\) on their respective intervals. Exact comparisons and arithmetic have polynomial bit complexity in \(\tau,L\). An explicit listing of every transition function takes an additional \(O(m)\) entries. Hence implementation is polynomial in \(m,\tau,q,L\); the policy does not require \(D\).
Finally, \(H(D)=1\) when \(q=1\), while \(H(D)>1\) when \(q>1\), because its last summand is \(1\) and every earlier summand is positive. Thus \(H(D)\) is a valid but nonsharp bound whenever \(q>1\).
The cumulative-hazard result in the [cited paper, Section 6 and Appendix A.5](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/adauctions2009_babioff_blumrosen_roth.pdf) concerns indivisible campaign-completion bidders. Here, divisible masses admit the nested fractional optima constructed above.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct for the formal mass-and-progress model in USER_TASK. It establishes \(R(D)=1\), \(\sup_D R(D)=1\), and a deterministic attaining policy computable in time polynomial in \(m,\tau,q,L\). No major or minor mathematical issues were found.
Absolute continuity and the zero initial conditions justify integrating the derivative constraint. The sums are finite, so exchanging summation and integration is valid. The resulting inequality \(\sum_{t,j}F_{t,j}(s)\le s\), together with \(F_{t,j}(s)\ge F_{t,k_t}(s)\), gives \(\sum_t k_tF_{t,k_t}(s)\le s\). The completed masses therefore satisfy every benchmark constraint. This proves the welfare upper bound for each realization, including randomized policies, and hence in expectation.
Each capacity \(a_i=k_i\mu_i\) is strictly positive, and the consecutive intervals have total length \(M\). The clipped functions \(y_i(s)\) satisfy their capacity bounds and sum to \(s\) throughout \(0\le s\le M\), including both endpoints. Dividing by positive \(k_i\) gives feasible completed masses.
Any feasible allocation satisfies the claimed prefix bounds because its total supply consumption is at most \(s\) and each prefix has capacity \(B_r\). The constructed allocation attains these bounds. In the telescoping identity, the coefficient of \(u_i\) is \(\sum_{r=i}^{\tau}(d_r-d_{r+1})=d_i\). All differences are nonnegative, so applying the prefix bounds preserves the inequality. Tied densities and zero-valued types cause no exception. No external optimization theorem is needed.
The functions \(F_{i,j}(s)=x_i(s)\) are nondecreasing, absolutely continuous, initially zero, and bounded by \(\mu_i\). Equality between successive transition masses satisfies the progress inequalities exactly.
Within each open capacity interval, precisely one type changes. Its \(k_i\) transitions each have derivative \(1/k_i\), giving total consumption rate \(1\). The finitely many breakpoints do not affect an almost-everywhere constraint. The constant extension after \(M\) is also feasible.
The simultaneous equality of transition masses is the decisive modeling point. USER_TASK explicitly defines feasibility through these cumulative constraints; it does not impose an additional transit-time or strict temporal-precedence condition. The policy therefore qualifies under the assigned model, and its dependence only on current supply and the known society establishes that it is online.
Positive supply, positive mass, and at least one positive value imply a strictly positive benchmark at every supply atom. Thus the attaining policy has positive expected welfare. Every policy has ratio at least \(1\), with zero-denominator policies assigned infinite ratio, while the constructed policy has ratio exactly \(1\). This holds for every eligible society, so taking the stated suprema is justified.
Rational density comparisons, capacity multiplication, and cumulative addition have polynomial bit complexity in the input length. The policy has a finite description through its sorted types, rational breakpoints, and transition rates. Explicitly listing all transitions requires \(O(m)\) entries, as acknowledged. No enumeration of campaign lengths in time polynomial solely in their binary encoding is claimed.
The last summand of \(H(D)\) is \(1\); every earlier summand is strictly positive. Consequently, \(H(D)=1\) exactly when \(q=1\), and it exceeds the sharp ratio when \(q>1\). The cited paper’s Section 6 and Appendix A.5 concern discrete bidders with knapsack completion valuations, so that comparison does not introduce an unsupported theorem application into this proof. [Auctions with Online Supply](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/adauctions2009_babioff_blumrosen_roth.pdf)
Required clarification or repair: None.
⟨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.