On the Optimal Fixed-Price Mechanism in Bilateral Trade

We study the problem of social welfare maximization in bilateral trade, where two agents, a buyer and a seller, trade an indivisible item. The seminal result of Myerson and Satterthwaite [29] shows that no incentive compatible and budget balanced (i.e., the mechanism does not run a deficit) mechanism can achieve the optimal social welfare in bilateral trade. Motivated by this impossibility result, we focus on approximating the optimal social welfare. We consider arguably the simplest form of mechanisms -the fixed-price mechanisms, where the designer offers trade at a fixed price to the seller and buyer. Besides the simple form, fixed-price mechanisms are also the only dominant strategy incentive compatible and budget balanced mechanisms in bilateral trade [23].

We obtain improved approximation ratios of fixed-price mechanisms in both (i) the setting where the designer has the full prior information, that is, the value distributions of both the seller and buyer; and (ii) the setting where the designer only has access to limited information of the prior. In the full prior information setting, we show that the optimal fixed-price mechanism can achieve at least 0.72 of the optimal welfare, and no fixed-price mechanism can achieve more than 0.7381 of the optimal welfare. Prior to our result the state of the art approximation ratio was 1-1 e +0.0001 ≈ 0.632 [24]. Interestingly, we further show that the optimal approximation ratio achievable with full prior information is identical to the optimal approximation ratio obtainable with only one-sided prior information, i.e., the buyer's or the seller's value distribution. As a simple corollary, our upper and lower bounds in the full prior information setting also apply to the one-sided prior information setting.

We further consider two limited information settings. In the first one, the designer is only given the mean of the buyer's value (or the mean of the seller's value). We show that with such minimal information, one can already design a fixed-price mechanism that achieves 2/3 of the optimal social welfare, which surpasses the previous state of the art ratio even when the designer has access to the full prior information. Furthermore, 2/3 is the optimal attainable ratio in this setting. In the second limited information setting, we assume that the designer has access to finitely many samples from the value distributions. Recent results show that one can already obtain a constant factor approximation to the optimal welfare using a single sample from the seller's distribution [3,16,24]. Our goal is to understand what approximation ratios are possible if the designer has more than one but still finitely many samples. This is usually a technically more challenging regime and requires tools different from the single-sample analysis. We propose a new family of sample-based fixed-price mechanisms that we refer to as the order statistic mechanisms and provide a complete characterization of their approximation ratios for any fixed number of samples. Using the characterization, we provide the optimal approximation ratios obtainable by order statistic mechanism for small sample sizes (no more than 10 samples) and observe that they significantly outperform the single sample mechanism.