Approximate efficiency in matching markets

Nicole Immorlica*, Brendan Lucier, Glen Weyl, Joshua Mollner

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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’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.

Original languageEnglish (US)
Title of host publicationWeb and Internet Economics - 13th International Conference, WINE 2017, Proceedings
EditorsNikhil R. Devanur, Pinyan Lu
PublisherSpringer Verlag
Pages252-265
Number of pages14
ISBN (Print)9783319719238
DOIs
StatePublished - Jan 1 2017
Event13th International Conference on Web and Internet Economics, WINE 2017 - Bangalore, India
Duration: Dec 17 2017Dec 20 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10660 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Conference on Web and Internet Economics, WINE 2017
CountryIndia
CityBangalore
Period12/17/1712/20/17

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Approximate efficiency in matching markets'. Together they form a unique fingerprint.

Cite this