Speeding Up Deferred Acceptance

June 2025 ● Gregory Gutin , Daniel Karapetyan , Phillip R Neary , Alexander Vickery & Anders Yeo ● (Forthcoming) Journal of Mechanism & Institution Design

Download

Abstract

A run of the deferred acceptance (DA) algorithm may contain proposals that are sure to be rejected. In this paper we introduce the accelerated deferred acceptance algorithm that proceeds in a similar manner to DA but with sure-to-be rejected proposals ruled out. Accelerated deferred acceptance outputs the same stable matching as DA but does so more efficiently: it terminates in weakly fewer rounds, requires weakly fewer proposals, and stable pairs match no later. Computational experiments show that the efficiency savings can be strict.

Figure 1: The proportion of final pairs matched by round.

citation


            @article{gutin2024speedingdeferredacceptance,
            
              title =
              {Speeding up deferred acceptance},

            archivePrefix  =
              {arXiv},

             eprint =
              {2409.06865},
            primaryClass =
               {econ.TH} ,
            year =
              {2024},
            doi =
              https://doi.org/10.48550/arXiv.2409.06865,
            author =
              {Gregory Z. Gutin and Daniel Karapetyan and Philip R. Neary and Alexander Vickery and Anders Yeo}