@inproceedings{a3288f66cb27490c8523ce67ea304648,
title = "Approximate efficiency in matching markets",
abstract = "We propose a measure of approximate ex-ante Pareto efficiency in matching markets. According to this measure, a lottery over matchings is γ -approximately efficient if there is no alternate lottery in which each agent{\textquoteright}s ex-ante expected utility increases by an γ factor. A mechanism is γ -approximately efficient if every lottery produced in equilibrium is γ -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.",
author = "Nicole Immorlica and Brendan Lucier and Glen Weyl and Joshua Mollner",
year = "2017",
month = jan,
day = "1",
doi = "10.1007/978-3-319-71924-5_18",
language = "English (US)",
isbn = "9783319719238",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "252--265",
editor = "Devanur, {Nikhil R.} and Pinyan Lu",
booktitle = "Web and Internet Economics - 13th International Conference, WINE 2017, Proceedings",
note = "13th International Conference on Web and Internet Economics, WINE 2017 ; Conference date: 17-12-2017 Through 20-12-2017",
}