Approximate Efficiency in Matching Markets

We propose a measure of approximate ex-ante Pareto efficiency in matching markets. According to this measure, a lottery over matchings is gamma-approximately efficient if there is no alternate lottery in which each agent’s ex-ante expected utility increases by a gamma factor.  A mechanism is gamma-approximately efficient if every lottery produced in equilibrium is gamma-approximately efficient. We argue this is the natural extension of approximate efficiency in transferable-utility settings to our nontransferable-utility setting. Using this notion, we are able to quantify the intuited efficiency improvement of the so-called Boston mechanism and the recently-proposed choice-augmented deferred acceptance mechanism over the random serial dictatorship mechanism. Furthermore, we provide the first formal statement and analysis of the Raffle mechanism, which is conceptually simpler than the Boston mechanism and has a comparable efficiency guarantee.