Answer: Unattainable: pure-RB replicated-market consistency with the prescribed exact tie rule contradicts tagged-advertiser truthfulness, already for $K=2$ and $\tau=3$, for every rational $\gamma>1$.
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateBIN-Pri achieves an approximation ratio of no more than 3 2 on LSW, i.e., 𝑊𝑒𝑙𝑜𝑢𝑟≥2 3𝑊𝑒𝑙𝑂𝑃𝑇, where 𝑊𝑒𝑙𝑜𝑢𝑟 denotes the LSW of our mechanism, and 𝑊𝑒𝑙𝑂𝑃𝑇= 𝑚𝑎𝑥Π𝑊𝑒𝑙(Π).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational \(\gamma>1\), ordered slot click-through rates \(x_k\), per-capita capacities \(q_k\) with \(\sum_k q_k\leq 1\), and a finite-support rational distribution \(\mu\) over types \(\theta=(v,\tau)\), does there exist an anonymous direct mechanism computable in time polynomial in \(K\), \(\tau_0=|\operatorname{supp}(\mu)|\), and the input bit length? It must assign advertisers integral slots, possibly by lottery, be truthful and individually rational for a tagged advertiser against fixed background \(\mu\), enforce \(p\leq v\) for every realized payment \(p\) to an \(\mathrm{RB}\), and agree with the replicated-market limits of VCG and Cavallo’s mechanism in the respective pure-class cases. The mechanism must guarantee expected liquid social welfare at least \(\frac{2}{3}\) of the feasible assignment optimum.
A society is given by its support: \(\tau\) types \(\theta=(v,c)\), with positive binary-rational masses \(\mu_\theta\) summing to \(1\); \(\tau\) is the support size, not the number of possible types. Values \(v>0\) are rational and classes \(c\in\{\mathrm{UM},\mathrm{RB}\}\) are private. Public rational data are \(\gamma>1\), \(K\geq1\) slot categories with \(0<x_1\leq\cdots\leq x_K\), and capacities \(q_k>0\) satisfying \(\sum_kq_k\leq1\); write \(m=K\) and let \(L\) denote total input bit length.
An anonymous direct mechanism gives each reported type a lottery over an integral category \(k\in\{0,\ldots,K\}\) and a nonnegative per-click payment \(p\); \(k=0\) means no assignment, with \(x_0=p=0\). Each realization assigns at most \(q_k\) mass to category \(k\), and each advertiser receives at most one category.
Realized UM utility is \((v-p)x_k\). Realized RB utility is \((\gamma v-p)x_k\) when \(p\leq v\), and \(-\infty\) otherwise. Against every fixed background \(\mu\), every tagged advertiser must maximize expected utility by reporting both coordinates truthfully, allowing any positive rational value and either class as a report; truthful payments must satisfy \(p\leq v\) almost surely for both classes.
For truthful assignment probabilities \(a_{\theta k}\), liquid social welfare is \(W=\sum_{\theta,k\geq1}\mu_\theta v_\theta x_k a_{\theta k}\). Define \(\mathrm{OPT}\) as its maximum over \(a_{\theta k}\geq0\) with \(\sum_{k\geq1}a_{\theta k}\leq1\) and \(\sum_\theta\mu_\theta a_{\theta k}\leq q_k\).
Consistency requires the truthful joint category/payment law for each supported type in a pure-class society to equal its replicated-market limit: for integers \(N\) clearing all denominators, use \(N\mu_\theta\) advertisers of each type and \(Nq_k\) individual slots of CTR \(x_k\), then let \(N\to\infty\). Break equal-value ties by uniformly random, report-independent priorities, and identify replicated slots with their categories; if necessary add one zero-valued dummy advertiser to ensure a loser exists.
In the pure-UM replicas use VCG. In the pure-RB replicas assign the highest values to the highest CTRs; listing occupied slots bottom-up as \(j=1,\ldots,J\), with CTRs \(X_j\), assigned values \(b_j\), highest losing value \(b_0\), and \(X_0=P_0=0\), charge \(P_j=\min\{b_{j-1},[P_{j-1}X_{j-1}+\gamma b_{j-1}(X_j-X_{j-1})]/X_j\}\).
Does there exist a single anonymous direct mechanism satisfying these requirements for every such input, computing exact finite rational outcome lotteries in time polynomial in \(m=K\), \(\tau\), and \(L\) (including a tagged report's encoding), and guaranteeing \(W\geq\tfrac23\mathrm{OPT}\), or is this approximation guarantee unattainable under these requirements?
For finite advertisers, BIN-Pri is truthful and consistent and guarantees liquid social welfare at least \(\tfrac23\) of the assignment optimum. [Tang et al., AAMAS 2024](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p1818.pdf)
No result settling this precise distributional, tagged-advertiser approximation question was located in the literature search.
The guarantee is unattainable under the stated requirements. In fact, pure-RB consistency and tagged-advertiser truthfulness are already incompatible. This holds for every rational $\gamma>1$, with two categories and three supported types.
The obstruction uses the prescribed treatment of exact equal-value ties.
Fix any rational $\gamma>1$. Set
$$
x_1=\frac{\gamma-1}{\gamma},
\qquad x_2=1,
\qquad q_1=\frac14,
\qquad q_2=\frac12.
$$
These data satisfy $0<x_1<x_2$ and $q_1+q_2=\frac34\leq1$.
Take the pure-RB society
$$
\mu_{(1/2,\mathrm{RB})}=\frac14,
\qquad
\mu_{(1,\mathrm{RB})}=\frac12,
\qquad
\mu_{(2,\mathrm{RB})}=\frac14.
$$
All masses are positive binary rationals, and the support size is $\tau=3$.
For this fixed background $\mu$, write $D_\mu(r)$ for the joint category/payment law received by a tagged advertiser reporting type $r$. Since the mechanism is anonymous and direct, this law depends on the report and background, rather than on the advertiser’s unobserved true type.
Let $N=4t$ be any admissible replication size, with $t$ a positive integer. The replica contains:
The prescribed value ordering makes all value-$\frac12$ advertisers losers. The category-$1$ slots receive $t$ value-$1$ advertisers. The category-$2$ slots receive the other $t$ value-$1$ advertisers and all $t$ value-$2$ advertisers.
Uniform, report-independent priorities among the $2t$ value-$1$ advertisers therefore give each such advertiser probability $\frac12$ of receiving each category. Every value-$2$ advertiser receives category $2$.
We now compute the payments using precisely the recurrence in the question.
The highest losing value is $b_0=\frac12$. For the bottom occupied slot, the recurrence gives
$$
P_1
=
\min\left\{
\frac12,
\frac{\gamma(\frac12)x_1}{x_1}
\right\}
=
\frac12.
$$
Within category $1$, consecutive CTRs are equal. Every subsequent predecessor has value $1$, so, inductively,
$$
P_j=\min\{1,P_{j-1}\}=\frac12.
$$
Thus every category-$1$ payment is $\frac12$.
The predecessor of the first category-$2$ slot has value $1$, CTR $x_1$, and payment $\frac12$. Since $x_2=1$, the payment for this first upper slot is
$$
\begin{aligned}
P_{t+1}
&=
\min\left\{
1,\frac12x_1+\gamma(1-x_1)
\right\}\\
&=
\min\left\{
1,\frac{\gamma-1}{2\gamma}+1
\right\}\\
&=1.
\end{aligned}
$$
All subsequent category-$2$ slots have the same CTR, and their predecessors have values at least $1$. Consequently, induction gives
$$
P_j=\min\{b_{j-1},P_{j-1}\}=1
\qquad
\text{for }j=t+2,\ldots,3t.
$$
The resulting category/payment laws are therefore exactly the same for every admissible replication size. In particular, their replicated-market limits exist and equal these laws.
Consistency forces
$$
D_\mu((1,\mathrm{RB}))
=
\begin{cases}
(k,p)=(1,\frac12),&\text{with probability }\frac12,\\
(k,p)=(2,1),&\text{with probability }\frac12,
\end{cases}
$$
and
$$
D_\mu((2,\mathrm{RB}))
=
(k,p)=(2,1)
\qquad\text{with probability }1.
$$
Consider a tagged advertiser whose true type is $(1,\mathrm{RB})$.
Both truthful payment outcomes satisfy $p\leq1$. Its expected truthful utility is therefore
$$
\begin{aligned}
U_{\mathrm{truth}}
&=
\frac12\left(\gamma-\frac12\right)x_1
+\frac12(\gamma-1)x_2\\
&=
\frac12\left(\gamma-\frac12\right)
\frac{\gamma-1}{\gamma}
+\frac12(\gamma-1)\\
&=
(\gamma-1)-\frac{\gamma-1}{4\gamma}.
\end{aligned}
$$
Now let this advertiser report $(2,\mathrm{RB})$, keeping the background $\mu$ fixed as required by tagged-advertiser truthfulness. Anonymity and directness imply that it receives $D_\mu((2,\mathrm{RB}))$: category $2$ at payment $1$, with probability $1$.
This payment is feasible for its true value $1$, because the RB payment constraint allows equality. Its deviation utility is
$$
U_{\mathrm{dev}}=(\gamma\cdot1-1)x_2=\gamma-1.
$$
Hence
$$
U_{\mathrm{dev}}-U_{\mathrm{truth}}
=
\frac{\gamma-1}{4\gamma}
>
0.
$$
This contradicts truthful reporting against the fixed background $\mu$.
The deviation uses another supported report, so specifying outcomes for unsupported reports cannot repair the contradiction.
The contradiction uses only anonymity, directness, tagged-advertiser truthfulness, and the stipulated pure-RB consistency law. Thus no mechanism satisfies all the requirements, regardless of its running time or welfare guarantee. In particular, the requested $\frac23$ guarantee is unattainable.
The cited paper’s preliminaries assume distinct bidder values and describe an $\epsilon$ perturbation for ties; see page 1820, footnote 1. That convention does not establish truthfulness for the exact equal-value, uniformly randomized replica laws prescribed here. [Tang et al., AAMAS 2024](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p1818.pdf)
The binding payment $p=v$ is decisive: the upper-category outcome remains feasible for the tied lower-value advertiser, who strictly prefers it to the required lottery.
⟨structured verdict parsed — rendered above⟩
The prover’s impossibility argument is correct and resolves the requested existence question. No mathematical gaps or false steps were found.
The prover fixes an arbitrary rational $\gamma>1$ and constructs an input with $K=2$ and $\tau=3$. Its parameters satisfy all stated restrictions:
$$ 0<\frac{\gamma-1}{\gamma}<1, \qquad q_1+q_2=\frac34\leq1. $$
The three values are positive rationals, and the positive binary-rational masses sum to $1$. The society is pure RB, so the prescribed pure-RB consistency requirement applies.
An impossibility on this admissible family suffices to rule out a mechanism satisfying the requirements for every input. No welfare calculation or running-time lower bound is needed if truthfulness and consistency already contradict each other.
For an admissible replication size $N=4t$, the stated advertiser and slot counts are correct. There are $3t$ occupied slots and $4t$ advertisers, so losers already exist and no dummy is needed.
Sorting by value places all $t$ value-$2$ advertisers in category $2$. The $2t$ value-$1$ advertisers occupy the remaining $t$ category-$2$ slots and all $t$ category-$1$ slots. All value-$\frac12$ advertisers lose.
Uniform priorities among the $2t$ tied value-$1$ advertisers therefore give each probability $\frac12$ of receiving each category. This conclusion concerns individual marginal laws, precisely what consistency requires; independence between advertisers’ assignments is unnecessary.
The highest losing value is correctly identified as $b_0=\frac12$. The bottom-slot calculation gives
$$ P_1=\min\left\{\frac12,\frac{\gamma}{2}\right\}=\frac12. $$
Within category $1$, equal consecutive CTRs reduce the recurrence to
$$ P_j=\min\{b_{j-1},P_{j-1}\}. $$
The relevant predecessors have value $1$, so all category-$1$ payments remain $\frac12$. For $t=1$, this induction range is empty and the initial calculation suffices.
At the category boundary, the predecessor has value $1$, payment $\frac12$, and CTR $x_1$. The displayed computation is correct:
$$ \frac12x_1+\gamma(1-x_1) = \frac{\gamma-1}{2\gamma}+1>1. $$
Thus the first category-$2$ payment is $1$. Every subsequent predecessor has value at least $1$, and equal CTRs preserve payment $1$.
Consequently, both category/payment laws used by the prover are exact at every admissible replication size. Their limits require no additional convergence argument.
Both reports $(1,\mathrm{RB})$ and $(2,\mathrm{RB})$ are supported in the same pure-RB background $\mu$. Consistency therefore fixes both truthful marginal laws exactly as stated.
Under the task’s fixed-background tagged-advertiser requirement, a direct mechanism cannot distinguish a true value-$1$ advertiser reporting $(2,\mathrm{RB})$ from a truthful tagged advertiser making that same report against $\mu$. The deviation consequently receives the law $D_\mu((2,\mathrm{RB}))$.
This step correctly uses the task’s distributional formulation. It does not assume that a finite advertiser’s deviation leaves a finite reported profile unchanged.
Both truthful payments are feasible for true value $1$. The truthful expected utility simplifies correctly to
$$ U_{\mathrm{truth}} = (\gamma-1)-\frac{\gamma-1}{4\gamma}. $$
The deviation yields category $2$ at payment $1$ with certainty. Equality is allowed in the true RB affordability condition $p\leq v$, so its utility is finite and equals
$$ U_{\mathrm{dev}}=\gamma-1. $$
The resulting gain is
$$ U_{\mathrm{dev}}-U_{\mathrm{truth}} = \frac{\gamma-1}{4\gamma}>0. $$
Strict positivity holds throughout the stated domain $\gamma>1$. This directly violates tagged-advertiser truthfulness. A deviation changing only the value coordinate is sufficient, since truthfulness must cover every allowed report.
The ancillary citation is accurate: the paper assumes distinct bidder values in its preliminaries, and page 1820, footnote 1 describes breaking ties through non-manipulable IDs and a positive $\epsilon$ subtraction from values. [Tang et al., AAMAS 2024](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p1818.pdf)
That convention differs from the task’s exact equal-value replica recurrence with uniformly randomized priorities. The prover correctly avoids treating the cited finite-market result as establishing truthfulness for the required limit laws. Its contradiction is self-contained and does not depend on that literature comparison.
The output establishes incompatibility of two required properties, and hence unattainability of the requested $\frac23$ guarantee. There are no blocking issues and no additional clarification is required.
This is a mechanism-existence impossibility result, rather than a polynomial-time algorithm or a computational hardness classification. Accordingly, the requested complexity-status field is marked unresolved under its explicit rule for answers that do not classify complexity.
⟨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.