Fixed-Price Approximations in Bilateral Trade

We consider the bilateral trade problem, in which two agents trade a single indivisible item. It is known that the only dominant-strategy truthful mechanism is the fixed-price mechanism: given commonly known distributions of the buyer's value B and the seller's value S, a price p is offered to both agents and trade occurs if S ≤ p ≤ B. The objective is to maximize either expected welfare mathbbE[S + (B-S) 1S ≤ p ≤ B] or expected gains from trade mathbbE[(B-S) 1S ≤ p ≤ B]. We improve the approximation ratios for several welfare maximization variants of this problem. When the agents' distributions are identical, we show that the optimal approximation ratio for welfare is frac2+√24. With just one prior sample from the common distribution, we show that a 3/4-approximation to welfare is achievable. When agents' distributions are not required to be identical, we show that a previously best-known (1-1/e)-approximation can be strictly improved, but 1-1/e is optimal if only the seller's distribution is known.