Tighter Bounds for the Random-Offerer Mechanism in Bilateral Trade

Abstract

The random-offerer mechanism for bilateral trade selects the seller or the buyer uniformly and lets the selected agent make a profit-maximizing take-it-or-leave-it offer. Let $\ddot{I}{}_{\mathrm{RO}}$ be the infimum, over independent value distributions, of the mechanism's gains from trade divided by first-best gains from trade. We prove $\frac{1}{\ddot{I}}€\le \ddot{I}{}_{\mathrm{RO}}<0.460242308085529$. For the lower bound, we improve the previous guarantee from approximately $0.317844$ to $1/\ddot{I}€\approx 0.318310$. The proof uses a parameterized Lagrangian bound for pointwise-monotone allocations. At multiplier one, this bound has coefficient $2/\ddot{I}€$, and the Lagrangian separates into two terms controlled by the optimal seller-offering and buyer-offering profits. For the upper bound, we construct an explicit family consisting of a truncated equal-revenue buyer and a seller distribution with a tilted power-law lower tail and a constant-virtual-cost segment. The family satisfies $\mathrm{FB}/\mathrm{RO}>2.17276852308451$, improving the previous explicit ratio $2.0749$; rigorous interval arithmetic certifies the numerical inequality.

27 pages, 1 table

Topics & keywords