Abstract

We study the problem of approximating social welfare in bilateral trade using a finite number of samples. The seminal result of~\citet{myerson_efficient_1983} show that no Bayesian incentive compatible, individually rational, and budget balance mechanism can achieve the optimal social welfare even in bilateral trade, arguably the simplest two-sided market, where a seller is selling an item to a buyer. 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. In this paper, 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. We propose a new family of mechanisms that we refer to as the \emph{order statistic mechanisms} and provide a complete characterization of their approximation ratios for any fixed number of samples. Using the characterization, we numerically compute the approximation ratios obtained by the optimal order statistic mechanism for small sample sizes (no more than $10$ samples), and observe that they significantly outperform the single sample mechanism.

Biography

Jinzhao Wu is a final-year undergraduate in Turing Class, Peking University. He has a broad interest in theoretical computer science with particular interests in algorithms under uncertainty and algorithmic game theory.

• Admission

Tencent ID: 935-154-875