Speeding up deferred acceptance

Gutin, Gregory Z.; Karapetyan, Daniel; Neary, Philip R.; Vickery, Alexander; Yeo, Anders

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 these efficiency savings can be strict.

Citation

Gutin, G. Z., Karapetyan, D., Neary, P. R., Vickery, A., & Yeo, A. (in press). Speeding up deferred acceptance. Journal of Mechanism and Institution Design,

• Journal Article Type: Article
• Acceptance Date: Jan 15, 2025
• Deposit Date: Mar 7, 2025
• Journal: Journal of Mechanism and Institution Design
• Print ISSN: 2399-844X
• Electronic ISSN: 2399-8458
• Publisher: Society for the Promotion of Mechanism and Institution Design
• Peer Reviewed: Peer Reviewed
• Public URL: https://nottingham-repository.worktribe.com/output/46206848