Algorithms, Combinatorics and Optimization Seminar April 4, 2024 3:00pm — 4:00pm Location: In Person - Wean Hall 8220 Speaker: PAWEL PRALAT, Professor, Department of Mathematics, Toronto Metropolitan University https://math.ryerson.ca/~pralat/ Random Matching Markets 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. 4:00 pm → tea and cookies in the math lounge (bring your own mug if you have one), Wean 6220 Event Website: https://aco.math.cmu.edu/abs-23-24/apr04.html Add event to Google Add event to iCal