Answer: —
Theorem 3 — class: other
Given rational cohort masses \(\mu_\theta\) summing to \(1\), values \(v_\theta\), unknown shared click rates \(p_\theta\), a per-advertiser quota \(q\), and \(H\le q\), form \(N\mu_\theta\) individually identifiable advertisers of each type and run \(T_N=HN\) rounds. Each round selects one eligible advertiser and observes only that advertiser’s click; determine the minimax expected regret as \(N\to\infty\) among deterministic, normalized, truthful mechanisms with bid-independent exploratory rounds, against the static benchmark maximizing \(\sum_\theta x_\theta v_\theta p_\theta\) subject to \(0\le x_\theta\le q\mu_\theta\) and \(\sum_\theta x_\theta=H\). When a best cohort has enough capacity for all \(H\) and has a fixed \(\delta\)-gap over the runner-up, determine whether the paper’s polynomial gap-regret phenomenon persists.
A society is given by its support: the list of \(\tau\geq2\) types with positive masses \(\mu_\theta\), each a binary rational, with \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
Fix a public impression quota \(q\in\mathbb{Z}_{>0}\) and rational \(0<H\leq q\). For each integer \(N\) with \(N\mu_\theta\) and \(HN\) integral, create \(N\mu_\theta\) identifiable advertisers of type \(\theta\) and run \(T_N=HN\) rounds; each round must select one advertiser with fewer than \(q\) previous impressions.
Public cohort membership certifies a shared unknown click probability \(p_\theta\in[0,1]\), but reveals no private values. Potential clicks are independent across advertisers and rounds, with no prior on \(p\); only the selected advertiser's click is observed. Performance is evaluated on profiles where every member of cohort \(\theta\) has private value \(v_\theta\in\mathbb{Q}\cap(0,1]\) per click.
Each advertiser submits one positive bid. Allocation is deterministic and online; payments use only bids and observed clicks. Truthfulness means dominant-strategy truthfulness for every complete potential-click realization and every profile of positive individual values and bids, including profiles without equal values within cohorts; utility is value times received clicks minus payment. Normalization means each advertiser's payment tends to zero as her bid tends to zero, holding other bids and the realization fixed.
Require exploration separation: for every complete realization \(\rho\), if for some bid profile flipping the selected advertiser's click at round \(t\) changes any later allocation, then the advertiser selected at \(t\), with \(\rho\) fixed, is independent of the entire bid profile. Let \(\mathcal{M}_N\) be this mechanism class.
Define \(B(\mu,v,p)=\max\{\sum_\theta x_\theta v_\theta p_\theta:0\leq x_\theta\leq q\mu_\theta,\ \sum_\theta x_\theta=H\}\) and \(R_M(N)=\sup_{v,p}\{NB(\mu,v,p)-\mathbb{E}[\text{total click value under truthful bids}]\}\). Define \(R_{M,\delta}(N)\) by restricting this supremum to instances with a unique best cohort \(\theta^*\), \(q\mu_{\theta^*}\geq H\), and \(v_{\theta^*}p_{\theta^*}-\max_{\theta\ne\theta^*}v_\theta p_\theta=\delta\max_\theta v_\theta\), for fixed \(0<\delta\leq\tfrac14\).
The support, \(q\), and \(H\) remain fixed as \(N\to\infty\) through admissible integers. Running times are measured in \(m=1\) ad slot, \(\tau\), total binary input and bid length \(L\), and \(N,q,H\).
What is the asymptotic order of \(\inf_{M\in\mathcal{M}_N}R_M(N)\), including its dependence on \(\tau,\mu,q,H\)?
For mechanism families satisfying \(R_M(N)=O(N^\gamma)\) with \(\gamma<1\), what is the sharp tradeoff with \(R_{M,\delta}(N)\): is polynomial growth unavoidable, or can polylogarithmic growth occur?
For finitely many uncapacitated advertisers, deterministic exploration-separated allocation rules have worst-case regret \(\Omega(k^{1/3}T^{2/3})\); for fixed \(k\), normalized truthful mechanisms match this up to logarithmic factors. Under \(R(T)=O(T^\gamma)\), their gap regret is \(\Omega(\delta T^{2(1-\gamma)-\epsilon})\) for every \(\epsilon>0\). [Source](https://arxiv.org/html/0812.2291)
No result settling this exact model with shared cohort click probabilities and individual impression quotas was located.
This is a partial solution. It proves the fixed-support phase diagram and the sharp polynomial exponent of the worst-case/gap-regret tradeoff, repairing the value-scaling issue identified in the verifier report.
It also strengthens the parameter dependence in two ways:
Matching the general parameter dependence in the latter regime remains open.
All limits below run through admissible integers $N$. Write
$$
c_\theta=q\mu_\theta,\qquad C_\theta=c_\theta N,\qquad T=HN.
$$
Thus $C_\theta$ and $T$ are integers, and $\sum_\theta C_\theta=qN$.
For a truthful homogeneous cohort-value profile, put
$$
s_\theta=v_\theta p_\theta.
$$
If $A_\theta$ denotes the mechanism’s total impression count for cohort $\theta$, then
$$
\mathbb E[\text{total click value}]
=\sum_\theta s_\theta\,\mathbb E[A_\theta].
$$
Indeed, conditional on the history preceding a round and the advertiser selected in that round, its click has the corresponding cohort probability. The selection is online and therefore independent of that round’s potential clicks.
The benchmark $NB$ is the maximum of $s\cdot x$ over
$$
0\le x_\theta\le C_\theta,\qquad \sum_\theta x_\theta=T.
$$
It has an integer optimum: sort the cohort scores and fill integer capacities until the integer horizon is exhausted. Integer cohort counts can be distributed among the identifiable advertisers without exceeding their individual quota $q$.
If $H=q$, every feasible mechanism exhausts all advertiser quotas. Consequently,
$$
\inf_{M\in\mathcal M_N}R_M(N)=0.
$$
Henceforth assume $H<q$ and define
$$
d=q-H,\qquad
\ell_\theta=(c_\theta-d)_+,\qquad
u_\theta=\min(c_\theta,H),\qquad
w_\theta=u_\theta-\ell_\theta,
$$
and
$$
Z=\{\theta:\ell_\theta=0\},\qquad a=\min(H,d).
$$
Every feasible count vector satisfies
$$
L_\theta:=\ell_\theta N
\le A_\theta\le
U_\theta:=u_\theta N.
$$
The upper bound follows from the cohort capacity and horizon. For the lower bound, the other cohorts have total capacity $qN-C_\theta$, so
$$
A_\theta\ge \max(0,T-qN+C_\theta)=L_\theta.
$$
Both endpoints are feasible because the remaining impression count lies between zero and the other cohorts’ total capacity.
The following identity will be useful:
$$
w_\theta=\min(c_\theta,H,d,q-c_\theta)>0.
$$
To verify it, if $c_\theta\le d$, then $\ell_\theta=0$ and $q-c_\theta\ge H$, giving $w_\theta=\min(c_\theta,H)$. If $c_\theta>d$ and $c_\theta\le H$, then $w_\theta=d$. If $c_\theta>d$ and $c_\theta>H$, then $w_\theta=q-c_\theta$, which is smaller than the other three quantities. Positivity follows from $H,d>0$ and the existence of at least two positive-mass cohorts.
There is also strictly positive slack after allocating all mandatory impressions:
$$
\sum_\theta\ell_\theta<H.
$$
For $P=\{\theta:\ell_\theta>0\}$, if $P$ is nonempty, then
$$
H-\sum_\theta\ell_\theta
=\sum_{\theta\notin P}c_\theta+(|P|-1)d>0.
$$
When $|P|=1$, the first term is positive; when $|P|\ge2$, the second is positive. The assertion is immediate if $P$ is empty.
Let
$$
r^*(N)=\inf_{M\in\mathcal M_N}R_M(N).
$$
All constant-factor statements below have universal constants, with sufficiently-large-$N$ thresholds allowed to depend on the fixed support parameters.
Suppose $Z=\varnothing$. Sort the positive mandatory quantities as
$$
\ell_{(1)}\le\ell_{(2)}\le\cdots\le\ell_{(\tau)}
$$
and define
$$
\Lambda=
\max_{1\le k\le\tau}
\sqrt{\frac{\log(k+1)}{\ell_{(k)}}}.
$$
Here and below, $\log$ is the natural logarithm.
Then
$$
\boxed{
r^*(N)=\Theta\!\left(d\Lambda\sqrt N\right).
}
$$
For example, for equal masses in this regime,
$$
r^*(N)=
\Theta\!\left(
(q-H)\sqrt{
\frac{N\log(\tau+1)}{q/\tau-(q-H)}
}
\right).
$$
Suppose $Z\ne\varnothing$. Define the family of simultaneously omittable cohort sets
$$
\mathcal J=
\left\{
J\subseteq Z:\sum_{\theta\in J}c_\theta\le d
\right\},
$$
and put
$$
\kappa=\max_{J\in\mathcal J}|J|,
\qquad
F=\max_{J\in\mathcal J}\sum_{\theta\in J}w_\theta^2.
$$
A singleton containing any member of $Z$ belongs to $\mathcal J$, so $\kappa\ge1$ and $F>0$.
There are universal constants $b,B>0$ such that
$$
\boxed{
bF^{1/3}
\le
\liminf_{N\to\infty}\frac{r^*(N)}{N^{2/3}}
\le
\limsup_{N\to\infty}\frac{r^*(N)}{N^{2/3}}
\le
B\min\left\{
\sum_{\theta\in Z}w_\theta^{2/3},
\left(\kappa a^2\log(2\tau)\right)^{1/3}
\right\}.
}
$$
The lower bound strengthens the maximum-over-one-cohort bound in the notes. The upper bound also replaces the horizon quantity $H$ by $\min(H,q-H)$ and the number of omittable cohorts by $\kappa$ in its second alternative.
These bounds do not generally match.
In particular,
$$
\boxed{
r^*(N)=
\begin{cases}
0,&H=q,\\
\Theta_{\mu,q,H}(\sqrt N),&H<q,\ Z=\varnothing,\\
\Theta_{\mu,q,H}(N^{2/3}),&H<q,\ Z\ne\varnothing.
\end{cases}
}
$$
The square-root regime is exactly
$$
q(1-\min_\theta\mu_\theta)<H<q.
$$
At equality, at least one cohort is omittable, and the exponent is $2/3$.
Let
$$
S=\{\theta:c_\theta\ge H\}.
$$
The restricted gap class is nonempty exactly when $S\ne\varnothing$. If $S=\varnothing$, the restricted supremum is over an empty class and does not represent a nonnegative regret quantity without a convention.
When $S\ne\varnothing$, every mechanism family with
$$
r_N:=R_M(N)=o(N)
$$
satisfies, for sufficiently large admissible $N$,
$$
\boxed{
R_{M,\delta}(N)\ge
\frac{\delta N^2}{8192r_N^2}
\max_{k\in S}\sum_{j\ne k}u_j^2.
}
$$
Therefore, if $R_M(N)=O(N^\gamma)$ with $\gamma<1$, then
$$
R_{M,\delta}(N)=\Omega_{\mu,q,H,\delta}
\left(N^{2(1-\gamma)}\right).
$$
Necessarily $\gamma\ge2/3$. Conversely, for every $\gamma\in[2/3,1)$ there is a mechanism family satisfying
$$
R_M(N)=O_{\mu,q,H}(N^\gamma),
\qquad
R_{M,\delta}(N)=
O_{\mu,q,H,\delta}\left(N^{2(1-\gamma)}\right).
$$
Thus polynomial gap regret is unavoidable whenever the stipulated gap class is nonempty. Polylogarithmic gap regret cannot occur under a fixed sublinear-power worst-case guarantee.
The remainder proves these statements.
Choose deterministic integer exploration counts satisfying
$$
q\le E_\theta\le C_\theta,\qquad
E_\theta\ge L_\theta,\qquad
\sum_\theta E_\theta\le T.
$$
Designate one advertiser in each cohort as its reporter. Use the following mechanism:
$$
\widehat s_\theta=
b_{\mathrm{reporter},\theta}\widehat p_\theta
$$
and filling the residual cohort capacities in that order.
A reporter receives the same $q$ impressions at the same rounds under every bid profile and receives no exploitation impressions. Her click count and zero payment are therefore independent of her own bid for every complete realization.
Every other advertiser’s bid is unused. Her allocations and payment are consequently independent of her own bid.
Thus truthful bidding is weakly dominant for every positive individual-value profile, including heterogeneous values within cohorts. This uses precisely the weak dominant-strategy requirement in the question.
Payments are identically zero, so normalization holds. Every exploration allocation is independent of the entire bid profile. Exploitation clicks do not affect later allocations. Hence exploration separation holds.
Under truthful homogeneous cohort values,
$$
\widehat s_\theta=v_\theta\widehat p_\theta.
$$
First compare the benchmark with the best allocation constrained to give each cohort at least $E_\theta$ impressions. Starting from a benchmark count vector, fill deficits below $E_\theta$ by reducing counts above their corresponding requirements. Such reductions are possible because $\sum E_\theta\le T$.
At most
$$
\sum_\theta(E_\theta-L_\theta)
$$
impressions move, and every move loses at most one unit of expected value.
Let $y^*$ maximize the true residual scores and let $\widehat y$ maximize the estimated residual scores. Estimated-score optimality gives
$$
s\cdot y^*-s\cdot\widehat y
\le
(s-\widehat s)\cdot(y^*-\widehat y)
\le
N\sum_\theta
w_\theta|\widehat p_\theta-p_\theta|.
$$
For the last inequality, the complete allocations $E+y^*$ and $E+\widehat y$ are feasible, so their coordinate differences are bounded by $w_\theta N$; also $v_\theta\le1$.
Exploration is fixed, so the $E_\theta$ observations are independent Bernoulli variables with mean $p_\theta$. Consequently,
$$
\mathbb E|\widehat p_\theta-p_\theta|
\le
\sqrt{\operatorname{Var}(\widehat p_\theta)}
\le\frac1{2\sqrt{E_\theta}}.
$$
We obtain
$$
\boxed{
R_M(N)\le
\sum_\theta(E_\theta-L_\theta)
+\frac N2\sum_\theta\frac{w_\theta}{\sqrt{E_\theta}}.
}
$$
There is a second estimation bound. If $x,x'$ are feasible count vectors, then
$$
\sum_\theta(x_\theta-x'_\theta)_+
\le HN.
$$
Applying the same observation to the unused capacities $C-x$ and $C-x'$, whose totals are $dN$, gives
$$
\sum_\theta(x_\theta-x'_\theta)_+\le dN.
$$
Thus
$$
\|x-x'\|_1\le2aN.
$$
It follows that residual estimation regret is at most
$$
2aN\max_\theta|\widehat p_\theta-p_\theta|.
$$
The next lemma applies to every deterministic exploration-separated allocation rule. Truthfulness is not needed for it.
Fix a complete potential-click table. At round $t$, regard the selected advertiser as a function of the entire bid profile.
Suppose this function is nonconstant. Flipping any one advertiser’s entry in the click row at $t$ leaves all later allocations unchanged for every bid profile:
Selection at $t$ depends only on earlier rows, so it remains nonconstant as entries in the current row are changed. We may therefore replace the entire row by zeros without changing any allocation under any bid profile.
Process rows chronologically:
In the second case, erased entries are unobserved under every bid profile and hence cannot affect allocations.
The resulting transcript, denoted $Y$, has three properties:
The first property follows because online selection at the next round depends only on the already processed rows. The erasure operations preserve all allocations, proving the other two properties.
Let $S_j$ be the number of retained observations from cohort $j$. Pathwise, under every bid profile,
$$
S_j\le A_j.
$$
Consider two environments differing only in cohort $j$. Its probabilities are respectively $1/2$ and $1/2+\varepsilon$, with $|\varepsilon|\le1/4$. Let their transcript laws be $P_0,P_\varepsilon$, and put
$$
e_j=\mathbb E_0[S_j].
$$
Conditional on the retained past, sampling decisions agree in both environments, and a retained observation is a fresh Bernoulli sample. The relative-entropy chain rule therefore gives
$$
D(P_0\Vert P_\varepsilon)
=e_j\operatorname{kl}(1/2,1/2+\varepsilon).
$$
Here
$$
\operatorname{kl}(1/2,1/2+\varepsilon)
=-\frac12\log(1-4\varepsilon^2)
\le4\varepsilon^2.
$$
For example, the inequality follows from
$$
-\log(1-x)\le\frac{x}{1-x}
$$
and $4\varepsilon^2\le1/4$.
Pinsker’s inequality gives
$$
\boxed{
\operatorname{TV}(P_0,P_\varepsilon)
\le\sqrt2\,|\varepsilon|\sqrt{e_j}.
}
$$
For fixed bids, $A_j$ is a transcript function taking values in $[L_j,U_j]$. The bounded-function characterization of total variation consequently yields
$$
\boxed{
|\mathbb E_\varepsilon A_j-\mathbb E_0A_j|
\le w_jN\,\operatorname{TV}(P_0,P_\varepsilon).
}
$$
We will also use the reverse-direction calculation. If cohort $j$ changes from $1/2$ to $1/2-\varepsilon$, then
$$
D(P_j\Vert P_0)
=\mathbb E_j[S_j]\operatorname{kl}(1/2-\varepsilon,1/2)
\le4\varepsilon^2\mathbb E_j[S_j].
$$
The Bernoulli bound follows from $D(P\Vert Q)\le\chi^2(P,Q)$; here the latter is $4\varepsilon^2$.
Fix a mechanism and write $r=R_M(N)$. Use the baseline environment with every probability equal to $1/2$, and put
$$
e_j=\mathbb E_0[S_j].
$$
Give every cohort value one. Change only cohort $j$’s probability to $1/2+\varepsilon$ or $1/2-\varepsilon$.
In the positive instance, a benchmark gives $j$ exactly $U_j$ impressions. In the negative instance, it gives $j$ exactly $L_j$. Thus the two regrets are
$$
\varepsilon(U_j-\mathbb E_+A_j),
\qquad
\varepsilon(\mathbb E_-A_j-L_j).
$$
Adding them and applying the transcript bounds gives
$$
2r\ge
\varepsilon w_jN
\left(1-2\sqrt2\,\varepsilon\sqrt{e_j}\right).
$$
Take
$$
\varepsilon=\frac1{8\sqrt{e_j+1}}.
$$
The parenthesized term is at least $1/2$, so
$$
\boxed{
r\ge\frac{w_jN}{32\sqrt{e_j+1}}.
}
$$
In particular, $r>0$ whenever $H<q$.
Keep the baseline probabilities, but give cohort $j$ value $1/2$ and every other cohort value one.
The benchmark gives $j$ its minimum feasible count $L_j$. Every impression above that count loses $1/4$. Hence
$$
r\ge\frac14(\mathbb E[A_j]-L_j).
$$
Because the transcript is independent of bids and $S_j\le A_j$,
$$
e_j\le L_j+4r.
$$
Combining this with the two-instance bound gives the nonasymptotic inequality
$$
\boxed{
r^2(\ell_jN+4r+1)
\ge\frac{w_j^2N^2}{1024}.
}
$$
A uniform version holds in every environment with
$$
p_\theta\in[1/4,3/4].
$$
Give cohort $j$ value $1/8$ and all others value one. Its score is at most $3/32$, whereas every other score is at least $1/4$. Reducing its allocation from $A_j$ to $L_j$ and filling available capacity elsewhere improves expected value by at least
$$
\frac18(A_j-L_j).
$$
Therefore, in every such environment,
$$
\boxed{
\mathbb E[S_j]\le L_j+8r.
}
$$
This bound uses valid rational homogeneous values and bid independence of the transcript.
Assume $Z=\varnothing$.
Since every $c_\theta>d$ and there are at least two cohorts,
$$
H>d,\qquad c_\theta<H,\qquad q-c_\theta>d.
$$
Thus
$$
w_\theta=d,\qquad L_\theta=(c_\theta-d)N.
$$
Equivalently, every feasible allocation leaves unused counts
$$
O_\theta=C_\theta-A_\theta
$$
satisfying
$$
0\le O_\theta\le dN,\qquad \sum_\theta O_\theta=dN.
$$
Use the reporter mechanism with
$$
E_\theta=L_\theta.
$$
This is feasible for sufficiently large $N$: each $L_\theta$ eventually exceeds $q$, and $\sum L_\theta<T$.
There is no exploration-forcing loss. The estimation bound from Section 3 gives
$$
R_M(N)\le2dN\,\mathbb E X,
\qquad
X=\max_\theta|\widehat p_\theta-p_\theta|.
$$
Hoeffding’s inequality applies to each fixed collection of $L_\theta$ independent Bernoulli observations. Sorting the mandatory quantities, for $z\ge\Lambda$,
$$
\begin{aligned}
\Pr\left(X>\frac z{\sqrt N}\right)
&\le2\sum_{k=1}^{\tau}\exp(-2\ell_{(k)}z^2)\\
&\le2\sum_{k=1}^{\tau}(k+1)^{-2z^2/\Lambda^2}.
\end{aligned}
$$
The second inequality uses
$$
\ell_{(k)}\ge\frac{\log(k+1)}{\Lambda^2}.
$$
For $b\ge2$,
$$
\sum_{m=2}^{\infty}m^{-b}
\le2^{-b}+\int_2^\infty x^{-b}\,dx
\le3\cdot2^{-b}.
$$
Consequently,
$$
\Pr\left(X>\frac z{\sqrt N}\right)
\le6\exp\left(-2\log2\,\frac{z^2}{\Lambda^2}\right)
\qquad(z\ge\Lambda).
$$
Integrating the tail yields
$$
\mathbb E X\le C_0\frac{\Lambda}{\sqrt N}
$$
for a universal finite constant $C_0$. Thus
$$
r^*(N)\le2C_0d\Lambda\sqrt N.
$$
Consider any mechanism. If
$$
r\ge d\Lambda\sqrt N,
$$
the desired lower bound already holds.
Otherwise, for sufficiently large $N$,
$$
8r\le\ell_{(1)}N.
$$
The baseline sampling constraint gives, for a cohort with mandatory quantity $\ell_{(1)}$,
$$
e_j\le L_j+8r\le2\ell_{(1)}N.
$$
Section 5 therefore implies
$$
r\ge
\frac{dN}{32\sqrt{2\ell_{(1)}N+1}}
=\Omega\!\left(\frac d{\sqrt{\ell_{(1)}}}\sqrt N\right).
$$
This controls the terms defining $\Lambda$ with $k\le3$, because
$$
\sqrt{\frac{\log(k+1)}{\ell_{(k)}}}
\le
\sqrt{\frac{\log4}{\ell_{(1)}}}.
$$
Fix $K\ge4$ and let $J$ contain the $K$ cohorts with smallest mandatory quantities.
For each $j\in J$, consider the environment
$$
p_j=\frac12-\varepsilon,\qquad
p_\theta=\frac12\quad(\theta\ne j),
$$
with every value equal to one. Denote its transcript law by $P_j$, and denote the all-$1/2$ transcript law by $P_0$.
For sufficiently large $N$, choose
$$
\varepsilon=
\frac18\sqrt{\frac{\log K}{\ell_{(K)}N}}
\le\frac14.
$$
Under the assumption $r<d\Lambda\sqrt N$, the uniform sampling constraint gives
$$
\mathbb E_j[S_j]
\le L_j+8r
\le2\ell_{(K)}N.
$$
Therefore,
$$
D(P_j\Vert P_0)
\le4\varepsilon^2\mathbb E_j[S_j]
\le\frac18\log K.
$$
In environment $j$, the benchmark leaves all $dN$ unused impressions in cohort $j$. Its regret is exactly
$$
\varepsilon(dN-\mathbb E_j[O_j]).
$$
Because this is at most $r$,
$$
\frac{\mathbb E_j[O_j]}{dN}
\ge1-\frac r{\varepsilon dN}.
$$
Given the transcript, construct a randomized decoder by selecting a cohort with probabilities
$$
\frac{O_\theta}{dN}.
$$
If it selects a cohort outside $J$, map that answer to any fixed member of $J$. Its probability of correctly identifying $j$ is at least $\mathbb E_j[O_j]/(dN)$.
For completeness, the information inequality needed here is as follows. Let the true index be uniform on $J$, and let $\overline P$ be the average transcript law. Then
$$
I(J;Y)
=\frac1K\sum_{j\in J}D(P_j\Vert\overline P)
\le\frac1K\sum_{j\in J}D(P_j\Vert P_0)
\le\frac18\log K.
$$
The middle inequality follows from the identity
$$
\frac1K\sum_jD(P_j\Vert P_0)
=I(J;Y)+D(\overline P\Vert P_0).
$$
For any decoder, including one using independent randomization, the entropy bound
$$
H(J\mid Y)\le\log2+\Pr(\text{error})\log K
$$
implies
$$
\Pr(\text{correct})
\le\frac{I(J;Y)+\log2}{\log K}
\le\frac58.
$$
Here $K\ge4$ ensures $\log2/\log K\le1/2$.
Comparing this with the decoder’s lower success bound gives
$$
r\ge\frac38\varepsilon dN
=\frac3{64}d\sqrt N
\sqrt{\frac{\log K}{\ell_{(K)}}}.
$$
Since $\log(K+1)\le2\log K$, this controls the corresponding term in $\Lambda$.
Combining the single-cohort and multiple-cohort arguments proves
$$
r^*(N)=\Theta(d\Lambda\sqrt N).
$$
Assume $Z\ne\varnothing$.
Return to the baseline environment with all probabilities $1/2$. For any $J\in\mathcal J$, give cohorts in $J$ value $1/2$ and all other cohorts value one.
Because
$$
\sum_{j\in J}C_j\le dN,
$$
the other cohorts have capacity at least $T$. The benchmark omits every cohort in $J$, and the instance regret is exactly
$$
\frac14\sum_{j\in J}\mathbb E[A_j].
$$
Bid independence of the transcript gives
$$
\sum_{j\in J}e_j\le4r.
$$
For each $j$, the two-instance bound gives
$$
\frac{w_j^2N^2}{1024r^2}\le e_j+1.
$$
Choose a set $J$ attaining $F$ and sum:
$$
\frac{FN^2}{1024r^2}
\le\sum_{j\in J}e_j+|J|
\le4r+\kappa.
$$
Thus
$$
\boxed{
r^2(4r+\kappa)\ge\frac{FN^2}{1024}.
}
$$
Since $F>0$, this inequality forces $r\ge\kappa$ for sufficiently large $N$. Hence
$$
r^3\ge\frac{FN^2}{5120},
$$
which proves
$$
r^*(N)\ge bF^{1/3}N^{2/3}
$$
with a universal $b>0$.
Use
$$
E_\theta=
\begin{cases}
L_\theta,&\theta\notin Z,\\
\left\lceil(Nw_\theta/4)^{2/3}\right\rceil,&\theta\in Z.
\end{cases}
$$
For sufficiently large $N$, these counts satisfy all reporter, capacity, and horizon requirements. Indeed, the additional counts are $o(N)$, while every cohort capacity and the slack after mandatory impressions are positive multiples of $N$.
The general regret bound gives
$$
R_M(N)\le
\frac3{2^{4/3}}N^{2/3}
\sum_{\theta\in Z}w_\theta^{2/3}
+\frac{\sqrt N}{2}
\sum_{\theta\notin Z}\frac{w_\theta}{\sqrt{\ell_\theta}}
+O(\tau).
$$
The coefficient follows by minimizing
$$
x+\frac{Nw_\theta}{2\sqrt x}.
$$
The mandatory-cohort contribution is $o(N^{2/3})$ for fixed support.
Give each cohort in $Z$ an exploration requirement $n_\theta=o(N)$, and each remaining cohort its mandatory requirement $L_\theta$. Define
$$
P(n)=\max_{J\in\mathcal J}\sum_{j\in J}n_j.
$$
For sufficiently large $N$, the cost of forcing these exploration counts is at most $P(n)$.
To prove this, take any benchmark count vector $x^*$ and let
$$
J=\{j\in Z:x_j^*<n_j\}.
$$
The other cohorts cannot have exploration deficits, because their requirement is their mandatory lower bound.
Since total unused capacity is $dN$,
$$
\sum_{j\in J}(c_jN-x_j^*)\le dN.
$$
Therefore,
$$
\sum_{j\in J}c_j
\le d+\frac{\sum_{j\in Z}n_j}{N}.
$$
There are finitely many subsets of $Z$. If any have capacity sum strictly greater than $d$, the minimum positive excess over $d$ is a fixed positive number. Because $\sum n_j=o(N)$, eventually the displayed inequality forces
$$
\sum_{j\in J}c_j\le d.
$$
Thus $J\in\mathcal J$.
Filling the deficits requires moving at most
$$
\sum_{j\in J}(n_j-x_j^*)
\le P(n)
$$
impressions, proving the assertion.
Use equal exploration counts $n$ for cohorts in $Z$ and mandatory counts elsewhere. For sufficiently large $N$, every cohort has at least $n$ observations.
For fixed independent Bernoulli averages with sample counts at least $n$, Hoeffding’s exponential-moment bound gives
$$
\mathbb E\max_\theta|\widehat p_\theta-p_\theta|
\le\sqrt{\frac{\log(2\tau)}{2n}}.
$$
Explicitly, for either sign,
$$
\mathbb E\exp\bigl(\lambda(\widehat p_\theta-p_\theta)\bigr)
\le\exp\left(\frac{\lambda^2}{8n}\right).
$$
Taking the maximum over both signs and all cohorts, then optimizing
$$
\frac{\log(2\tau)}{\lambda}+\frac{\lambda}{8n},
$$
proves the expectation bound.
The forcing cost is at most $\kappa n$, and Section 3 bounds estimation regret by $2aN$ times the maximum error. Consequently,
$$
R_M(N)\le
\kappa n+
2aN\sqrt{\frac{\log(2\tau)}{2n}}.
$$
Choosing $n$ of order
$$
\left(\frac{a^2N^2\log(2\tau)}{\kappa^2}\right)^{1/3}
$$
proves
$$
R_M(N)=
O\!\left(
\left(\kappa a^2\log(2\tau)\right)^{1/3}N^{2/3}
\right).
$$
This bound is asserted only for $Z\ne\varnothing$.
Suppose every cohort can individually fill the horizon:
$$
H\le\min_\theta c_\theta.
$$
Then $H\le q/2$, every cohort belongs to $Z$, and
$$
w_\theta=H,\qquad \kappa=\tau-1,\qquad
F=(\tau-1)H^2.
$$
Indeed, every proper cohort subset has capacity at most $q-H=d$, because its complement contains a cohort of capacity at least $H$.
The bounds become
$$
\Omega\!\left((\tau-1)^{1/3}(HN)^{2/3}\right)
\le r^*(N)
\le
O\!\left(
((\tau-1)\log(2\tau))^{1/3}(HN)^{2/3}
\right).
$$
Thus in this special case the remaining parameter gap is only a factor of order $(\log(2\tau))^{1/3}$.
A best cohort satisfying the capacity condition must belong to
$$
S=\{k:c_k\ge H\}.
$$
Conversely, for any $k\in S$, setting all values to one and
$$
p_k=\frac12+\delta,\qquad
p_j=\frac12\quad(j\ne k)
$$
gives a valid restricted instance. Thus the gap class is nonempty exactly when $S\ne\varnothing$.
Moreover, if $k\in S$, then for every $j\ne k$,
$$
c_j\le q-c_k\le q-H=d.
$$
Hence every other cohort lies in $Z$. A nonempty gap class therefore implies the $N^{2/3}$ worst-case regime.
Fix $k\in S$ and use the preceding gap environment. Let
$$
e_j=\mathbb E[S_j]
$$
under its bid-independent transcript law.
Fix $j\ne k$. Construct two separate hard instances by keeping all values except $v_k$ equal to one and choosing rational $v_k\in(0,1]$ such that
$$
\left|
v_k(1/2+\delta)-1/2
\right|\le\frac\varepsilon4.
$$
Such a rational exists by density, since the target value
$$
\frac1{1+2\delta}
$$
lies strictly between zero and one.
Change $p_j$ to $1/2+\varepsilon$ or $1/2-\varepsilon$. In the positive instance, cohort $j$ is better than every other cohort by at least $3\varepsilon/4$. In the negative instance, it is worse than every other cohort by at least $3\varepsilon/4$.
Since $L_j=0$, endpoint exchanges show that the two regrets are at least
$$
\frac{3\varepsilon}{4}(U_j-\mathbb E_+A_j),
\qquad
\frac{3\varepsilon}{4}\mathbb E_-A_j.
$$
For example, in the positive instance, increasing cohort $j$ to its feasible maximum $U_j$ displaces impressions each worth at least $3\varepsilon/4$ less. In the negative instance, removing cohort $j$ is feasible and improves every removed impression by at least that amount.
The baseline probability of cohort $j$ is $1/2$. Thus Section 4 applies even though other baseline probabilities differ. Bid independence permits the same $e_j$ to be used after changing the values. Adding and comparing transcript expectations gives
$$
2r_N\ge
\frac{3\varepsilon}{4}U_j
\left(1-2\sqrt2\,\varepsilon\sqrt{e_j}\right).
$$
Set
$$
\varepsilon=\frac{16r_N}{U_j}.
$$
Because $r_N=o(N)$ and $U_j=u_jN$ with $u_j>0$, eventually $\varepsilon\le1/4$.
If
$$
e_j\le\frac1{32\varepsilon^2},
$$
both total-variation distances from the baseline are at most $1/4$. The last regret inequality would then give
$$
2r_N\ge\frac{3\varepsilon}{8}U_j=6r_N,
$$
a contradiction. Consequently,
$$
e_j>
\frac1{32\varepsilon^2}
=\frac{U_j^2}{8192r_N^2}.
$$
Return to the original gap instance with all values one. Its regret is exactly
$$
\delta\sum_{j\ne k}\mathbb E[A_j]
\ge\delta\sum_{j\ne k}e_j.
$$
Summing the sampling lower bounds and maximizing over $k\in S$ proves
$$
R_{M,\delta}(N)\ge
\frac{\delta N^2}{8192r_N^2}
\max_{k\in S}\sum_{j\ne k}u_j^2.
$$
Fix $\gamma\in[2/3,1)$ and put
$$
\alpha=2(1-\gamma),\qquad
n=\left\lceil N^\alpha\right\rceil.
$$
Use the reporter mechanism with
$$
E_\theta=\max(L_\theta,n,q).
$$
These counts are feasible for sufficiently large $N$, because $\alpha<1$ and there is positive linear slack after mandatory impressions.
The general regret bound gives
$$
R_M(N)=O(n+N/\sqrt n)=O(N^\gamma),
$$
where $n=O(N^\gamma)$ follows from $\gamma\ge2/3$.
Now consider any restricted gap instance and define
$$
V=\max_\theta v_\theta>0.
$$
The true best-to-runner-up score gap is $\delta V$.
Use the event
$$
\mathcal E=
\left\{
|\widehat p_\theta-p_\theta|\le\delta/3
\text{ for every }\theta
\right\}.
$$
On this event,
$$
|\widehat s_\theta-s_\theta|
\le v_\theta\delta/3
\le V\delta/3.
$$
Therefore, for every inferior cohort $j$,
$$
\widehat s_{\theta^*}-\widehat s_j
\ge
\delta V-\frac{2\delta V}{3}
=\frac{\delta V}{3}>0.
$$
Thus $\mathcal E$ identifies the best cohort uniformly over arbitrarily small permitted values. This is the required repair of the verifier’s objection.
The best cohort’s residual capacity fills all remaining rounds:
$$
C_{\theta^*}-E_{\theta^*}
\ge T-E_{\theta^*}
\ge T-\sum_\theta E_\theta.
$$
Hence exploitation uses only the best cohort on $\mathcal E$.
Every other cohort has $L_j=0$, so its exploration count is $\max(n,q)$. Hoeffding’s inequality and a union bound give
$$
\Pr(\mathcal E^c)
\le2\tau\exp(-2n\delta^2/9).
$$
Consequently,
$$
R_{M,\delta}(N)
\le
(\tau-1)\max(n,q)
+2\tau HN\exp(-2n\delta^2/9)
=
O(N^\alpha).
$$
Since $\delta>0$ and $\alpha>0$ are fixed, the exponential term is negligible compared with $N^\alpha$.
This proves the matching exponent
$$
\alpha=2(1-\gamma).
$$
The constructions use only observed clicks, fixed schedules, integer counters, and sorting of rational cohort scores. Payments require no computation beyond returning zero.
Each mechanism runs in polynomial time in the stated parameters: it reads bids of total length $L$, performs $HN\le qN$ rounds, and sorts $\tau$ scores with bit lengths polynomial in $L+\log(Nq)$. The integer exploration counts may be supplied as design parameters of $O(\log(Nq))$ bits. The displayed rational-power choices can also be computed by integer power comparisons and binary search.
For the $\kappa$-based construction, $\kappa$ is computable in polynomial time by sorting omittable cohorts by capacity and taking the largest initial segment whose capacity sum is at most $d$. No computation of the lower-bound quantity $F$ is required by a mechanism.
For smaller admissible $N$ where the chosen exploration counts are infeasible, use a fixed quota-respecting schedule with zero payments. This preserves membership in $\mathcal M_N$ and does not change any asymptotic statement.
The fixed-support exponents, the full parameter dependence in the mandatory-impression regime, and the gap-regret exponent tradeoff are proved. What remains unresolved is the matching coefficient dependence in the general $N^{2/3}$ regime: the lower factor $F^{1/3}$ need not match either proved upper factor.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial results: the fixed-support regret exponents, matching parameter dependence when every cohort has mandatory impressions, and the claimed worst-case/gap-regret exponent tradeoff. I found no false mathematical step in those arguments.
It does not fully resolve USER_TASK: the dependence on $\tau,\mu,q,H$ remains unmatched in the general regime with omittable cohorts. The prover explicitly acknowledges this limitation. The appropriate overall classification is partial.
The preliminary reductions are correct.
$$
\mathbb E[\text{total click value}]
=\sum_\theta v_\theta p_\theta\,\mathbb E[A_\theta]
$$
follows from online selection and independence of the current potential clicks from the preceding history. Adaptive selection does not invalidate this calculation.
$$
L_\theta\le A_\theta\le U_\theta
$$
and feasibility of both endpoints follow from the aggregate capacity of the other cohorts.
$$
w_\theta=\min(c_\theta,H,d,q-c_\theta)>0
$$
is correct. Positivity uses the positive masses of at least two cohorts.
$$
\sum_\theta\ell_\theta<H
$$
covers the empty, singleton, and larger cases for the set of positive mandatory counts. This provides the linear slack used in the later constructions.
No issue was found in this section.
The mechanism satisfies the stated incentive requirements, including heterogeneous individual-value profiles.
Each reporter receives exactly $q$ impressions in the fixed exploration schedule and none afterward. Consequently, her own bid cannot change her realized clicks or payment. Every other advertiser’s bid is unused, so it likewise cannot change that advertiser’s allocation or payment.
This proves weak dominant-strategy truthfulness for every complete realization. It does not require the advertiser to care about allocations to other members of her cohort.
Zero payments satisfy normalization. Exploration selections are independent of all bids, and exploitation clicks are ignored. Exploration separation therefore holds.
The requirements that reporters receive $q$ exploration impressions and that all exploration counts fit the capacities and horizon hold for sufficiently large $N$ in the constructions. The fallback mechanism handles smaller admissible $N$.
No issue was found here.
The exploration-forcing comparison is valid. Deficits can be filled by reducing coordinates above their exploration requirements because
$$
\sum_\theta E_\theta\le T.
$$
The number of moved impressions is at most
$$
\sum_\theta(E_\theta-L_\theta),
$$
and each move loses at most one unit of expected value.
Estimated-score optimality gives the stated comparison between the true and estimated residual optimizers. Their complete count vectors are feasible, so each coordinate difference is bounded by $w_\theta N$. The factor $v_\theta\le1$ is used correctly.
The exploration schedule is fixed. Its observations are therefore independent Bernoulli samples, and
$$
\mathbb E|\widehat p_\theta-p_\theta|
\le\frac1{2\sqrt{E_\theta}}
$$
is valid.
The second estimation bound is also correct. Feasible allocations have total used capacity $HN$ and total unused capacity $dN$, yielding
$$
\|x-x'\|_1\le2\min(H,d)N.
$$
Both upper bounds are justified as written.
This is the central structural lemma. Its erasure argument is sound under the exploration-separation definition in USER_TASK.
For a fixed complete realization, suppose the selected advertiser at a round varies with the bid profile. If flipping an advertiser’s click at that round changed a later allocation under a profile selecting that advertiser, exploration separation would force the selection at that round to be independent of the entire bid profile. That contradicts the assumed variation.
Profiles selecting another advertiser do not observe the flipped entry. Online selection also ensures that changing the current click row cannot change selection at the current round. Thus the row can be erased one entry at a time.
Chronological processing matters: at each stage, the processed table is itself a complete realization to which exploration separation applies. The preservation claim concerns all bid profiles simultaneously.
The resulting transcript has the asserted properties:
Hence
$$
S_j\le A_j
$$
holds pathwise under every bid profile.
The transcript is used as an information-theoretic object. The proof does not require an efficient procedure for checking constancy over all bid profiles.
The relative-entropy calculation has the required hypotheses: conditional sampling decisions are deterministic functions of the retained past, and retained clicks are fresh Bernoulli observations.
The computation
$$
\operatorname{kl}(1/2,1/2+\varepsilon)
=-\frac12\log(1-4\varepsilon^2)
\le4\varepsilon^2
$$
is valid for $|\varepsilon|\le1/4$.
Pinsker’s inequality then gives the stated total-variation bound. The expectation comparison uses a transcript function whose range has width $w_jN$, so its constant is correct.
The reverse-direction bound also follows from the stated Bernoulli $\chi^2$ calculation.
No issue was found in these information bounds.
The positive and negative single-cohort instances have benchmark allocations $U_j$ and $L_j$, respectively. Their regret formulas are correct because the remaining cohorts have equal scores.
The choice
$$
\varepsilon=\frac1{8\sqrt{e_j+1}}
$$
lies within the permitted probability range and makes the parenthesized factor at least $1/2$. Thus
$$
r\ge\frac{w_jN}{32\sqrt{e_j+1}}
$$
is justified.
Changing cohort $j$’s value while preserving the probability environment preserves the transcript law. This is the necessary justification for transferring the sampling bound across bid profiles.
The baseline sampling-cost bound has score difference $1/4$. In the uniform version, cohort $j$ has score at most $3/32$, whereas every other cohort has score at least $1/4$. The claimed lower improvement of $1/8$ per moved impression is therefore conservative and valid.
The resulting nonasymptotic inequalities follow correctly.
The consequences
$$
H>d,\qquad c_\theta<H,\qquad w_\theta=d
$$
follow from every cohort having capacity greater than $d$ and the existence of another such cohort.
For the upper bound, $E_\theta=L_\theta$ is feasible eventually. The Hoeffding union bound, the comparison with the definition of $\Lambda$, and the summation bound are correct. Tail integration gives the claimed universal multiple of $\Lambda/\sqrt N$.
For the lower bound:
$$ D(P_j\Vert P_0)\le\frac18\log K. $$
Independent decoder randomization does not invalidate the entropy argument.
Thus the claimed parameter dependence
$$
r^*(N)=\Theta(d\Lambda\sqrt N)
$$
is established.
The simultaneous-omission lower bound is correct. For $J\in\mathcal J$, the complement has enough capacity to fill the horizon, so the benchmark omits all cohorts in $J$. Summing the sampling constraints yields
$$
r^2(4r+\kappa)\ge\frac{FN^2}{1024}.
$$
For fixed parameters and sufficiently large $N$, this implies the stated universal lower coefficient.
The weighted exploration calculation is correct, including the coefficient
$$
\frac3{2^{4/3}}.
$$
Rounding contributes only the stated bounded per-cohort error.
The sharper forcing bound is justified by finiteness of the subset family and the positive minimum excess of any capacity sum strictly above $d$. It correctly includes subsets whose capacity sum equals $d$.
The exponential-moment calculation gives the stated maximum estimation error. Balancing it with $\kappa n$ gives the second upper coefficient.
The special-case identities for $\kappa$ and $F$ are also correct.
Major issue — unresolved part of the target: these lower and upper coefficients do not generally match. Therefore, the output does not determine the requested general dependence on $\tau,\mu,q,H$.
Minimum additional work required: establish matching parameter dependence in this regime, or explicitly retain the result as a partial answer. The output already takes the latter position; a complete answer requires additional mathematics.
The fixed-support exponent $2/3$ nevertheless follows from the proved bounds.
The gap class is nonempty exactly when $S$ is nonempty. The construction witnessing nonemptiness respects the probability range and uses rational values. The empty-class qualification is appropriate.
If $k\in S$, every other cohort is omittable. Thus a nonempty gap class necessarily lies in the $N^{2/3}$ worst-case regime.
The lower-bound construction correctly addresses value scaling:
The endpoint exchange bounds are valid. With
$$
\varepsilon=\frac{16r_N}{U_j},
$$
the probability perturbation is admissible eventually because $r_N=o(N)$. The contradiction under insufficient sampling gives the stated constant $8192$.
Returning to the original gap environment yields exactly the regret $\delta$ times the inferior-cohort impression count. Summation proves the displayed lower bound.
The upper construction uses the correct accuracy event. Its score errors scale with
$$
V=\max_\theta v_\theta,
$$
so identification remains valid even when all values are arbitrarily small. The best cohort has enough residual capacity, and the failure probability is bounded uniformly over the restricted class.
Consequently, the exponent tradeoff and exclusion of polylogarithmic gap regret under a fixed sublinear-power guarantee are established.
Given the integer exploration counts, the implementation uses polynomially many rounds, counters, rational comparisons, and sorting operations. The claimed computation of $\kappa$ by sorting capacities is correct. No computation of $F$ is needed.
Minor clarification: the blanket statement that all displayed power choices can be computed by integer power comparisons needs qualification for an arbitrary real $\gamma$. Section 8.3 does not specify an encoding or computability assumption for that exponent.
The minimum clarification is to distinguish the polynomial implementation with supplied integer exploration counts from a uniform algorithm generating those counts, and to specify the exponent representation if the latter is claimed. This does not affect the mathematical regret bounds or the existence of the mechanisms indexed by $N$.
The final mathematical assessment is therefore: the established subresults withstand verification, but the full parameter-sensitive question remains open.
⟨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.