  The seminal impossibility result of Myerson and Satterthwaite (1983) states
that for bilateral trade, there is no mechanism that is individually rational
(IR), incentive compatible (IC), weakly budget balanced, and efficient. This
has led follow-up work on two-sided trade settings to weaken the efficiency
requirement and consider approximately efficient simple mechanisms, while still
demanding the other properties. The current state-of-the-art of such mechanisms
for two-sided markets can be categorized as giving one (but not both) of the
following two types of approximation guarantees on the gains from trade: a
constant ex-ante guarantee, measured with respect to the second-best efficiency
benchmark, or an asymptotically optimal ex-post guarantee, measured with
respect to the first-best efficiency benchmark. Here the second-best efficiency
benchmark refers to the highest gains from trade attainable by any IR, IC and
weakly budget balanced mechanism, while the first-best efficiency benchmark
refers to the maximum gains from trade (attainable by the VCG mechanism, which
is not weakly budget balanced).
  In this paper, we construct simple mechanisms for double-auction and matching
markets that simultaneously achieve both types of guarantees: these are ex-post
IR, Bayesian IC, and ex-post weakly budget balanced mechanisms that 1) ex-ante
guarantee a constant fraction of the gains from trade of the second-best, and
2) ex-post guarantee a realization-dependent fraction of the gains from trade
of the first-best, such that this realization-dependent fraction converges to 1
(full efficiency) as the market grows large.
