Az előadásra hibrid formában kerül sor zoom felületen, illetve személyesen a K.0.11-12-es földszinti előadóban 2025.05.29-én, 13.00 órától.
Előadó: Christopher Stapenhurst (BME)
Cím: Randomized Deferred Acceptance and Possibility Based Strategy Proofness
(joint work with József Pínter and Regina Stangl)
Absztrakt:
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.
