Fixed-Price Approximations in Bilateral Trade

Abstract

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\le p\le B$. The objective is to maximize either expected welfare $\mathbb{E}[S+(B-S)1_{S\le p\le B}]$ or expected gains from trade $\mathbb{E}[(B-S)1_{S\le p\le 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 $\frac{2+\sqrt{2}}{4}$. 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.

arXiv commentTo appear in SODA'22