In two-sided settings, market designers tend to advocate for deferred acceptance (DA) over priority mechanisms, even though theory tells us that both types of mechanisms can yield unstable matches in incomplete information equilibrium. However, if match participants on the proposed-to side deviate from equilibrium by truth-telling, then DA yields stable outcomes. In a novel experimental setting, we find out-of-equilibrium truth-telling under DA but not under a priority mechanism, which could help to explain the success of DA in preventing unraveling in the field. We then attempt to explain the difference in behavior across mechanisms by estimating an experience-weighted learning model adapted to this complex strategic environment. We find that initial beliefs drive the difference in agents’ ability to find strategic equilibria, rather than alternative explanations such as differences in the learning process.