The Exact Welfare Guarantee of Fixed-Price Bilateral Trade

Abstract

A seller and a buyer with independent private values can trade only at a posted price. We determine the worst case of this mechanism exactly: the best posted price always guarantees a ${\beta }_{\ast }=0.738024\dots$ fraction of first-best welfare, where ${\beta }_{\ast }$ is given in closed form by the root of an explicit equation, the worst-case buyer is unique up to scaling, and the worst case is never attained. This closes the gap $[0.7292,0.73805]$ left by work from SODA 2016 through two STOC 2023 papers and AAAI 2026. The proof is an explicit certificate of optimality: after one change of variables, the gap between the optimum and the value of any buyer is a sum of nonnegative integrals, as in a linear-programming dual, and equality identifies the worst-case shape. The certificate also gives the complete tradeoff between gains from trade and the seller's initial welfare: when first-best gains from trade are a fraction $\kappa$ of initial seller welfare, the exact worst-case fraction $\rho (\kappa )$ of gains obtained by the best price satisfies $\rho (\kappa )\sim 2/\log (1/\kappa )$ as $\kappa \to 0$. The worst-case buyer's survival function has two constant segments joined by an explicit nonexponential curve, and the worst case is approached through a vanishing atom escaping to infinity. The same constant is the exact guarantee of dominant-strategy mechanisms with individual rationality and strong budget balance in every realization. For two units with increasing submodular valuations, an explicit finite instance has ratio below $0.7290804$, so two units are strictly harder than one. Fixing the buyer, we characterize the least probability a random common price needs to guarantee a given ratio against every seller; bounding this quantity over all buyers would determine the exact two-unit constant. Within an explicit family the worst ratio is $0.729080\dots$, conjectured to be the two-unit constant.