Anarchy, stability, and utopia: Creating better matchings

We consider the loss in social welfare caused by individual rationality in matching scenarios. We give both theoretical and experimental results comparing stable matchings with socially optimal ones, as well as studying the convergence of various natural algorithms to stable matchings. Our main goal is to design mechanisms in order to incentivize agents to participate in matchings that are socially desirable. We show that theoretically, the loss in social welfare caused by strategic behavior can be substantial. We analyze some natural distributions of utilities that agents receive from matchings, and find that in most cases the stable matching attains close to the optimal social welfare. Furthermore, for certain graph structures, simple greedy algorithms for partnerswitching (some without convergence guarantees) converge to stability remarkably quickly in expectation. Even when stable matchings are significantly socially suboptimal, slight changes in incentives can provide good solutions. We derive conditions for the existence of approximately stable matchings that are also close to socially optimal, which demonstrates that adding small switching costs can make socially optimal matchings stable. We also show that introducing heterogeneity in tastes can greatly improve social outcomes.