Abstract

The paper to be presented is:

Title: The Influence of One Strategic Agent on the Core of Stable Matchings
Author: Ron Kupfer

Paper Abstract: In this work, we analyze the influence of a single strategic agent on the quality of the other agents' matchings in a matching market. We consider a stable matching problem with n men and n women when preferences are drawn uniformly from the possible n!^(2n) full ranking options. We focus on the effect of a single woman who reports a modified preferences list in a way that is optimal from her perspective. We show that in this case, the quality of the matching dramatically improves from the other women's perspective. When running the Gale-Shapley men-proposing algorithm, the expected women-rank is O(log^4(n)) and almost surely the average women-rank is O(log^(2+ϵ) n), rather than a rank of O(n/(logn)) in both cases under a truthful regime. On the other hand, almost surely, the average men's rank is no better than Omega(n/(log^(2+ϵ) n)) compared to a rank of O(logn) under a truthful regime. All of the results hold for any matching algorithm that guarantees a stable matching, which suggests that the core convergence observed in real markets may be caused by the strategic behavior of the participants.

Link to paper.

This week's presenter is: Ndiamé Ndiaye, McGill University.