The presentation will take place in a hybrid format via zoom interface or in person in the room K.0.11-12 on 29.05.2025, from 13.00.
Speaker: Christopher Stapenhurst (BME)
Title: Randomized Deferred Acceptance and Possibility Based Strategy Proofness
(joint work with József Pínter and Regina Stangl)
Abstract:
The deferred acceptance (DA) algorithm is known to be strategy-proof only for the proposing side in two-sided matching, with no deterministic and stable mechanism achieving strategy-proofness for both sides. We propose a randomized variant of DA—where man-proposing and woman-proposing DA are selected with equal probability—and show that it achieves strategy-proofness when agents evaluate lotteries over matchings optimistically (i.e., focusing on their best possible realization). To generalize this insight, we introduce possibility-based strategy-proofness (PBSP), a new incentive concept requiring that no agent can misreport preferences to make a strictly better matching possible in the lottery. We prove that random DA satisfies PBSP, offering a viable path to incentive-compatible stable matching without restricting to deterministic mechanisms. Our results demonstrate how stochasticity, combined with ordinal evaluations, can circumvent classic impossibility theorems.
