Source-linked AI summary
Sample Complexity of the Second-Best Bilateral Trade
Qiaoyun Shi, Shengxin Liu, Zongqi Wan
TL;DR
The paper asks how sample-based learning can approach the second-best GFT benchmark while preserving BIC, IIR, and ex-ante WBB, rather than learning only simple or fixed-price mechanisms. It develops upper and lower bounds for bounded-support and unbounded-MHR distributions, showing benchmark-sensitive multiplicative complexity and dependence on the mean-to-benchmark ratio. The results characterize sample requirements across three regimes.
Problem
Prior learning work focused on simple or fixed-price bilateral-trade mechanisms, leaving the sample complexity of learning BIC, IIR, and ex-ante WBB mechanisms near the second-best GFT benchmark open.
Method
The paper combines empirical mechanism learning with revenue margins, rare-block lower-bound constructions, and effective-window truncation for unbounded MHR distributions.
Results
The paper gives matching or nearly matching bounds in additive bounded-support, multiplicative bounded-support, and multiplicative unbounded-MHR regimes.
Takeaways & Limitations
Multiplicative learning in bilateral trade is benchmark-sensitive: when SB(D) is small, no sample bound independent of SB(D) is possible, while unbounded-MHR complexity depends on χµ(D).
Takeaways & Limitations
The unbounded-distribution result assumes MHR marginals and seller regularity, with finite means and positive densities on support interiors.
Abstract
from arXiv · showhide
We study the sample complexity of learning near-optimal bilateral trade mechanisms. Unlike previous work on learning simple or fixed-price bilateral-trade mechanisms, we focus on mechanisms satisfying Bayesian incentive compatibility (BIC), interim individual rationality (IIR), and ex-ante weak budget balance (WBB). In other words, our target is to design a sample-based mechanism that achieves the second-best gains-from-trade benchmark. We give matching or nearly matching upper and lower bounds in three regimes. For regular product distributions on $[0,h]^2$, additive $\varepsilon$-approximation has sample complexity $\widetildeΘ(h^2/\varepsilon^2)$. For multiplicative $(1-α)$-approximation under the same assumptions, we find that the sample complexity is $\widetildeΘ(h/(\mathrm{SB}(D)α^2))$, which is benchmark-sensitive with unavoidable dependence on the second-best gains from trade $\mathrm{SB}(D)$. We also investigate unbounded distributions under a monotone hazard rate (MHR) assumption. The sample complexity depends on the ratio $χ_μ(D)=μ(D)/\mathrm{SB}(D)$, where $μ(D)$ is the sum of the buyer's expected value and the seller's expected cost.
1 Introduction
The paper studies how many independent samples are needed to learn BIC, IIR, and ex-ante WBB bilateral-trade mechanisms approaching the second-best GFT benchmark. It gives matching or nearly matching bounds for additive and multiplicative approximation on bounded supports, plus multiplicative approximation for unbounded MHR distributions.
- Motivation: The learning target is a mechanism whose GFT is close to the second-best benchmark under the unknown buyer and seller distributions.The mechanism must satisfy BIC, IIR, and ex-ante WBB under the true distribution.
- Our Results and Techniques: The paper provides matching or nearly matching upper and lower bounds across three approximation regimes.These are additive bounded-support, multiplicative bounded-support, and multiplicative unbounded-MHR settings.
- Our Results and Techniques: Distribution-relative feasibility requires a positive empirical revenue margin because empirical WBB need not transfer directly to the true distribution.The analysis uses this margin to preserve feasibility after transfer while retaining near-optimality.
- Bounded support: additive approximation: The additive bounded-support learner optimizes an empirical canonical mechanism class with a revenue margin and uses a posted-spread comparator.This yields a mechanism with GFT(M; D) ≥ SB(D) −ε under the true distribution.
- Bounded support: multiplicative approximation: The multiplicative lower bound establishes unavoidable benchmark sensitivity by diluting a distinguishing instance block into a rare event.The resulting instances satisfy SB(D) = Θ(ph), while distinguishing the appropriate feasible mechanism incurs an additional 1/p sample cost.
- Unbounded support: multiplicative approximation: The unbounded-MHR learner identifies an effective bounded window, learns there, and extends the mechanism back to the original type space.Its sample complexity depends on the mean-to-benchmark ratio χµ(D).
2 Preliminaries
The preliminaries define bilateral-trade mechanisms, GFT and revenue, feasibility, and the first- and second-best benchmarks. They also introduce regularity, MHR distributions, threshold mechanisms, and the sample-based learning target.
- Mechanism model: A direct mechanism M = (q, xB, xS) specifies trade probability and buyer and seller payments.Its GFT is E_D[q(b, s)(b −s)], while revenue is E_D[xB(b, s) −xS(b, s)].
- Feasibility and benchmarks: A mechanism is feasible when it is BIC, IIR, and ex-ante WBB, with ex-ante WBB requiring nonnegative expected revenue.The second-best GFT is the largest GFT achievable by a feasible mechanism.
- Feasibility and benchmarks: The first-best GFT trades whenever buyer value exceeds seller cost, whereas the second-best benchmark is constrained by incentive and budget requirements.For regular product distributions, SB(D) ≤ FB(D) ≤ 3.15 SB(D).
- Distributional assumptions: Regularity requires monotone virtual value or virtual cost, while MHR requires a nondecreasing hazard rate.Virtual values support revenue bounds through virtual surplus.
- Threshold mechanisms: Randomized threshold mechanisms mix deterministic monotone-threshold mechanisms independently of reports, preserving BIC and IIR while making GFT and revenue affine.The learned mechanism is such a randomized threshold mechanism, constructed from samples.
- Learning model: The learner uses independent marginal samples and targets either additive GFT(M; D) ≥ SB(D) −ε or multiplicative GFT(M; D) ≥ (1 −α) SB(D).The output is required to be feasible under the true distribution with probability at least 1 −γ.
3 Additive Approximation with Bounded Support Distributions
The bounded-support additive learner uses a margin-constrained empirical LP and converts its solution into a randomized threshold mechanism that is feasible and near-optimal under the true distribution. Matching lower bounds show the required sample scale is quadratic in h/ε, up to logarithmic factors.
- Upper bound: A positive empirical revenue margin transfers feasibility from the empirical distribution to the unknown true distribution.The margin absorbs empirical-to-true revenue deviations while preserving near-optimality through a posted-spread comparator.
- Upper bound: The learner builds endpoint-augmented empirical grids and optimizes monotone allocation probabilities in a finite linear program.The LP uses O(m^2) allocation variables and constraints, then extends the solution to the original report space.
- Upper bound: At most two monotone integral grid allocations are mixed independently of reports to produce the returned randomized threshold mechanism.Each component receives threshold payments that preserve BIC and IIR on the grid and match the LP objective and revenue on empirical profiles.
- Upper bound: O(hδ) bounds the combined GFT and revenue change when marginal Kolmogorov distance is at most δ.This transfer lemma is applied after projecting canonical threshold mechanisms onto the empirical grid.
- Upper bound: GFT(c M; D) ≥ SB(D) − O(ε) − O(hδK), while choosing cK sufficiently small ensures true revenue is nonnegative and total GFT loss is at most ε.With the Dvoretzky–Kiefer–Wolfowitz bound, the resulting mechanism is BIC, IIR, and ex-ante WBB with GFT at least SB(D) − ε.
4 Multiplicative Approximation with Bounded Support Distributions
The bounded-support multiplicative learner localizes empirical optimization around an estimated second-best benchmark scale, yielding a near-optimal BIC, IIR, and ex-ante WBB mechanism. Matching lower bounds show that the dependence on h/SB(D) is unavoidable.
- Upper bound: The learner first estimates the benchmark scale, then optimizes a localized empirical LP with a positive revenue margin.The LP also excludes negative-surplus trades and caps empirical GFT at the estimated scale.
- Upper bound: The pilot estimate bV is a constant-factor estimate of SB(D) with high probability.
- Upper bound: The localized transfer lemma controls empirical-to-true error at the benchmark scale rather than the ambient scale h.This produces the sharper linear dependence on h/SB(D).
- Upper bound: With probability at least 1 −γ, Algorithm 2 returns a BIC, IIR, and ex-ante WBB mechanism satisfying GFT(M; D) ≥ (1 −α) SB(D).
- Lower bound: The lower bound embeds an additive hard pair in a probability-p active block, reducing one-sample information by p while preserving relative WBB separation.Choosing η = Θ(α) gives WBB separation Ω(αph), one-sample KL divergence O(pα^2), and SB(D±) = Θ(ph).
- Lower bound: Theorem 4.4 shows that any learner requires a benchmark-sensitive number of samples from each marginal in the worst case.The upper and lower bounds match up to a factor Λh(D)^2.
5 Multiplicative Approximation with Unbounded MHR Distributions
For unbounded MHR distributions, the paper estimates a finite cap, learns on a sentinel-truncated bounded instance, and extends the mechanism back to the original type space. The resulting guarantee depends on χ_μ(D), and the lower bound shows this benchmark sensitivity is intrinsic.
- Method: Under MHR marginals and seller regularity, the learner estimates a finite cap, truncates the instance, applies the bounded learner, and extends the mechanism.The cap/sentinel construction prevents high seller costs from being capped downward and creating artificial surplus.
- Method: The estimated mean and posted-spread revenue scales support a cap for which SB(D)/SB(D^bw) = O(χ_μ(D)L_μ,α(D)).
- Upper bound: With probability at least 1 −γ, the estimated-cap learner returns a BIC, IIR, and ex-ante WBB mechanism satisfying GFT(M; D) ≥ (1 −α) SB(D).
- Results: The MHR upper and lower bounds match up to polylogarithmic factors L_μ,α(D)^3L_χ(D).
- Lower bound: The lower-bound construction hides a bounded-support hard instance in a rare upper-tail region, so relative approximation requires discovering that informative region.The benchmark can remain small while the rare region carries the separation needed to identify a feasible mechanism.
- Lower bound: Theorem 5.3 establishes worst-case sample lower bounds for arbitrarily large benchmark ratios χ under the stated MHR assumptions.
A.2 Finite-grid implementation
The finite-grid construction converts monotone allocations into threshold mechanisms with canonical payments, preserving incentive properties and enabling comparisons between continuous and empirical distributions.
- Grid implementation: Every allocation monotone in the buyer report and seller report is implemented through threshold payments on the finite grid.
- Grid implementation: Integral monotone allocations become deterministic threshold rules, while fractional allocations are implemented as report-independent mixtures.
- Grid implementation: The stepwise extension preserves DSIC and ex-post IR, agrees with the grid allocation, and leaves expectations unchanged on grid-supported distributions.
- Threshold convention: Using the stated threshold convention, buyer thresholds use closed upper tails and seller thresholds use cumulative probabilities at the threshold.
- Distribution transfer: For bounded threshold mechanisms, replacing empirical marginals by true marginals changes the relevant quantities by O(hδ).The argument bounds each marginal replacement using bounded variation of monotone integrands.
- Empirical comparison: On empirical profiles, the finite-grid mechanism preserves GFT and weakly increases revenue relative to the original threshold mechanism.
B.3 Proof of Lemma 3.3
A posted-spread mechanism provides a revenue scale that is logarithmically related to the expected gains from trade on bounded support. This relation supplies the comparator used in the additive analysis.
- Posted-spread revenue: The maximum posted-spread revenue R is positive and at most the expected realized GFT W.
- Posted-spread revenue: The seller-side and buyer-side arguments each lower-bound posted-spread revenue through logarithmic factors involving h/R.
- Benchmark relation: The delegated-pricing ratio yields a lower bound relating R to FB(D) and SB(D) through 1 + log(h/SB(D)).
- Benchmark relation: A posted-spread mechanism with revenue at least R/2 also achieves GFT at least its revenue because trade occurs only when realized GFT dominates the price spread.
B.4 Proof of Theorem 3.4
The proof constructs an empirical mechanism that preserves near-second-best gains from trade and a target revenue margin, then transfers these guarantees to the true distribution while retaining BIC, IIR, and ex-ante WBB.
- An empirical-margin LP optimum can be implemented as a mixture of at most two deterministic threshold mechanisms with identical empirical GFT and revenue.
- The transfer mixture achieves revenue at least ρtar and GFT at least (1 −ω)G when its components satisfy the stated GFT and revenue bounds.
- The empirical mechanism achieves GFT at least SB(D) −O(ε) and revenue at least ρadd on the empirical product distribution.
- On the true distribution, its guarantees become GFT at least SB(D) −O(ε) −O(hδK) and revenue at least ρadd −O(hδK).
- Choosing ρadd and δK appropriately limits total GFT loss to ε and ensures nonnegative true revenue, while the resulting mechanism is BIC, IIR, and ex-ante WBB.
B.7 Proof of Theorem 3.7
The proof establishes regularity and MHR properties for the constructed distributions and derives uniform empirical-to-true expectation bounds for monotone functions used in the learner analysis.
- The constructed buyer marginal is regular because its inverse hazard rate is decreasing, while the seller marginal is uniform and therefore regular and MHR.
- The feasible mechanism classes achieving SB(Dθ) −ε under the two distributions are disjoint whenever ε < cηh.
- Uniform concentration over half-lines extends to every bounded monotone function through layer-cake representations and separate buyer- and seller-coordinate projections.
- The resulting bounds control the true, hybrid, and empirical expectations of functions monotone in buyers and sellers, enabling comparison of mechanism statistics under D and bD.
C.3 Proof of Theorem 4.3
The proof handles unbounded MHR distributions by trimming surplus, localizing the mechanism, solving a constrained empirical LP, and transferring its guarantees back to the true distribution.
- Surplus trimming removes trades with b < s without decreasing GFT or revenue while preserving the canonical threshold form.
- A posted-spread mechanism supplies positive revenue, allowing mixing to create a surplus-trimmed, localized feasible benchmark for the empirical LP.
- The localized empirical LP optimum can be implemented by the mechanism class used in the transfer lemma, with empirical revenue at least 4ρ and GFT capped by C0 bV.
- The transferred mechanism attains GFT at least (1 −α)SB(D) under the true distribution.
- Report-independent randomization preserves BIC and IIR, and the construction is ex-ante WBB under D.
C.4 Proof of Theorem 4.4
The proof embeds an additive hard pair into bounded-support distributions, establishes regularity and MHR, and combines cap selection with a bounded learner to transfer second-best performance.
- The embedded buyer support lies in [pR, 2R], while the seller support lies in [R, 2R].
- The buyer revenue curve is flat on the inactive branch and concave on the active branch, ensuring buyer regularity after the embedding.
- Inactive blocks have nonpositive realized and virtual surplus, so they cannot improve the benchmark or offset the cross-world WBB separation.
- The embedded pair preserves a cross-world WBB separation of Ω(pηR), while its feasible (1 −α)-optimal mechanism classes are disjoint.
- For MHR learning, Algorithm 3 estimates a cap, projects samples to the truncated instance, runs the bounded learner, and extends the output to the original instance.
- The truncation framework preserves a BIC, IIR, and ex-ante-WBB mechanism attaining at least VH = SB(DH).
D.2 Proof of Theorem 5.2
The proof combines cap selection with a bounded learner, then extends the learned mechanism while preserving BIC, IIR, and ex-ante WBB. The resulting sample complexity follows by combining the learner and cap-selection bounds with a union bound.
- Cap selection: The selected cap satisfies the bounded learner's hypothesis after splitting confidence between cap selection and learning.A constant-factor estimate of μ(D) supports the cap choice when Ccap is sufficiently large.
- Bounded learning: With accuracy α/2 and confidence γ/3, the bounded learner returns a mechanism for the capped distribution.
- Mechanism extension: The extended mechanism is BIC, IIR, and ex-ante WBB on D.
- Mechanism extension: GFT(c_M; D) ≥ GFT(N_b_w; D_b_w), so extension preserves at least the capped mechanism's gains from trade.
- Sample complexity: The final success probability is at least 1 − γ, and the cap-selection and bounded-learner sample complexities have the same order.This follows from substituting the bounds into Lemma D.7 and applying a union bound.
D.3 Proof of Theorem 5.3
The proof embeds an additive hard pair into MHR product distributions using a rare active block and an exponential-tail inactive branch. This preserves the relevant benchmark separation while relating the rare-block probability to χ_μ.
- Rare-block embedding: The construction replaces the inactive branch with an exponential-tail branch and shifts the active block by R log(1/p).
- Rare-block embedding: The two branches join smoothly at q = p because their values and derivatives agree there.
- MHR verification: The buyer and seller marginals are MHR, so D+ and D− satisfy Assumption 5.1.The inactive buyer branch has hazard rate 1/R, while the translated seller distribution has nondecreasing virtual cost.
- Benchmark preservation: Outside the active block, realized and virtual surplus are nonpositive, so the inactive region contributes neither to the benchmark nor to the separation.
- Benchmark preservation: The active-block GFT and virtual-surplus integrals are exactly p times those of the additive hard pair, enabling the same benchmark-scaling and cross-world-separation argument.
- Parameter calibration: The construction chooses p so that χ_μ(D_θ) = Θ(χ), completing the theorem.
- Lower-bound separation: Choosing η = Θ(α) makes the feasible (1 − α)-optimal classes disjoint, while the one-sample KL divergence is O(pα^2).