Algorithms, Combinatorics and Optimization Seminar

— 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