A theoretical preprint asks how many samples are needed to learn a bilateral-trade mechanism that comes close to the second-best benchmark while meeting the model's incentive, rationality and budget-balance constraints. The answer changes with the guarantee being sought and the assumptions placed on buyer values and seller costs. Across three regimes, the paper reports matching or nearly matching upper and lower sample-complexity bounds.
The document is an arXiv version 1 preprint in cs.GT dated 26 Aug 2026.
The learner starts with two separate distributions
The model uses independent samples from the separate buyer-value and seller-cost distributions, known in the paper as marginals. From those samples, the learner constructs a trading rule and compares its gains from trade, or GFT, with SB(D), the paper's second-best benchmark. The mechanism must meet the stated incentive, rationality and budget-balance conditions.
An absolute target brings a quadratic sample scale
For regular product distributions on [0,h]², the additive target is an absolute one: the learned mechanism must deliver GFT of at least SB(D)−ε. The upper bound gives that guarantee with a per-marginal sample scale of h²/ε², up to logarithmic factors. In plain terms, the dependence is quadratic in the support scale h and in the inverse error tolerance 1/ε.
The lower bound lands on the same quadratic scale. Uniform additive learning over regular product distributions on [0,h]² requires Ω(h²/ε²) samples from each marginal in the worst case. A learner meant to succeed across the full class therefore cannot generally promise a smaller order of growth. Because the upper and lower results agree apart from logarithmic factors, the quadratic dependence is presented as a feature of the learning problem, not merely of one algorithm.
The upper-bound method optimizes an empirical class of canonical mechanisms with a positive revenue margin and uses a posted-spread comparator to provide revenue slack. That slack is part of the construction used to transfer the empirical solution into a mechanism that meets the stated incentive, rationality and budget-balance constraints.
A percentage guarantee depends on the benchmark
The bounded-support multiplicative result uses a percentage target. Rather than allowing an absolute error ε, the learner seeks GFT of at least (1−α)SB(D), with high probability. Its per-marginal sample scale is essentially h/[SB(D)α²], plus logarithmic factors. Because the benchmark is in the denominator, a smaller SB(D) makes a fixed-percentage guarantee more demanding, and tighter relative accuracy raises the cost through the inverse-square α² term.
The corresponding lower bound is Ω(h/[SB(D)α²]) samples from each marginal in the worst case for uniformly successful learners over regular bounded product distributions. The hard instances use rare informative blocks: outside the block, two candidate distributions are nearly indistinguishable, while their weak-budget-balance separation remains concentrated in the rare region. The construction makes the benchmark-sensitive sample scale a worst-case feature of the distribution class.
A suitable localized linear-program optimum can be implemented as a mixture of at most three deterministic threshold mechanisms. The learner first uses a pilot estimate of the benchmark to localize the optimization, while retaining canonical payments and a positive revenue margin.
Unbounded values add a tail-handling step
When support is unbounded, the MHR method selects a cap and applies sentinel truncation to reduce the problem to a bounded instance without artificial trades in the tail. Under the paper's stated MHR and seller-regularity assumptions, the estimated-cap learner achieves a high-probability (1−α)-approximation. Its per-marginal sample scale is χµ(D)Lµ,α(D)³/α², up to logarithmic factors.
For constructed large-ratio MHR instances, the lower bound is Ω(χµ(D)/[Lχ(D)α²]) samples per marginal. The upper and lower results share the same benchmark-sensitive character, but the paper says they match only up to polylogarithmic factors. As in the bounded multiplicative case, the lower-bound construction places the decisive distinction in a rare region that carries the relevant weak-budget-balance separation while revealing little information in each sample.
A map of worst-case sample difficulty
Together, the results give a theoretical map of worst-case sample difficulty. The bounded additive task has the quadratic h²/ε² scale; bounded multiplicative learning depends essentially on h/[SB(D)α²]; and the unbounded MHR task depends on χµ(D), with logarithmic or polylogarithmic overheads in the stated bounds. The paper therefore does not establish a multiplicative guarantee independent of SB(D) or χµ(D).
The boundaries are explicit. The bounded results apply to regular product distributions on [0,h]², while the unbounded result relies on the stated MHR setting and seller regularity. The lower bounds are worst-case statements for those classes, and the MHR upper and lower bounds still differ by polylogarithmic factors.
Paper data and sources
Original title: Sample Complexity of the Second-Best Bilateral Trade
Authors: Qiaoyun Shi, Shengxin Liu, Zongqi Wan
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text