Stable Mechanisms and Bounded Belief Revision

Abstract

Agents in matching markets typically cannot report their full preference list, and no stable mechanism induces truthful reporting, so the assignment an agent can expect depends on how others report and must be revised as she learns about her rivals. I ask how often a stable mechanism can force such revisions. I first show that the set of agents with a unique stable partner is identical across every stable mechanism, so no mechanism protects more agents than another in this sense, and any comparison must concern agents with multiple achievable partners. For these, deferred acceptance, whichever side proposes, bounds the number of revisions by the length of the agent's reported list alone, uniformly across market size, and every revision is an improvement. This bound is neither automatic under stability and optimality nor exclusive to deferred acceptance: I construct a stable, optimal mechanism under which revisions are unbounded, and another, distinct from both extremes, that still achieves the bound. Finally, I show that a directional condition on how a mechanism switches between the two extremal stable matchings, which I call non-regression, is sufficient for the bound.