Speeding up deferred acceptance

• Tác giả: Gregory Z Gutin, Daniel Karapetyan, Philip R Neary, Alexander Vickery, Anders Yeo
• Ngôn ngữ: eng
• Ký hiệu phân loại: 641.555 Timesaving cooking
• Thông tin xuất bản: 2024
• Bộ sưu tập: Metadata
• ID: 204128

Tóm tắt

A run of the deferred acceptance (DA) algorithm may contain proposals that are sure to be rejected. 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 final pairs match no later. Computational experiments show that these efficiency savings can be strict.