Fixed-Price Approximations in Bilateral Trade
share
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 𝔼[S + (B-S) 1_S ≤ p < B] or expected gains from trade 𝔼[(B-S) 1_S ≤ 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 2+√(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.
READ FULL TEXT