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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Games under the Tiered Deferred Acceptance Mechanism
We study the tiered deferred acceptance mechanism used in school admissions, such as in China and Turkey. This mechanism partitions schools into tiers and applies the deferred acceptance algorithm within each tier. Once …
Equitable Stable Matchings in Quadratic Time
Can a stable matching that achieves high equity among the two sides of a market be reached in quadratic time? The Deferred Acceptance (DA) algorithm finds a stable matching that is biased in favor of one side; optimizing…
Market Design with Deferred Acceptance: A Recipe for Policymaking
We introduce a method to derive from a characterization of institutional choice rules (or priority rules), a characterization of the Gale-Shapley deferred-acceptance (DA) matching rule based on these choice rules. We app…
Mechanisms for a dynamic many-to-many school choice problem
We examine the problem of assigning teachers to public schools over time when teachers have tenured positions and can work simultaneously in multiple schools. To do this, we investigate a dynamic many-to-many school choi…
Monotone comparative statics for submodular functions, with an application to aggregated deferred acceptance
We propose monotone comparative statics results for maximizers of submodular functions, as opposed to maximizers of supermodular functions as in the classical theory put forth by Veinott, Topkis, Milgrom, and Shannon amo…
Combinatorial Optimization