Speeding up deferred acceptance
<|reference_start|>Speeding up deferred acceptance: 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.<|reference_end|>
@article{gutin2024speeding,
    title={Speeding up deferred acceptance},
    author={Gregory Z. Gutin and Daniel Karapetyan and Philip R. Neary and
  Alexander Vickery and Anders Yeo},
    journal={arXiv preprint arXiv:2409.06865},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.06865},
    primaryClass={econ.TH cs.GT}
}