UVictoria Discrete Math Seminar: Pawel Pralat

Stable matching mechanisms are ubiquitous in theory and in practice, with centralized mechanisms used to match students to schools or medical residents to hospitals. It is known that imbalance in the number of agents on either side of a random matching market has a profound effect on the market’s expected characteristics. The “long side” (i.e. the side with a greater number of agents) receives significantly worse matches in expectation than the “short side”. As a result, agents on the long side have very little market power, and must settle for a match which is not much better than a random assignment. During the talk, I will discuss classical results and present a new proof that analyzes the most natural algorithm (“long side proposing”) producing the optimal stable outcome. This new proof, arguably, provides a better intuition for this surprising huge advantage of the short side.