Answer: No. The specified replication-limit mechanism can violate IC: a tagged VM can report UM, retain the same tier, and pay strictly less.
Theorem 4. — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMPR achieves an approximation ratio of at most $2$ on LSW, i.e., $Wel_{MPR}\ge \frac{1}{2} Wel_{OPT}$, where $Wel_{OPT} = max_{\Pi}Wel(\Pi)$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of types \(t=(v,\tau)\), rational masses \(\mu_t\), increasing tier click-through rates \(x_j\), and rational per-capita tier supplies \(s_j\) with \(\sum_j s_j<1\), take replications with \(N\mu_t\) advertisers and \(Ns_j\) slots. Does the MPR sequence yield a polynomial-time computable limit of type-tier assignments and prices, together with a tagged infinitesimal advertiser’s outcome under each report, that is incentive compatible for both classes, individually rational, robust, and achieves liquid social welfare at least half the feasible optimum?
A society is given by its support: a list of \(\tau\) types \(t=(v,c)\), where \(v\in\mathbb Q_{\ge0}\), \(c\in\{\mathrm{UM},\mathrm{VM}\}\), and each positive mass \(\mu_t\) is a binary rational; \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) tiers with rational CTRs \(0<x_1<\cdots<x_m\) and rational supplies \(s_j>0\), with \(\sum_j s_j<1\). Each advertiser receives at most one slot; nonallocation has CTR and price zero.
At tier \(j\) with per-click price \(p\), a UM maximizes \(x_j(v-p)\); a VM maximizes \(vx_j\) subject to \(p\le v\), preferring lower per-click price at equal value. Both value and class may be reported arbitrarily in \(\mathbb Q_{\ge0}\times\{\mathrm{UM},\mathrm{VM}\}\).
For every positive integer \(N\) making all counts integral, replicate type \(t\) into \(N\mu_t\) advertisers and tier \(j\) into \(Ns_j\) slots. Order slots bottom-up, write their CTRs as \(a_k\), and put \(a_0=p^{(0)}=0\). Value ties use fixed identifiers ordered lexicographically by support index and copy index, with smaller identifiers ranked higher.
Define MPR as follows: select the \(K=N\sum_j s_j\) highest-ranked advertisers, put the next advertiser at dummy slot zero, and initially place selected VMs in ascending rank in the lowest slots. The dummy advertiser participates in pricing according to its reported class.
For each occupied slot and the next vacant slot, quote \(p^{(k)}=\max\{[p^{(\ell)}a_\ell+w(a_k-a_\ell)]/a_k,z\}\), where \(\ell\) is the closest lower UM's slot, \(w\) its reported value, and \(z\) the closest lower VM's reported value; an absent class contributes zero.
Insert selected UMs in ascending rank: with \(q\) slots occupied, choose the lowest \(k\in\{1,\ldots,q+1\}\) maximizing \(a_k(v-p^{(k)})\), shift occupants at and above \(k\) up one slot, insert the UM, and recompute quotes above it. Winners pay their final slot quotes; losers pay zero.
The aggregate outcome is the empirical measure of \((t,j,p)\), giving each background advertiser mass \(1/N\); limits mean weak limits along all integral replications. A tagged infinitesimal advertiser is one additional advertiser, with a fixed identifier preceding all background identifiers under every report; its outcome under a report is the limit of its tier and per-click price in the corresponding augmented replication.
Polynomial-time computability means approximating aggregate measures in Wasserstein distance and tagged prices to \(2^{-b}\), while computing tagged tiers exactly, in time polynomial in \(m,\tau,L,b\); \(L\) includes the binary lengths of the society, tier data, and queried report.
IC means truthful reporting is preferred under the stated UM or VM preferences for every true tagged type and report; IR means truthful prices do not exceed value. Robustness means equality with the corresponding replication limits of VCG in all-UM societies and GSP in all-VM societies, using the same value-tie convention.
For feasible masses \(z_{tj}\ge0\), require \(\sum_j z_{tj}\le\mu_t\) and \(\sum_t z_{tj}\le s_j\); define \(W(z)=\sum_{t,j}v_t x_jz_{tj}\) and \(W^*=\max_z W(z)\).
Does MPR always have polynomial-time computable aggregate and tagged-report limits defining an IC, IR, robust mechanism with \(W\ge\tfrac12W^*\), or can this continuous factor-\(2\) guarantee fail?
Discrete MPR is IC, IR, robust, and achieves \(W\ge\tfrac12W^*\); discrete IC, IR, robust mechanisms cannot guarantee a factor below \(\tfrac54\). These results use distinct bidder values. [Source](https://arxiv.org/pdf/2211.16251)
No result settling this specified replication-limit problem was located.
1. Conclusion
The asserted guarantee is false: the specified replication limits can violate IC. The counterexample has two distinct tier CTRs and two distinct support values. Its aggregate welfare is optimal; the failure concerns the VM preference for lower prices at equal value.
2. Society and tiers
Take the all-VM society with support
\(t_L=(1,\mathrm{VM})\), \(t_H=(3,\mathrm{VM})\), and masses
\(\mu_L=7/8\), \(\mu_H=1/8\).
Let the tiers have
\(x_1=1\), \(x_2=2\), and supplies
\(s_1=s_2=1/4\).
These satisfy every stated hypothesis.
All integral replications are \(N=8r\), where \(r\) is a positive integer. Such a replication contains \(7r\) low-value advertisers, \(r\) high-value advertisers, and \(4r\) slots. Slots \(1,\ldots,2r\) have CTR \(1\); slots \(2r+1,\ldots,4r\) have CTR \(2\).
Add a tagged advertiser whose true type is \((4,\mathrm{VM})\). Compare truthful reporting with the report \((4,\mathrm{UM})\). Thus the deviation changes only the reported class, and the tagged advertiser has no value tie with any background advertiser.
3. Truthful tagged outcome
Under truthful reporting, the selected advertisers are:
The dummy advertiser is a VM of value \(1\).
All selected advertisers are VMs, so MPR places them bottom-up in increasing value order, respecting the prescribed identifiers within ties. The low-value advertisers occupy slots \(1,\ldots,3r-1\), the background high-value advertisers occupy slots \(3r,\ldots,4r-1\), and the tagged advertiser occupies slot \(4r\).
With no UM present, each quote equals the closest lower VM’s reported value. The advertiser immediately below the tagged advertiser has value \(3\). Consequently, for every \(r\), the truthful tagged outcome is
\((j,p)=(2,3)\).
Its replication limit therefore exists and equals \((2,3)\).
4. Outcome after reporting UM
Under the report \((4,\mathrm{UM})\), the selected set and dummy advertiser remain exactly the same.
Before inserting the tagged UM, MPR places the \(4r-1\) selected background VMs as follows: low-value advertisers occupy slots \(1,\ldots,3r-1\), and high-value advertisers occupy slots \(3r,\ldots,4r-1\).
Including the next vacant slot \(4r\), the initial quotes are
\(p^{(k)}=1\) for \(1\le k\le 3r\), and
\(p^{(k)}=3\) for \(3r+1\le k\le4r\).
Indeed, the first high-value VM faces a lower VM of value \(1\), whereas every subsequent quote faces a lower VM of value \(3\).
The reported UM value is \(4\). Its insertion utilities are therefore:
| Candidate slots | CTR | Quote | UM utility |
|---|---:|---:|---:|
| \(1,\ldots,2r\) | \(1\) | \(1\) | \(3\) |
| \(2r+1,\ldots,3r\) | \(2\) | \(1\) | \(6\) |
| \(3r+1,\ldots,4r\) | \(2\) | \(3\) | \(2\) |
The middle range is nonempty because \(2r+1\le3r\) for every \(r\ge1\). Thus MPR inserts the tagged UM at the lowest maximizing slot, namely \(2r+1\).
Its quote is \(1\). Insertion leaves every advertiser below that slot unchanged, and the specified recomputation affects only quotes above it. Hence its final outcome is
\((j,p)=(2,1)\)
for every integral replication.
The deviating tagged limit therefore also exists and equals \((2,1)\).
5. Strict violation of IC
Evaluate both outcomes using the tagged advertiser’s true VM preferences.
Both allocate tier \(2\), giving value
\(v x_2=4\cdot2=8\).
Both are affordable: the truthful price is \(3\le4\), and the deviating price is \(1\le4\).
At equal value, a VM strictly prefers the lower per-click price. Therefore the report \((4,\mathrm{UM})\) is strictly preferred to truthful reporting.
This proves that the specified replication-limit mechanism is not IC. The gain is exact in every integral replication; it does not arise from a limiting affordability issue.
6. Aggregate limit and welfare
For completeness, the unaugmented society also has an explicit aggregate limit.
In replication \(N=8r\), MPR selects \(3r\) low-value VMs and all \(r\) high-value VMs. The low-value winners occupy slots \(1,\ldots,3r\), all at price \(1\). The first high-value winner pays \(1\); the remaining \(r-1\) high-value winners pay \(3\).
Writing \(\delta_{(t,j,p)}\) for a unit point mass and using tier \(0\) for nonallocation, the aggregate limit is
\(\nu=\frac12\delta_{(t_L,0,0)}
+\frac14\delta_{(t_L,1,1)}
+\frac18\delta_{(t_L,2,1)}
+\frac18\delta_{(t_H,2,3)}\).
The only discrepancy between the finite empirical measure and this limit is mass \(1/N\) of high-value winners paying \(1\) instead of \(3\). Thus convergence holds along all integral replications, including in Wasserstein distance.
The limiting allocation has welfare
\(W=\frac14+2\cdot\frac18+3\cdot2\cdot\frac18=\frac54\).
To verify optimality, for any feasible allocation write \(z_{Lj}=z_{t_Lj}\) and \(z_{Hj}=z_{t_Hj}\). Then
\(W(z)=\sum_j x_j(z_{Lj}+z_{Hj})+2\sum_jx_jz_{Hj}\).
The supply constraints bound the first sum by
\(\sum_jx_js_j=3/4\).
Since \(x_j\le2\) and \(\sum_jz_{Hj}\le1/8\), the second term is at most \(1/2\).
Hence \(W(z)\le5/4\), attained by the limiting allocation. Therefore \(W=W^*=5/4\).
The counterexample consequently refutes the full asserted mechanism guarantee through IC failure, while attaining optimal welfare. Repeated values and equal CTRs within tiers are intrinsic to these replications, so the [source’s distinct-bidder-value premise](https://arxiv.org/pdf/2211.16251) cannot establish IC for them.
⟨structured verdict parsed — rendered above⟩
The counterexample is correct. It disproves the asserted conjunction of properties by exhibiting a strict IC violation. It does not show failure of the standalone welfare inequality \(W\ge \tfrac12W^*\), and it does not classify the general replication-limit problem’s computational complexity.
The verification below uses the intended bottom-up ordering: selected VMs are placed from lower to higher reported value, with the prescribed identifiers resolving ties.
All input conditions hold:
Integrality of the high-value count requires \(N/8\) to be an integer. Thus the admissible replications are exactly \(N=8r\), with \(r\ge1\). Their counts are correctly stated: \(7r\) low-value advertisers, \(r\) high-value advertisers, and \(4r\) slots, divided equally between the two tiers.
The tagged true type \((4,\mathrm{VM})\) and alternative report \((4,\mathrm{UM})\) are permitted. IC is required for every tagged true type, so the tag need not belong to the background support.
Finding: Correct.
There are \(4r\) available slots. Since the tag has reported value \(4\), selection includes the tag, all \(r\) value-\(3\) advertisers, and \(3r-1\) value-\(1\) advertisers. These counts sum to \(4r\).
There remain unselected value-\(1\) advertisers, so the dummy is indeed a value-\(1\) VM.
Under the bottom-up VM ordering, the occupied ranges are exactly:
With no lower UM, the UM contribution to each quote is zero. The closest lower VM beneath the tag has value \(3\), so its price is \(3\). Slot \(4r\) belongs to tier \(2\).
This remains valid at \(r=1\): the tag is in slot \(4\), immediately above the sole value-\(3\) background advertiser.
Finding: The truthful outcome is exactly \((2,3)\) for every admissible replication, so its limit exists.
Changing only the tag’s class leaves its value rank, selected set, and dummy unchanged.
The selected background VMs occupy slots \(1,\ldots,4r-1\), with the ranges stated in the output. The quote at slot \(1\) uses the value-\(1\) dummy. Subsequent quotes through slot \(3r\) also encounter a closest lower VM of value \(1\). In particular, slot \(3r\), occupied by the first value-\(3\) VM, has quote \(1\).
Quotes from slot \(3r+1\) through the next vacant slot \(4r\) encounter a lower VM of value \(3\). Hence:
\[ p^{(k)}=1\quad(1\le k\le3r),\qquad p^{(k)}=3\quad(3r+1\le k\le4r). \]
Finding: Correct, including the boundary slot \(3r\).
The insertion utilities for reported value \(4\) are correctly computed:
The maximizing range is nonempty because \(2r+1\le3r\) for every \(r\ge1\). The prescribed lowest-slot tie rule therefore selects slot \(2r+1\), in tier \(2\), at quote \(1\).
Insertion leaves the lower occupants unchanged. The rule recomputes quotes above the inserted UM, so its own quote remains \(1\). There are no further selected UMs to insert.
At \(r=1\), the maximizing range consists of slot \(3\) alone, so the same conclusion holds.
Finding: The deviating outcome is exactly \((2,1)\) for every admissible replication, so its limit exists.
Both outcomes are affordable for the true value-\(4\) VM, since \(3\le4\) and \(1\le4\). Both allocate tier \(2\), yielding the same VM value \(4\cdot2=8\).
The task expressly specifies a preference for lower per-click price at equal value. Consequently, the alternative report is strictly preferred.
This is a strict violation of the stated IC requirement. It persists unchanged in every admissible replication and therefore in the tagged limits.
Finding: The central counterexample is fully established.
In the unaugmented replication, selection includes \(3r\) low-value and \(r\) high-value VMs. Their allocation and prices are correctly described:
Dividing by \(N=8r\) gives precisely the stated limiting measure. The finite measure differs only by transferring mass \(1/N\) between the two high-value price atoms.
All these atoms lie in a fixed finite set. Thus this vanishing discrepancy establishes weak convergence and Wasserstein convergence under a fixed metric on the outcome space.
Finding: Correct.
The welfare calculation is correct:
\[ W=\frac14+2\cdot\frac18+3\cdot2\cdot\frac18=\frac54. \]
For any feasible allocation, the decomposition
\[ W(z)=\sum_j x_j(z_{Lj}+z_{Hj})+2\sum_jx_jz_{Hj} \]
is exact. The supply constraints bound the first term by \(3/4\). The high-type mass constraint and \(x_j\le2\) bound the second term by \(1/2\). Therefore \(W(z)\le5/4\).
The limiting allocation satisfies the feasibility constraints and attains this bound. Hence \(W=W^*=5/4\).
The output correctly distinguishes IC failure from welfare failure. Its counterexample suffices to negate the universal package requested in the task; no general complexity result or welfare counterexample follows from it.
Actionable feedback: No mathematical repair is needed. Preserve the distinction between refuting the full mechanism guarantee and refuting the standalone factor-\(2\) welfare bound.
⟨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.