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 \leq p < B$. The objective is to maximize either expected welfare $\mathbb{E}[S + (B-S) \mathbf{1}_{S \leq p < B}]$ or expected gains from trade $\mathbb{E}[(B-S) \mathbf{1}_{S \leq p < B}]$. We determine the optimal approximation ratio for several variants of the problem. When the agents' distributions are identical, we show that the optimal approximation ratio for welfare is $\frac{2+\sqrt{2}}{4}$. The optimal approximation for gains from trade in this case was known to be $1/2$; we show that this can be achieved even with just $1$ sample from the common distribution. We also show that a $3/4$-approximation to welfare can be achieved with $1$ sample from the common distribution. 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.