Answer: No mechanism satisfies the stated guarantees.
Theorem 6.3(a) — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateConsider a multi-parameter MAB domain with vj ≤1 and µj > 0 for every ad j. Then mechanism Mδ is stochastically truthful, for every δ ∈(0, 1). Consider σ-skewed problem instances, and assume maxj∈A0 vjµj > ǫ > 0. There exists δ ∈(0, 1) such that mechanism Mδ satisfies the following: (a) W(M) > W(RND) on all problem instances with at least two agents, as long as σ > 1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses \(\lambda_t\) over finitely many advertiser portfolio types \(t\), value vectors \(v_t\in[0,1]^m\), a horizon \(H\), and unknown but fixed positive CTR vectors \(\theta_t\), construct a finite-support policy and history-based payment rule with running time polynomial in \(m,\tau,H\), and the input bit length. The policy may use an individual’s report, the distribution of reports, and observed clicks; each individual deviation has zero mass and must still receive report-dependent treatment. Require stochastic truthfulness for every \(\theta\), total assignment mass at most one per stage, and per-capita welfare strictly above uniform allocation whenever \(M_2^2\ge\sigma M_1^2\) for some \(\sigma>1\) and \(\max_{t,j}v_{t,j}\theta_{t,j}>\epsilon>0\), where \(M_q=\left(\sum_t\lambda_t\frac{1}{m}\sum_{j=1}^m(v_{t,j}\theta_{t,j})^q\right)^{1/q}\).
Consider an atomless society of total mass \(1\). A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\lambda_t\) a binary rational; \(\tau\) is the support size, not the number of possible types.
Each type has a public portfolio of \(m\ge1\) distinct ads, private rational values \(v_t\in[0,1]^m\), and fixed CTRs \(\theta_t\in(0,1]^m\), unknown to both advertisers and mechanism. Portfolios belonging to different advertisers are disjoint. The horizon \(H\ge2\) and rational parameters \(\sigma>1\), \(\epsilon\in(0,1)\) are given.
Advertisers report their value vectors once. At each stage a policy chooses a distribution with finite support over feasible assignment plans: each individual receives at most one impression, and total assigned mass is at most \(1\); skips are allowed.
For each type, ad, and stage there is an independent Bernoulli click indicator with parameter \(\theta_{t,j}\), shared by individuals of that true type. An individual observes it only when assigned that ad; the mechanism observes it only through actual assignments. Reports do not change an individual's underlying CTR or click indicators. Unassigned clicks and counterfactual executions are unavailable.
The policy and final payment rule may depend on public portfolios, individual reports and observed histories, and the distribution of reports and observed histories. They must specify treatment for every report in \([0,1]^m\), including reports outside the population support.
Stochastic truthfulness means that, for every CTR vector and every fixed distribution of others' reports, truthful reporting maximizes each individual's expected total click value minus payment, over mechanism randomness and clicks. An individual deviation has zero mass, leaves aggregate distributions unchanged, and changes that individual's treatment according to the reported vector. Payments are signed monetary amounts with finite expectations and depend only on available observations.
At truthful reports, let \(W\) be expected total click value per capita and define \(M_q=\left(\sum_t\lambda_t\frac{1}{m}\sum_{j=1}^m(v_{t,j}\theta_{t,j})^q\right)^{1/q}\) for \(q\in\{1,2\}\). Require \(W>HM_1\), the welfare of uniform allocation, whenever \(M_2^2\ge\sigma M_1^2\) and \(\max_{t,j}v_{t,j}\theta_{t,j}>\epsilon\).
Is constructing a stochastically truthful mechanism with these guarantees possible in time polynomial in \(m,\tau,H,L\), or is this construction problem NP-hard? Here \(L\) is the binary input length; construction must give a finite description whose stage and payment evaluations also take polynomial time on rational reports.
For finitely many advertisers, at least two advertisers, bounded nonnegative values, positive CTRs, and a nonempty exploitation phase, a stochastically truthful mechanism strictly improves on uniform allocation under the corresponding skewness and positive-value conditions. [Discrete result](https://arxiv.org/pdf/1302.4138v2).
The source checks identified no result settling this precise atomless construction problem with finite-support policies.
Conclusion. The stated guarantees are impossible, even without truthfulness or computational restrictions. The obstruction persists for arbitrary portfolio size and strictly positive values.
An admissible counterexample. Fix any \(m\ge 2\), \(H\ge 2\), \(\sigma>1\), and \(\epsilon\in(0,1)\). Choose a positive dyadic rational \(p\) satisfying \(p\le 1/(4\sigma)\).
Consider two types, belonging to different advertisers with disjoint portfolios:
Both masses are positive binary rationals. All values and CTRs satisfy the prescribed bounds. Each portfolio contains \(m\) distinct ads.
This counterexample has polynomial encoding length: writing \(\sigma=a/b\) with positive integers \(a,b\), one can take \(p=2^{-k}\), where \(k\) is the binary length of \(a\), plus two.
Verification of the trigger conditions. Since every ad within a given type has the same value per impression,
\(M_1=p+(1-p)p=p(2-p)\),
and
\(M_2^2=p+(1-p)p^2\ge p\).
Consequently,
\(\sigma M_1^2=\sigma p^2(2-p)^2\le 4\sigma p^2\le p\le M_2^2\).
Also, \(\max_{t,j}v_{t,j}\theta_{t,j}=1>\epsilon\). Thus the required strict welfare improvement applies to this society.
A universal welfare upper bound. Here all click indicators equal one almost surely. Under the stated per-individual impression cap, each type-\(A\) individual can obtain at most value \(1\) in a stage, and each type-\(B\) individual can obtain at most value \(p\).
More explicitly, let \(a_{A,h}\) and \(a_{B,h}\) denote the masses receiving impressions at stage \(h\) in any realized execution. Feasibility gives \(a_{A,h}\le p\) and \(a_{B,h}\le 1-p\). Therefore realized stage welfare is at most
\(a_{A,h}+p\,a_{B,h}\le p+p(1-p)=M_1\).
Summing over stages and taking expectations yields \(W\le HM_1\). Uniform allocation attains this bound because it gives every individual an impression, and every ad in that individual’s portfolio has the same value.
The required inequality \(W>HM_1\) is therefore impossible. Payments, randomization, observed histories, and knowledge of the CTRs cannot change this welfare bound.
Why global skewness does not suffice. This is not merely the special case \(m=1\): the construction works for every \(m\ge 2\), with two advertisers and strictly positive values. Its skewness arises between types, while uniform allocation already maximizes welfare within each type.
To see the distinction algebraically, write \(x_{t,j}=v_{t,j}\theta_{t,j}\) and \(\mu_t=m^{-1}\sum_j x_{t,j}\). Expanding the squares gives
\(M_2^2-M_1^2=\sum_t\lambda_t m^{-1}\sum_j(x_{t,j}-\mu_t)^2+\sum_t\lambda_t(\mu_t-M_1)^2\).
In this example, the first term is zero; the second supplies all the skewness. The per-individual cap prevents that between-type variation from producing additional welfare.
The cited discrete rule instead selects one ad among all advertisers’ ads in each round, so its resource constraint differs from the one here. [Discrete source, Section 6.1](https://arxiv.org/pdf/1302.4138v2).
Accordingly, the construction problem as stated is infeasible; polynomial-time construction versus NP-hardness is not the applicable dichotomy.
⟨structured verdict parsed — rendered above⟩
The prover’s impossibility claim is correct under the intended interpretation that an individual’s click values concern ads in that individual’s portfolio. The counterexample satisfies the trigger conditions, while uniform allocation already attains the maximum feasible welfare. No major or minor issues were found.
The task requires a mechanism satisfying the welfare guarantee for every admissible society and CTR vector. Consequently, one admissible society on which the required improvement is infeasible suffices to disprove existence. No truthfulness or computational argument is needed once this obstruction is established.
The proposed society has support size \(\tau=2\), positive masses summing to \(1\), and disjoint portfolios belonging to two advertisers. Its values lie in \([0,1]\), and its CTRs equal \(1\), which is permitted by the domain \((0,1]\). Deterministic Bernoulli variables with parameter \(1\) also satisfy the stipulated independence requirement.
The choice \(0<p\le 1/(4\sigma)\), with \(\sigma>1\), ensures \(p<1\), so both masses are positive. The example applies for every stated \(m\ge2\) and \(H\ge2\). Failure on these permitted inputs already refutes universal feasibility.
The explicit dyadic choice is valid. If \(\sigma=a/b>1\), with positive integers \(a,b\), and \(\ell\) is the binary length of \(a\), then the proposed \(k=\ell+2\) gives
\[ p=2^{-(\ell+2)}<\frac{1}{4a}\le\frac{b}{4a}=\frac{1}{4\sigma}. \]
Both \(p\) and \(1-p\) have binary rational descriptions of length proportional to \(k\). Repeating the specified values over the portfolios gives a description polynomial in the parameters claimed by the prover.
This encoding observation is correct, although the impossibility result does not depend on a polynomial encoding bound.
Because each type’s ads have identical value and CTR, the factor \(1/m\) cancels within each type. The displayed moment calculations are correct:
\[ M_1=p+(1-p)p=p(2-p), \]
\[ M_2^2=p+(1-p)p^2\ge p. \]
Every step in the bound
\[ \sigma M_1^2 =\sigma p^2(2-p)^2 \le4\sigma p^2 \le p \le M_2^2 \]
is justified: \(0<p<1\) gives \((2-p)^2\le4\), and \(p\le1/(4\sigma)\) gives \(4\sigma p^2\le p\).
The maximum value–CTR product is \(1\), so the second trigger holds for every allowed \(\epsilon\in(0,1)\). Thus the required strict improvement genuinely applies; the example does not exploit a vacuous trigger.
All clicks occur almost surely. The per-individual impression constraint therefore limits each type-\(A\) individual’s stage value to \(1\) and each type-\(B\) individual’s stage value to \(p\).
For every realized feasible assignment, the masses receiving impressions satisfy
\[ 0\le a_{A,h}\le p,\qquad 0\le a_{B,h}\le1-p. \]
Hence the prover’s bound
\[ a_{A,h}+p\,a_{B,h} \le p+p(1-p) =M_1 \]
is valid pointwise. Summing over the horizon and taking expectations yields \(W\le HM_1\), including for adaptive and randomized policies.
Uniform allocation attains this bound because every assigned portfolio ad has the same value within its type. Payments do not enter the task’s definition of welfare, so signed payments cannot invalidate the upper bound.
This contradicts the required \(W>HM_1\) on an instance satisfying both triggers.
The variance decomposition is correct. With \(x_{t,j}=v_{t,j}\theta_{t,j}\) and \(\mu_t=m^{-1}\sum_jx_{t,j}\), expansion gives exactly the two displayed variance terms. Within-type variation vanishes in this example, leaving only between-type variation.
The source comparison is also accurate: the discrete paper specifies that each round either skips or displays one ad, and Section 6.1 analyzes allocation across advertisers’ ads. This differs from the atomless task’s per-individual impression constraint. [Discrete source](https://arxiv.org/pdf/1302.4138v2). The impossibility argument itself does not rely on importing any theorem from that source.
The output resolves the task by establishing infeasibility. It does not establish NP-hardness, nor does it need to: the requested guarantees cannot be met even with unrestricted computation.
No additional clarification or repair is needed for the mathematical argument.
⟨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.